Algorithms · Quantum walk
Quantum walk speedup of backtracking
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.
Attested & literatureUpdated
Open on the mapView frozen graph
A small worked example, computed in your browser. It is not a result from this record's papers.
A discrete-time quantum walk on a 4-cycle
One coin qubit, two position qubits (4 positions on a cycle), 3 steps starting at position 0.
Step 1 of 3 · Quantum walk step (4-cycle)
Probability of each outcome after this step
- 01150%
- 11050%
Flips the coin with a Hadamard, then shifts the position by +1 if the coin is |1⟩ or -1 mod 4 if the coin is |0⟩; with the coin in superposition, both shifts happen at once, entangling coin and position.
Probability leaves the outcome it was on and appears on 2 entirely different ones — not one outcome is populated both before and after. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
The same coin flip and shift, applied again.
Probability leaves all 2 outcomes it was on and appears on 4 entirely different ones — not one outcome is populated both before and after.
The same coin flip and shift, a third time.
Probability leaves all 4 outcomes it was on and appears on 2 entirely different ones — not one outcome is populated both before and after. The entanglement comes apart here: each qubit has a state of its own again.
Readout The position always reads 3, for either value of the coin: constructive interference on this small cycle concentrates the walk onto a single position after exactly 3 steps.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupStated 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 costO(√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).
- Papers1
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.
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 →
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)..
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 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- 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).
- Speedup class
- Polynomial (checked against the record's own primary paper, which states it)
- Complexity 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."
- Circuit
- Not supplied
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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.
Where this sits
This record is named by the layer graph at:
- Walk the backtracking tree itself Method
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.
Related entries
- Subset finding by quantum walk
Algorithms
- Grover unstructured search
Algorithms
- Element distinctness by quantum walk
Algorithms
References
- Quantum walk speedup of backtracking algorithms
Ashley Montanaro · 2015
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.