Hybrid opdel-og-hersk tilgang til træsøgningsalgoritmer

Hybrid opdel-og-hersk tilgang til træsøgningsalgoritmer

Tidsstempel: 23. marts 2023 kl. 9:57
Kildeknude: 2029300

Mathys Rennela1, Sebastiaan Brand2, Alfons Laarman2, og Vedran Dunjko2

1Laboratoire de Physique de l'Ecole Normale Supérieure, Inria, CNRS, ENS-PSL, Mines-Paristech, Sorbonne Université, PSL Research University, Paris, Frankrig
2LIACS, Leiden University, Leiden, Holland

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

En af udfordringerne ved kvantecomputere på kort og mellemlang sigt er det begrænsede antal qubits, vi kan bruge til beregninger. At finde metoder, der opnår nyttige kvanteforbedringer under størrelsesbegrænsninger, er således et nøglespørgsmål på området. På denne måde blev det for nylig vist, at en hybrid klassisk-kvante-metode kan hjælpe med at give polynomielle speed-ups til klassiske divide-and-conquer-algoritmer, selv når kun gives adgang til en kvantecomputer, der er meget mindre end selve problemet. I dette arbejde studerer vi hybrid divide-and-conquer-metoden i sammenhæng med træsøgningsalgoritmer og udvider den ved at inkludere kvantebacktracking, som giver bedre resultater end tidligere Grover-baserede metoder. Yderligere giver vi generelle kriterier for polynomielle speed-ups i træsøgningskonteksten, og giver en række eksempler, hvor polynomiale speed ups, ved hjælp af vilkårligt mindre kvantecomputere, kan opnås. Vi leverer betingelser for speedups for den velkendte algoritme for DPLL, og vi beviser tærskelfri speedups for PPSZ-algoritmen (kernen i den hurtigste nøjagtige booleske tilfredsstillelsesløser) for velopdragne klasser af formler. Vi giver også et simpelt eksempel, hvor speed-ups kan opnås på en algoritme-uafhængig måde under visse velundersøgte kompleksitetsteoretiske antagelser. Til sidst diskuterer vi kort de grundlæggende begrænsninger af hybride metoder i at give speed-ups til større problemer.

Populært resumé

På kort og mellemlang sigt, med kvantecomputere med et begrænset antal qubits, kan visse problemforekomster være for store til at blive løst på en kvantecomputer. I denne sammenhæng er det naturligt at se på opdel-og-hersk-strategier: opdel klassisk problemet i dele, der er små nok til at blive løst på kvantecomputeren og kombiner resultaterne bagefter. Dette kaldes en kvante-klassisk hybridalgoritme.

Træsøgningsalgoritmer er særligt velegnede til denne hybride tilgang. Når søgerummet er et komplet binært træ, er det ligetil at dele problemet op i dele, der er små nok til en given kvantecomputer og stadig stå tilbage med en (mindre) kvantehastighed på det oprindelige problem. Men i de fleste klassiske træsøgningsalgoritmer beskæres grene under søgningen, og et sparsommere træ forbliver. I denne indstilling bliver det mindre indlysende, hvis en lille polynomiel speedup stadig kan opnås med en hybridalgoritme.

I dette papir studerer vi denne hybride opdel-og-hersk-metode i sammenhæng med træsøgningsalgoritmer, såsom algoritmerne udviklet til boolsk tilfredsstillelse. Vores vigtigste bidrag er, at vi giver tilstrækkelige betingelser for kvantehastigheder og anvender dem på to velkendte boolske tilfredshedsalgoritmer.

► BibTeX-data

► Referencer

[1] Vedran Dunjko, Yimin Ge og J Ignacio Cirac. "Beregningshastigheder ved hjælp af små kvanteenheder". Physical review letters 121, 250501 (2018).
https://​/​doi.org/​10.1103/​PhysRevLett.121.250501

