Quantum-Walk Speedup of Backtracking Algorithms
Theory of Computing, Volume 14(15), pp. 1-24, 2018
Bibliography with links to cited articles
[1] Scott Aaronson and Andris Ambainis: Quantum search of spatial regions. Theory of Computing, 1(4):47–79, 2005. Preliminary version in FOCS’03. [doi:10.4086/toc.2005.v001a004, arXiv:quant-ph/0303041]
[2] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe: Post-quantum key exchange – a new hope. In Proc. 25th USENIX Security Symp. (USENIX Security’16), pp. 327–343. USENIX Association, 2016. Available at IACR.
[3] Andris Ambainis: Quantum search algorithms. ACM SIGACT News, 35(2):22–35, 2004. [doi:10.1145/992287.992296, arXiv:quant-ph/0504012]
[4] Andris Ambainis: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210–239, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447311, arXiv:quant-ph/0311001]
[5] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang: 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 in FOCS’07. [doi:10.1137/080712167, arXiv:quant-ph/0703015]
[6] Andris Ambainis and Ronald de Wolf: Average-case quantum query complexity. J. Phys. A: Math. Gen., 34(35):6741–6754, 2001. Preliminary version in STACS’00. [doi:10.1088/0305-4470/34/35/302, arXiv:quant-ph/9904079]
[7] Andris Ambainis and Martins Kokainis: 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]
[8] Ola Angelsmark, Vilhelm Dahllöf, and Peter Jonsson: 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]
[9] Peter van Beek: Backtracking search algorithms. In Handbook of Constraint Programming. Elsevier, 2006. [doi:10.1016/S1574-6526(06)80008-8]
[10] Aleksandrs Belovs: Quantum walks and electric networks, 2013. [arXiv:1302.3143]
[11] Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez: 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]
[12] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [doi:10.1137/S0097539796300933, arXiv:quant-ph/9701001]
[13] Ethan Bernstein and Umesh V. Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]
[14] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. 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]
[15] Chris Cade, Ashley Montanaro, and Aleksandrs Belovs: 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] Nicolas J. Cerf, Lov K. Grover, and Colin P. 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]
[17] Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari: The electrical resistance of a graph captures its commute and cover times. Comput. Complexity, 6(4):312–340, 1996. Preliminary version in STOC’89. [doi:10.1007/BF01270385]
[18] Yuanmi Chen and Phong Q. 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]
[19] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. 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]
[20] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca: Quantum algorithms revisited. Proc. Royal Soc. A, 454(1969):339–354, 1998. [doi:10.1098/rspa.1998.0164, arXiv:quant-ph/9708016]
[21] Evgeny Dantsin, Vladik Kreinovich, and Alexander Wolpert: On quantum versions of record-breaking algorithms for SAT. ACM SIGACT News, 36(4):103–108, 2005. [doi:10.1145/1107523.1107524]
[22] Martin Davis, George Logemann, and Donald Loveland: A machine program for theorem-proving. Commun. ACM, 5(7):394–397, 1962. [doi:10.1145/368273.368557]
[23] Martin Davis and Hilary Putnam: A computing procedure for quantification theory. J. ACM, 7(3):201–215, 1960. [doi:10.1145/321033.321034]
[24] Rafaël del Pino, Vadim Lyubashevsky, and David Pointcheval: 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/978-3-319-44618-9_15]
[25] Niklas Eén and Niklas Sö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]
[26] Edward Farhi, Jeffery Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda: 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]
[27] Edward Farhi, Jeffery Goldstone, Sam Gutmann, and Michael Sipser: Quantum computation by adiabatic evolution. Technical report, MIT, 2000. [arXiv:quant-ph/0001106]
[28] Edward Farhi and Sam Gutmann: Quantum computation and decision trees. Phys. Rev. A, 58(2):915–928, 1998. [doi:10.1103/PhysRevA.58.915, arXiv:quant-ph/9706062]
[29] Eugene C. Freuder and Alan K. Mackworth: Constraint satisfaction: An emerging paradigm. In Handbook of Constraint Programming, pp. 13–27. Elsevier, 2006. [doi:10.1016/S1574-6526(06)80006-4]
[30] Martin Fü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-3-540-78773-0_67]
[31] Nicolas Gama, Phong Q. Nguyen, and Oded Regev: 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]
[32] Carla P. Gomes, Henry Kautz, Ashish Sabharwal, and Bart Selman: Satisfiability solvers. In Handbook of Knowledge Representation, pp. 89–134. Elsevier, 2008. [doi:10.1016/S1574-6526(07)03002-7]
[33] Lov K. 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]
[34] Peter Høyer and Mojtaba Komeili: 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]
[35] Stacey Jeffery and Shelby Kimmel: NAND-trees, average choice complexity, and effective resistance, 2015. [arXiv:1511.02235]
[36] Alexei Kitaev: Quantum measurements and the abelian stabilizer problem, 1996. [arXiv:quant-ph/9511026]
[37] Donald E. Knuth: Estimating the efficiency of backtrack programs. Mathematics of Computation, 29(129), 1975. [doi:10.1090/S0025-5718-1975-0373371-6]
[38] Hari Krovi, Frédéric Magniez, Maris Ozols, and Jérémie Roland: Quantum walks can find a marked element on any graph. Algorithmica, 74(2):851–907, 2016. Preliminary version in ICALP’10. [doi:10.1007/s00453-015-9979-8, arXiv:1002.2419]
[39] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy: 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]
[40] Inês Lynce and João P. 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]
[41] Frédéric Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha: On the hitting times of quantum versus random walks. Algorithmica, 63(1–2):91–116, 2012. Preliminary version in SODA’09. [doi:10.1007/s00453-011-9521-6, arXiv:0808.0084]
[42] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha: Search via quantum walk. SIAM J. Comput., 40(1):142–164, 2011. Preliminary version in STOC’07. [doi:10.1137/090745854, arXiv:quant-ph/0608026]
[43] Salvatore Mandrà, Gian Giacomo Guerreschi, and Alán Aspuru-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]
[44] João Marques-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]
[45] Ashley Montanaro: Quantum walk speedup of backtracking algorithms, 2015. [arXiv:1509.02374]
[46] Dominic J. Moylett, Noah Linden, and Ashley Montanaro: 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]
[47] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.
[48] Renato Portugal, Raqueline Azevedo M. Santos, T. D. Fernandes, and Demerson N. 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]
[49] Claus-Peter Schnorr and Martin Euchner: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program., 66(1–3):181–199, 1994. Preliminary version in FCT’91. [doi:10.1007/BF01581144]
[50] Uwe Schö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]
[51] Neil Shenvi, Julia Kempe, and K. Birgitta Whaley: Quantum random-walk search algorithm. Phys. Rev. A, 67(5):052307:1–11, 2003. [doi:10.1103/PhysRevA.67.052307, arXiv:quant-ph/0210064]
[52] Larry Stockmeyer: On approximation algorithms for #P. SIAM J. Comput., 14(4):849–861, 1985. [doi:10.1137/0214060]
[53] Mario Szegedy: 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]
[54] Avatar Tulsi: 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]
[55] Guoming Wang: Efficient quantum algorithms for analyzing large sparse electrical networks. Quantum Inf. Comput., 17(11 & 12):987–1026, 2017. [arXiv:1311.1851]
[56] Mingyu Xiao and Hiroshi Nagamochi: 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 in TAMC’13. [doi:10.1007/s00453-015-9970-4, arXiv:1212.6831]
[57] Mingyu Xiao and Hiroshi Nagamochi: An improved exact algorithm for TSP in graphs of maximum degree 4. Theory Comput. Syst., 58(2):241–272, 2016. Preliminary version in COCOON’12. [doi:10.1007/s00224-015-9612-x]