Backtracking is the general classical technique for exploiting problem structure in constraint satisfaction: explore a tree of partial assignments and prune the branches a predicate rules out. The question is whether an arbitrary backtracking algorithm — any predicate and any branching heuristic — can be sped up quantumly, rather than replaced by brute-force search over the whole assignment space.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Backtracking is the general classical technique for exploiting problem structure in constraint satisfaction: explore a tree of partial assignments and prune the branches a predicate rules out. The question is whether an arbitrary backtracking algorithm — any predicate and any branching heuristic — can be sped up quantumly, rather than replaced by brute-force search over the whole assignment space. The algorithm runs a discrete-time quantum walk on the tree that the classical backtracking algorithm implicitly defines, without knowing that tree's structure in advance. It is a special case of Belovs's correspondence between quantum walks and effective resistance, itself the quantum analogue of the classical link between random walks and electrical networks. Diffusion operators at each vertex mix it with its children and are defined purely from local calls to the predicate and the heuristic, so the walk never needs the tree laid out. Phase estimation on the walk operator then distinguishes the case where a marked vertex exists — the eigenvalue-one eigenvector stays close to the starting state — from the case where none does. Detection is extended to actually finding a solution by binary search down the tree, repeating detection on subtrees, and a separate eigenvector analysis gives a faster algorithm when the solution is promised unique.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Takes A rule naming the neighbours of any vertex, a rule saying whether a vertex is marked, somewhere to start — one named vertex, or a distribution over them — and the size bounds the schedule is computed from: the number of vertices, the depth, the maximum degree, or the size of the subsets a vertex stands for. Which of those a method needs is a property of the walk, not of the slot. Returns A marked vertex, with the evidence it is marked already in hand from the work stored on it — or the report that the graph holds none, at a stated failure probability.
How it works
The algorithm runs a discrete-time quantum walk on the tree that the classical backtracking algorithm implicitly defines, without knowing that tree's structure in advance. It is a special case of Belovs's correspondence between quantum walks and effective resistance, itself the quantum analogue of the classical link between random walks and electrical networks. Diffusion operators at each vertex mix it with its children and are defined purely from local calls to the predicate and the heuristic, so the walk never needs the tree laid out. Phase estimation on the walk operator then distinguishes the case where a marked vertex exists — the eigenvalue-one eigenvector stays close to the starting state — from the case where none does. Detection is extended to actually finding a solution by binary search down the tree, repeating detection on subtrees, and a separate eigenvector analysis gives a faster algorithm when the solution is promised unique. This record's speedup class, "Polynomial", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Stated by the primary source: "We usually think of T as being exponential in n; in this regime this complexity is a near-quadratic speedup over the classical algorithm.". Reported cost: O(√T · n^(3/2) · log n) evaluations of the predicate and the heuristic to find a solution or report none, where T is the number of vertices in the classical backtracking algorithm's tree and n the number of variables. Detecting whether a solution exists is cheaper, at O(√T · n) evaluations, and the promised-unique case costs O(√T · n · log³ n)..
Implementation
Unsupported
backtracking-quantum-walk-speedup.txt
ALGORITHM: Quantum walk speedup of backtracking
PROBLEM: Backtracking is the general classical technique for exploiting problem structure in constraint satisfaction: explore a tree of partial assignments and prune the branches a predicate rules out. The question is whether an arbitrary backtracking algorithm — any predicate and any branching heuristic — can be sped up quantumly, rather than replaced by brute-force search over the whole assignment space.
IDEA: The algorithm runs a discrete-time quantum walk on the tree that the classical backtracking algorithm implicitly defines, without knowing that tree's structure in advance. It is a special case of Belovs's correspondence between quantum walks and effective resistance, itself the quantum analogue of the classical link between random walks and electrical networks. Diffusion operators at each vertex mix it with its children and are defined purely from local calls to the predicate and the heuristic, so the walk never needs the tree laid out. Phase estimation on the walk operator then distinguishes the case where a marked vertex exists — the eigenvalue-one eigenvector stays close to the starting state — from the case where none does. Detection is extended to actually finding a solution by binary search down the tree, repeating detection on subtrees, and a separate eigenvector analysis gives a faster algorithm when the solution is promised unique.
REPORTED COST: O(√T · n^(3/2) · log n) evaluations of the predicate and the heuristic to find a solution or report none, where T is the number of vertices in the classical backtracking algorithm's tree and n the number of variables. Detecting whether a solution exists is cheaper, at O(√T · n) evaluations, and the promised-unique case costs O(√T · n · log³ n).
BASIS: abstract of arXiv:1509.02374: "Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(√T n^{3/2} log n) tests."; section 1.1, Theorem 1, for detection: "there is a quantum algorithm which, given T, evaluates P and h O(√T n log(1/δ)) times each, outputs true if there exists x such that P(x) is true, and outputs false otherwise"; section 1.1, Theorem 2, for the unique case: "there is a quantum algorithm which outputs x₀ using P and h O(√T n log³ n log(1/δ)) times each."
PRIMARY SOURCE: Ashley Montanaro (2015), Quantum walk speedup of backtracking algorithms — https://arxiv.org/abs/1509.02374
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Quantum walk with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Quantum walk speedup of backtracking algorithms2015 · Ashley Montanaro
Primary source, and the source of this record's cost claim. Theorem 1 in section 1.1 is detection and Theorem 2 is finding — different costs, and worth reading as two results rather than one. Section 2.1 carries the bounded-degree assumption and the doubling trick that removes the need to know the tree size in advance. Section 5 is where the author states the limit that matters most in practice: where classical backtracking finds a solution early without exploring the whole tree, this algorithm may not outperform it.