[2] Yimin Ge og Vedran Dunjko. "En hybrid algoritmeramme til små kvantecomputere med anvendelse til at finde Hamiltonske cyklusser". Journal of Mathematical Physics 61, 012201 (2020).
https://​/​doi.org/​10.1063/​1.5119235

[3] Ashley Montanaro. "Quantum-Walk Speedup of Backtracking Algorithms". Theory of Computing 14, 1-24 (2018).
https://​/​doi.org/​10.4086/​toc.2018.v014a015

[4] Martin Davis, George Logemann og Donald W Loveland. "Et maskinelt program til sætningsbevis". New York University, Institute of Mathematical Sciences. (1961).
https://​/​doi.org/​10.1145/​368273.368557

[5] Ramamohan Paturi, Pavel Pudlák, Michael E Saks og Francis Zane. "En forbedret eksponentiel-tidsalgoritme for k-SAT". Journal of the ACM (JACM) 52, 337–364 (2005).
https://​/​doi.org/​10.1145/​1066100.1066101

[6] Earl Campbell, Ankur Khurana og Ashley Montanaro. "Anvendelse af kvantealgoritmer til problemer med begrænsningstilfredshed". Quantum 3, 167 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-18-167

[7] Simon Martiel og Maxime Remaud. "Praktisk implementering af en kvante-backtracking-algoritme". I international konference om aktuelle tendenser i teori og praksis for informatik. Side 597–606. Springer (2020).
https:/​/​doi.org/​10.1007/​978-3-030-38919-2_49

[8] Thomas Dueholm Hansen, Haim Kaplan, Or Zamir og Uri Zwick. "Hurtigere k-sat algoritmer ved hjælp af biased-ppsz". I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Side 578–589. STOC 2019New York, NY, USA (2019). ACM.
https://​/​doi.org/​10.1145/​3313276.3316359

[9] Armin Biere, Marijn Heule og Hans van Maaren. "Håndbog om tilfredshed". Bind 185. IOS tryk. (2009).

[10] Marc Mezard, Marc Mezard og Andrea Montanari. "Information, fysik og beregning". Oxford University Press. (2009).
https://​/​doi.org/​10.1063/​1.3397047

[11] Martin Davis og Hilary Putnam. "En beregningsprocedure for kvantificeringsteori". J. ACM 7, 201-215 (1960).
https://​/​doi.org/​10.1145/​321033.321034

[12] Marijn JH Heule, Matti Juhani Järvisalo, Martin Suda, et al. "Løser- og benchmarkbeskrivelser". I Proceedings of SAT-konkurrence 2018. Institut for Datalogi, Helsinki Universitet (2018). url: http://hdl.handle.net/​10138/​237063.
http://​hdl.handle.net/​10138/​237063

[13] Robert Nieuwenhuis, Albert Oliveras og Cesare Tinelli. "Abstrakt DPLL og abstrakte DPLL modulo teorier". I international konference om logik til programmering af kunstig intelligens og ræsonnement. Side 36-50. Springer (2005).
https:/​/​doi.org/​10.1007/​978-3-540-32275-7_3

[14] Jasmin Christian Blanchette, Sascha Böhme og Lawrence C Paulson. "Udvidelse af Sledgehammer med SMT-løsere". Journal of automated reasoning 51, 109–128 (2013).
https:/​/​doi.org/​10.1007/​s10817-013-9278-5

[15] Daniel Rolf. "Derandomisering af PPSZ for unik-k-SAT". I international konference om teori og anvendelser af tilfredshedstestning. Side 216–225. Springer (2005).
https://​/​doi.org/​10.1007/​11499107_16

[16] Dominik Scheder og John P Steinberger. "PPSZ til generel k-SAT, hvilket gør Hertlis analyse enklere og 3-SAT hurtigere". I 32nd Computational Complexity Conference (CCC 2017). Bind 79, side 9:1–9:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017).
https://​/​doi.org/​10.4230/​LIPIcs.CCC.2017.9

