Fetching the paper…
Reading the bibliography…
We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs).
A computing procedure for quantification theory
M. Davis and H. Putnam · 1960
Earlier work this paper cites.
A machine program for theorem proving
M. Davis, G. Logemann, and D. Loveland · 1962
Earlier work this paper cites.
Estimating the efficiency of backtrack programs
D. Knuth · 1975
Earlier work this paper cites.
An average time analysis of backtracking
C. Brown and P. Purdom, Jr · 1981
Earlier work this paper cites.
On approximation algorithms for #P
L. Stockmeyer · 1985
Earlier work this paper cites.
The hardest constraint problems: A double phase transition
T. Hogg and C. Williams · 1994
Earlier work this paper cites.
Quantum measurements and the abelian stabilizer problem, 1995
A. Kitaev · 1995
Earlier work this paper cites.
Generating hard satisfiability problems
B. Selman, D. Mitchell, and H. Levesque · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
The electrical resistance of a graph captures its commute and cover times
A. Chandra, P. Raghavan, W. Ruzzo, R. Smolensky, and P. Tiwari · 1997
Earlier work this paper cites.
Quantum mechanics helps in searching for a needle in a haystack
L. Grover · 1997
Earlier work this paper cites.
Backtracking and random constraint satisfaction
P. Purdom · 1997
Earlier work this paper cites.
Statistical analysis of backtracking on inconsistent CSPs
I. Rish and D. Frost · 1997
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
Earlier work this paper cites.
Quantum computation and decision trees
E. Farhi and S. Gutmann · 1998
Earlier work this paper cites.
A probabilistic algorithm for k-SAT and constraint satisfaction problems
U. Schöning · 1999
Earlier work this paper cites.
Nested quantum search and structured problems
N. Cerf, L. Grover, and C. Williams · 2000
Earlier work this paper cites.
Quantum computation by adiabatic evolution
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 2000
Cited alongside, same era.
Average-case quantum query complexity
A. Ambainis and R. de Wolf · 2001
Cited alongside, same era.
Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms
S. Cocco and R. Monasson · 2001
Cited alongside, same era.
Trajectories in phase diagrams, growth processes, and computational complexity: how search algorithms solve the 3-satisfiability problem
S. Cocco and R. Monasson · 2001
Cited alongside, same era.
A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda · 2001
Cited alongside, same era.
Finite domain constraint satisfaction using quantum computation
Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
S. Cocco and R. Monasson · 2005
Later among the works it cites.
On quantum versions of record-breaking algorithms for SAT
E. Dantsin, V. Kreinovich, and A. Wolpert · 2005
Later among the works it cites.
Backtracking search algorithms
P. van Beek · 2006
Later among the works it cites.
Constraint satisfaction: an emerging paradigm
E. Freuder and A. Mackworth · 2006
Later among the works it cites.
Randomness and structure
C. Gomes and T. Walsh · 2006
Later among the works it cites.
Solving NP-complete problems with quantum search
M. Fürer · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
O. Angelsmark, V. Dahllöf, and P. Jonsson · 2002
Cited alongside, same era.
The efficiency of resolution and Davis–Putnam procedures
P. Beame, R. Karp, T. Pitassi, and M. Saks · 2002
Cited alongside, same era.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random satisfiability problem, and its application to stop-and-restart solutions
S. Cocco and R. Monasson · 2002
Cited alongside, same era.
Exponential algorithmic speedup by a quantum walk
A. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. Spielman · 2003
Cited alongside, same era.
An extensible SAT-solver
N. Eén and N. Sörensson · 2003
Cited alongside, same era.
An overview of backtrack search satisfiability algorithms
I. Lynce and J. P. Marques-Silva · 2003
Cited alongside, same era.
Satisfiability solvers
C. Gomes, H. Krautz, A. Sabharwal, and B. Selman · 2008
Later among the works it cites.
Faster quantum walk algorithm for the two dimensional spatial search
A. Tulsi · 2008
Later among the works it cites.
Any AND-OR formula of size n n can be evaluated in time n 1 / 2 + o ( 1 ) n^{1/2+o(1)} on a quantum computer
A. Ambainis, A. Childs, B. Reichardt, R. Špalek, and S. Zhang · 2010
Later among the works it cites.
A. Montanaro · 2010
Later among the works it cites.
Quantum query complexity of state conversion
T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy · 2011
Later among the works it cites.
Search via quantum walk
F. Magniez, A. Nayak, J. Roland, and M. Santha · 2011
Later among the works it cites.
On the hitting times of quantum versus random walks
F. Magniez, A. Nayak, P. Richter, and M. Santha · 2012
Later among the works it cites.
Quantum walks and electric networks, 2013
A. Belovs · 2013
Later among the works it cites.
Time-efficient quantum walks for 3-distinctness
A. Belovs, A. Childs, S. Jeffery, R. Kothari, and F. Magniez · 2013
Later among the works it cites.
Quantum algorithms for approximating the effective resistances in electrical networks, 2013
G. Wang · 2013
Later among the works it cites.
Improving exhaustive search implies superpolynomial lower bounds
R. Williams · 2013
Later among the works it cites.
Quantum walks can find a marked element on any graph
H. Krovi, F. Magniez, M. Ozols, and J. Roland · 2015
Closest in time.