[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 N^1∕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]