[17] Daniel Rolf. "Forbedret bundet til PPSZ/​schoning-algoritmen for 3-SAT". Journal on Satisfiability, Boolean Modeling and Computation 1, 111-122 (2006).
https:/​/​doi.org/​10.3233/​SAT190005

[18] Timon Hertli. "3-SAT hurtigere og enklere - unikke-SAT-grænser for PPSZ holder generelt". SIAM Journal on Computing 43, 718–729 (2014).
https://​/​doi.org/​10.1137/​120868177

[19] Timon Hertli. "Bryder PPSZ-barrieren for unik 3-SAT". In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, København, Danmark, 8.-11. juli 2014, Proceedings, Part I 41. Side 600–611. Springer (2014).
https:/​/​doi.org/​10.1007/​978-3-662-43948-7_50

[20] Dominik Scheder. "PPSZ er bedre end du tror". I 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Side 205–216. (2022).
https://​/​doi.org/​10.1109/​FOCS52979.2021.00028

[21] Lov K Grover. "En hurtig kvantemekanisk algoritme til databasesøgning". I Proceedings af det otteogtyvende årlige ACM-symposium om teori om computing. Side 212–219. (1996).
https://​/​doi.org/​10.1145/​237814.237866

[22] Andris Ambainis. "Kvante søgealgoritmer". ACM SIGACT News 35, 22–35 (2004).
https://​/​doi.org/​10.1145/​992287.992296

[23] Andris Ambainis og Martins Kokainis. "Kvantealgoritme til estimering af træstørrelse, med applikationer til backtracking og 2-spiller spil". I Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Side 989-1002. (2017).
https://​/​doi.org/​10.1145/​3055399.3055444

[24] Michael Jarret og Kianna Wan. "Forbedrede kvante-backtracking-algoritmer ved hjælp af effektive resistensestimater". Fysisk anmeldelse A 97, 022337 (2018).
https://​/​doi.org/​10.1103/​PhysRevA.97.022337

[25] Dominic J. Moylett, Noah Linden og Ashley Montanaro. "Kvantefremskyndelse af rejsende sælger-problemet for grafer med afgrænsede grader". Phys. Rev. A 95, 032323 (2017).
https://​/​doi.org/​10.1103/​PhysRevA.95.032323

[26] Neil D. Jones og William T. Laaser. "Fuldstændige problemer for deterministisk polynomisk tid". Teoretisk datalogi 3, 105 – 117 (1976).
https:/​/​doi.org/​10.1016/​0304-3975(76)90068-2

[27] Raymond Greenlaw, H James Hoover, Walter L Ruzzo, et al. "Grænser for parallel beregning: P-fuldstændighedsteori". Oxford University Press on Demand. (1995).

[28] Thomas Lengauer og Robert E Tarjan. "Asymptotisk snævre grænser for afvejninger mellem tid og rum i et stenspil". Journal of the ACM (JACM) 29, 1087-1130 (1982).
https://​/​doi.org/​10.1145/​322344.322354

[29] Charles H Bennett. "Tid/rum-afvejninger for reversibel beregning". SIAM Journal on Computing 18, 766–776 (1989).
https://​/​doi.org/​10.1137/​0218053

[30] T. Altman og Y. Igarashi. "Groft sortering: Sekventiel og parallel tilgang". J. Inf. Behandle. 12, 154-158 (1989). url: http://​/​id.nii.ac.jp/​1001/​00059782/​.
http://​/​id.nii.ac.jp/​1001/​00059782/​

[31] Hong-Yu Liang og Jing He. "Tilfredshed med indeksafhængighed". Journal of Computer Science and Technology 27, 668–677 (2012).
https:/​/​doi.org/​10.1007/​978-3-642-17517-6_7

