zbMATH — the first resource for mathematics

Quantum-walk speedup of backtracking algorithms. (English) Zbl 1417.68046
The author discusses quantum algorithms speedup via the technique of backtracking. To find a complete solution of a constraint satisfaction problems (CSP) backtracking algorithms explore a tree with vertices representing partial solutions of the CSP. The Davis-Putnam-Logemann-Loveland (DPLL) algorithm can be considered as a guiding example. The suggested quantum algorithms make use of an approach discussed in [A. Belovs, “Quantum walks and electric networks”, Preprint, arXiv:1302.3143] for detecting a marked vertex on a graph by a quantum walk. Some analogue of the so-called “staggered” quantum walk on a backtracking tree is used to detect the required solution.

68Q12 Quantum algorithms and complexity in the theory of computing
05C81 Random walks on graphs
81P68 Quantum computation
BKZ; MiniSat
Full Text: DOI
[1] [1] SCOTTAARONSON ANDANDRISAMBAINIS: Quantum search of spatial regions. Theory of Computing, 1(4):47–79, 2005. Preliminary version inFOCS’03. [doi:10.4086/toc.2005.v001a004, arXiv:quant-ph/0303041]4,5,18,19
[2] [2] ERDEMALKIM, LÉODUCAS, THOMASPÖPPELMANN,ANDPETERSCHWABE: Post-quantum key exchange – a new hope. In Proc. 25th USENIX Security Symp. (USENIX Security’16), pp. 327–343. USENIX Association, 2016. Available atIACR.7
[3] [3] ANDRISAMBAINIS: Quantum search algorithms. ACM SIGACT News, 35(2):22–35, 2004. [doi:10.1145/992287.992296,arXiv:quant-ph/0504012]7 THEORY OFCOMPUTING, Volume 14 (15), 2018, pp. 1–2419 ASHLEYMONTANARO
[4] [4] ANDRISAMBAINIS: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210– 239, 2007. Preliminary version inFOCS’04. [doi:10.1137/S0097539705447311,arXiv:quantph/0311001]5
[5] [5] ANDRISAMBAINIS, ANDREWM. CHILDS, BENW. REICHARDT, ROBERTŠPALEK,AND SHENGYUZHANG: Any AND-OR formula of size N can be evaluated in time N1/2+o(1)on a quantum computer. SIAM J. Comput., 39(6):2513–2530, 2010. Preliminary version inFOCS’07. [doi:10.1137/080712167,arXiv:quant-ph/0703015]7
[6] [6] ANDRISAMBAINIS ANDRONALD DEWOLF: Average-case quantum query complexity. J. Phys. A: Math. Gen., 34(35):6741–6754, 2001. Preliminary version inSTACS’00. [doi:10.1088/03054470/34/35/302,arXiv:quant-ph/9904079]4
[7] [7] ANDRISAMBAINIS ANDMARTINSKOKAINIS: Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In Proc. 49th STOC, pp. 989–1002. ACM Press, 2017. [doi:10.1145/3055399.3055444,arXiv:1704.06774]4,7
[8] [8] OLAANGELSMARK, VILHELMDAHLLÖF,ANDPETERJONSSON: Finite domain constraint satisfaction using quantum computation. In Proc. 27th Internat. Symp. Mathemat. Found. Comput. Sci. (MFCS’02), pp. 93–103. Springer, 2002. [doi:10.1007/3-540-45687-2_7]6 · Zbl 1014.68217
[9] [9] PETER VANBEEK: Backtracking search algorithms. In Handbook of Constraint Programming. Elsevier, 2006. [doi:10.1016/S1574-6526(06)80008-8]2,5
[10] [10] ALEKSANDRSBELOVS: Quantum walks and electric networks, 2013. [arXiv:1302.3143]5,8,9, 10
[11] [11] ALEKSANDRSBELOVS, ANDREWM. CHILDS, STACEYJEFFERY, ROBINKOTHARI,AND FRÉDÉRICMAGNIEZ: Time-efficient quantum walks for 3-distinctness. In Proc. 40th Internat. Colloq. on Automata, Languages and Programming (ICALP’13), pp. 105–122. Springer, 2013. [doi:10.1007/978-3-642-39206-1_10,arXiv:1302.7316]5,9
[12] [12] CHARLESH. BENNETT, ETHANBERNSTEIN, GILLESBRASSARD,ANDUMESHV. VAZIRANI: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [doi:10.1137/S0097539796300933,arXiv:quant-ph/9701001]18
[13] [13] ETHANBERNSTEIN ANDUMESHV. VAZIRANI: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version inSTOC’93. [doi:10.1137/S0097539796300921]9
[14] [14] GILLESBRASSARD, PETERHØYER, MICHELEMOSCA,ANDALAINTAPP: Quantum amplitude amplification and estimation. In SAMUELJ. LOMONACO, JR.ANDHOWARDE. BRANDT, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics, pp. 53–74. AMS, 2002. [doi:10.1090/conm/305/05215,arXiv:quant-ph/0005055]6
[15] [15] CHRISCADE, ASHLEYMONTANARO,ANDALEKSANDRSBELOVS: Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Inf. Comput., 18(1 & 2):18–50, 2018. [arXiv:1610.00581]16 THEORY OFCOMPUTING, Volume 14 (15), 2018, pp. 1–2420 QUANTUM-WALKSPEEDUP OFBACKTRACKINGALGORITHMS
[16] [16] NICOLASJ. CERF, LOVK. GROVER,ANDCOLINP. WILLIAMS: Nested quantum search and structured problems. Phys. Rev. A, 61(3):032303:1–14, 2000. [doi:10.1103/PhysRevA.61.032303, arXiv:quant-ph/9806078]5,6
[17] [17] ASHOKK. CHANDRA, PRABHAKARRAGHAVAN, WALTERL. RUZZO, ROMANSMOLENSKY,ANDPRASOONTIWARI: The electrical resistance of a graph captures its commute and cover times.Comput. Complexity, 6(4):312–340, 1996.Preliminary version inSTOC’89. [doi:10.1007/BF01270385]5,9
[18] [18] YUANMICHEN ANDPHONGQ. NGUYEN: BKZ 2.0: Better lattice security estimates. In Proc. 17th Internat. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT’11), pp. 1–20. Springer, 2011. [doi:10.1007/978-3-642-25385-0_1]7
[19] [19] ANDREWM. CHILDS, RICHARDCLEVE, ENRICODEOTTO, EDWARDFARHI, SAMGUTMANN, ANDDANIELA. SPIELMAN: Exponential algorithmic speedup by a quantum walk. In Proc. 35th STOC, pp. 59–68. ACM Press, 2003. [doi:10.1145/780542.780552,arXiv:quant-ph/0209131]5
[20] [20] RICHARDCLEVE, ARTUREKERT, CHIARAMACCHIAVELLO,ANDMICHELEMOSCA: Quantum algorithms revisited. Proc. Royal Soc. A, 454(1969):339–354, 1998. [doi:10.1098/rspa.1998.0164, arXiv:quant-ph/9708016]8
[21] [21] EVGENYDANTSIN, VLADIKKREINOVICH,ANDALEXANDERWOLPERT: On quantum versions of record-breaking algorithms for SAT.ACM SIGACT News, 36(4):103–108, 2005. [doi:10.1145/1107523.1107524]7
[22] [22] MARTINDAVIS, GEORGELOGEMANN,ANDDONALDLOVELAND: A machine program for theorem-proving. Commun. ACM, 5(7):394–397, 1962. [doi:10.1145/368273.368557]2
[23] [23] MARTINDAVIS ANDHILARYPUTNAM: A computing procedure for quantification theory. J. ACM, 7(3):201–215, 1960. [doi:10.1145/321033.321034]2
[24] [24] RAFAËL DELPINO, VADIMLYUBASHEVSKY,ANDDAVIDPOINTCHEVAL: The whole is less than the sum of its parts: Constructing more efficient lattice-based AKEs. In Proc. 10th Internat. Conf. on Security and Cryptography for Networks (SCN’16), pp. 273 – 291. Springer, 2016. [doi:10.1007/9783-319-44618-9_15]7
[25] [25] NIKLASEÉN ANDNIKLASSÖRENSSON: An extensible SAT-solver. In Proc. 6th Internat. Conf. on Theory and Applications of Satisfiability Testing (SAT’03), pp. 502–518. Springer, 2003. [doi:10.1007/978-3-540-24605-3_37]2
[26] [26] EDWARDFARHI, JEFFERYGOLDSTONE, SAMGUTMANN, JOSHUALAPAN, ANDREWLUNDGREN,ANDDANIELPREDA: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science, 292(5516):472–475, 2001. [doi:10.1126/science.1057726, arXiv:quant-ph/0104129]7
[27] [27] EDWARDFARHI, JEFFERYGOLDSTONE, SAMGUTMANN,ANDMICHAELSIPSER: Quantum computation by adiabatic evolution. Technical report, MIT, 2000. [arXiv:quant-ph/0001106]7 THEORY OFCOMPUTING, Volume 14 (15), 2018, pp. 1–2421 ASHLEYMONTANARO
[28] [28] EDWARDFARHI ANDSAMGUTMANN: Quantum computation and decision trees. Phys. Rev. A, 58(2):915–928, 1998. [doi:10.1103/PhysRevA.58.915,arXiv:quant-ph/9706062]6
[29] [29] EUGENEC. FREUDER ANDALANK. MACKWORTH: Constraint satisfaction: An emerging paradigm. In Handbook of Constraint Programming, pp. 13–27. Elsevier, 2006. [doi:10.1016/S15746526(06)80006-4]5
[30] [30] MARTINFÜRER: Solving NP-complete problems with quantum search. In Proc. 10th Latin Amer. Symp. on Theoretical Informatics (LATIN’08), pp. 784–792. Springer, 2008. [doi:10.1007/978-3540-78773-0_67]6 · Zbl 1136.68519
[31] [31] NICOLASGAMA, PHONGQ. NGUYEN,ANDODEDREGEV: Lattice enumeration using extreme pruning. In Proc. 29th Internat. Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT’10), pp. 257–278. Springer, 2010. [doi:10.1007/978-3-642-13190-5_13]7
[32] [32] CARLAP. GOMES, HENRYKAUTZ, ASHISHSABHARWAL,ANDBARTSELMAN: Satisfiability solvers. In Handbook of Knowledge Representation, pp. 89–134. Elsevier, 2008. [doi:10.1016/S15746526(07)03002-7]2
[33] [33] LOVK. GROVER: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79(2):325–328, 1997. [doi:10.1103/PhysRevLett.79.325,arXiv:quant-ph/9706033]1
[34] [34] PETERHØYER ANDMOJTABAKOMEILI: Efficient quantum walk on the grid with multiple marked elements. In Proc. 34th Symp. Theoret. Aspects of Computer Sci. (STACS’17), pp. 42:1–42:14. DROPS, 2017. [doi:10.4230/LIPIcs.STACS.2017.42,arXiv:1612.08958]18
[35] [35] STACEYJEFFERY ANDSHELBYKIMMEL: NAND-trees, average choice complexity, and effective resistance, 2015. [arXiv:1511.02235]7
[36] [36] ALEXEIKITAEV: Quantum measurements and the abelian stabilizer problem, 1996. [arXiv:quantph/9511026]8
[37] [37] DONALDE. KNUTH: Estimating the efficiency of backtrack programs. Mathematics of Computation, 29(129), 1975. [doi:10.1090/S0025-5718-1975-0373371-6]5 · Zbl 0297.68037
[38] [38] HARIKROVI, FRÉDÉRICMAGNIEZ, MARISOZOLS,ANDJÉRÉMIEROLAND: Quantum walks can find a marked element on any graph. Algorithmica, 74(2):851–907, 2016. Preliminary version inICALP’10. [doi:10.1007/s00453-015-9979-8,arXiv:1002.2419]5,19
[39] [39] TROYLEE, RAJATMITTAL, BENW. REICHARDT, ROBERTŠPALEK,ANDMARIOSZEGEDY: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.75,arXiv:1011.3020]8
[40] [40] INÊSLYNCE ANDJOÃOP. MARQUES-SILVA: An overview of backtrack search satisfiability algorithms.Annals of Mathematics and Artificial Intelligence, 37(3):307–326, 2003. [doi:10.1023/A:1021264516079]2 THEORY OFCOMPUTING, Volume 14 (15), 2018, pp. 1–2422 QUANTUM-WALKSPEEDUP OFBACKTRACKINGALGORITHMS · Zbl 1010.68069
[41] [41] FRÉDÉRICMAGNIEZ, ASHWINNAYAK, PETERC. RICHTER,ANDMIKLOSSANTHA: On the hitting times of quantum versus random walks. Algorithmica, 63(1–2):91–116, 2012. Preliminary version inSODA’09. [doi:10.1007/s00453-011-9521-6,arXiv:0808.0084]19
[42] [42] FRÉDÉRICMAGNIEZ, ASHWINNAYAK, JÉRÉMIEROLAND,ANDMIKLOSSANTHA: Search via quantum walk. SIAM J. Comput., 40(1):142–164, 2011. Preliminary version inSTOC’07. [doi:10.1137/090745854,arXiv:quant-ph/0608026]5,9
[43] [43] SALVATOREMANDRÀ, GIANGIACOMOGUERRESCHI,ANDALÁNASPURU-GUZIK: Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems. New J. Phys., 18(7):073003, 2016. [doi:10.1088/1367-2630/18/7/073003,arXiv:1512.00859]7
[44] [44] JOÃOMARQUES-SILVA: The impact of branching heuristics in propositional satisfiability algorithms. In Proc. 9th Portuguese Conf. on Artificial Intelligence: Progress in Artificial Intelligence (EPIA’99), pp. 62–74. Springer, 1999. [doi:10.1007/3-540-48159-1_5]3
[45] [45] ASHLEYMONTANARO:Quantum walk speedup of backtracking algorithms,2015. [arXiv:1509.02374]5
[46] [46] DOMINICJ. MOYLETT, NOAHLINDEN,ANDASHLEYMONTANARO: Quantum speedup of the traveling-salesman problem for bounded-degree graphs. Phys. Rev. A, 95(3):032323:1–10, 2017. [doi:10.1103/PhysRevA.95.032323,arXiv:1612.06203]7
[47] [47] MICHAELA. NIELSEN ANDISAACL. CHUANG: Quantum Computation and Quantum Information. Cambridge University Press, 2000.16
[48] [48] RENATOPORTUGAL, RAQUELINEAZEVEDOM. SANTOS, T. D. FERNANDES,ANDDEMERSONN. GONÇALVES: The staggered quantum walk model. Quantum Information Processing, 15(1):85–101, 2016. [doi:10.1007/s11128-015-1149-z,arXiv:1505.04761]10
[49] [49] CLAUS-PETERSCHNORR ANDMARTINEUCHNER: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program., 66(1–3):181–199, 1994. Preliminary version inFCT’91. [doi:10.1007/BF01581144]7
[50] [50] UWESCHÖNING: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proc. 40th FOCS, pp. 410–414. IEEE Comp. Soc. Press, 1999. [doi:10.1109/SFFCS.1999.814612] 7
[51] [51] NEILSHENVI, JULIAKEMPE,ANDK. BIRGITTAWHALEY: Quantum random-walk search algorithm. Phys. Rev. A, 67(5):052307:1–11, 2003. [doi:10.1103/PhysRevA.67.052307,arXiv:quantph/0210064]5
[52] [52] LARRYSTOCKMEYER: On approximation algorithms for #P. SIAM J. Comput., 14(4):849–861, 1985. [doi:10.1137/0214060]6 · Zbl 0589.68031
[53] [53] MARIOSZEGEDY: Quantum speed-up of Markov chain based algorithms. In Proc. 45th FOCS, pp. 32–41. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.53,arXiv:quant-ph/0401053]5,9, 18 THEORY OFCOMPUTING, Volume 14 (15), 2018, pp. 1–2423 ASHLEYMONTANARO
[54] [54] AVATARTULSI: Faster quantum walk algorithm for the two dimensional spatial search. Phys. Rev. A, 78(1):012310:1–6, 2008. [doi:10.1103/PhysRevA.78.012310,arXiv:0801.0497]19
[55] [55] GUOMINGWANG: Efficient quantum algorithms for analyzing large sparse electrical networks. Quantum Inf. Comput., 17(11 & 12):987–1026, 2017. [arXiv:1311.1851]7,12
[56] [56] MINGYUXIAO ANDHIROSHINAGAMOCHI: An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. Algorithmica, 74(2):713–741, 2016. Preliminary version inTAMC’13. [doi:10.1007/s00453-015-9970-4,arXiv:1212.6831]7
[57] [57
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.