[32] Marcello Benedetti, John Realpe-Gómez og Alejandro Perdomo-Ortiz. "Kvante-assisterede Helmholtz-maskiner: En kvante-klassisk deep learning-ramme for industrielle datasæt i enheder på kort sigt". Quantum Science and Technology 3, 034007 (2018).
https:/​/​doi.org/​10.1088/​2058-9565/​aabd98

[33] Aram W. Harrow. "Små kvantecomputere og store klassiske datasæt" (2020) arXiv:2004.00026.
arXiv: 2004.00026

[34] Michael A Nielsen og Isaac Chuang. "Kvanteberegning og kvanteinformation". American Association of Physics Teachers. (2002).
https://​/​doi.org/​10.1017/​CBO9780511976667

[35] Robert B. Griffiths og Chi-Sheng Niu. "Semiklassisk fourier-transformation til kvanteberegning". Phys. Rev. Lett. 76, 3228-3231 (1996).
https://​/​doi.org/​10.1103/​PhysRevLett.76.3228

[36] Robert Raussendorf og Hans J. Briegel. "En envejs kvantecomputer". Phys. Rev. Lett. 86, 5188-5191 (2001).
https://​/​doi.org/​10.1103/​PhysRevLett.86.5188

[37] Thomas E O'Brien, Brian Tarasinski og Barbara M Terhal. "Kvantefaseestimering af flere egenværdier for småskala (støjende) eksperimenter". New Journal of Physics 21, 023022 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​aafb8e

[38] Akshay Ajagekar, Travis Humble og Fengqi You. "Kvantecomputerbaserede hybride løsningsstrategier til storskala diskrete-kontinuerlige optimeringsproblemer". Computers & Chemical Engineering 132, 106630 (2020).
https://​/​doi.org/​10.1016/​j.compchemeng.2019.106630

[39] Tianyi Peng, Aram W Harrow, Maris Ozols og Xiaodi Wu. "Simulering af store kvantekredsløb på en lille kvantecomputer". Physical review letters 125, 150504 (2020).
https://​/​doi.org/​10.1103/​PhysRevLett.125.150504

[40] Sergey Bravyi, Graeme Smith og John A. Smolin. "Handel med klassiske og kvanteberegningsressourcer". Fysisk gennemgang X 6 (2016).
https://​/​doi.org/​10.1103/​physrevx.6.021043

[41] Martijn Swenne. "Løser SAT på støjende kvantecomputere". https://​/​theses.liacs.nl/​1725 (2019). Bacheloropgave.
https://​/​theses.liacs.nl/​1725

[42] Theodore J Yoder, Guang Hao Low og Isaac L Chuang. "Fastpunkt kvantesøgning med et optimalt antal forespørgsler". Physical review letters 113 (2014).
https://​/​doi.org/​10.1103/​PhysRevLett.113.210501

[43] Alessandro Cosentino, Robin Kothari og Adam Paetznick. "Afkvantisering af Read-once Quantum Formulas". I 8. konference om teorien om kvanteberegning, kommunikation og kryptografi (TQC 2013). Bind 22 af Leibniz International Proceedings in Informatics (LIPIcs), side 80-92. Dagstuhl, Tyskland (2013). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://​/​doi.org/​10.4230/​LIPIcs.TQC.2013.80

[44] David A Barrington. "Afgrænsningsprogrammer i polynomisk størrelse genkender præcis de sprog i NC1". Journal of Computer and System Sciences 38, 150-164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

Citeret af

[1] Casper Gyurik, Chris Cade og Vedran Dunjko, "Mod kvantefordel via topologisk dataanalyse", arXiv: 2005.02607, (2020).

[2] Kyle EC Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield og Eleanor Rieffel, "Quantum-accelerated constraint programmering", Quantum 5 (550).

[3] Casper Gyurik, Chris Cade og Vedran Dunjko, "Mod kvantefordel via topologisk dataanalyse", Quantum 6 (855).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-03-25 02:02:00). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2023-03-25 02:01:59).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

Tidsstempel:

Mere fra Quantum Journal