Walk the backtracking tree itself

What it fills

• Walk a graph to the vertex you want

  When candidates sit on a graph and the work done at one vertex is still worth something at its neighbour, walk the graph instead of sampling it — and pay per move rather than per candidate.

When it applies

What the algorithm needs is what a backtracking algorithm already has: a predicate $P : D \to \{\text{true}, \text{false}, \text{indeterminate}\}$ over partial assignments $D = ([d] \cup \{*\})^{n}$ and a heuristic $h : D \to \{1, \ldots, n\}$ "which returns the next index to branch on from a given partial assignment". It does not need the tree: "we do not necessarily know the structure of $T$ in advance", only the distance of a vertex from the root. That is the break with the earlier walk-search literature and the paper states it as one — "in prior work it is usually assumed that the input graph is known in advance, and moreover that the initial state of the quantum walk is the stationary distribution of the corresponding random walk". An upper bound on the number of vertices $T$ is used but need not be known: guesses are doubled from $T = 1$, and a returned vertex is checked before the algorithm terminates, because "if our guess for $T$ is too low, the correctness proof of Algorithm 2 no longer holds". Local domain size $d = O(1)$ is assumed throughout, and for the finding half so is bounded degree.

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• Estimate the eigenphase of a unitary

  Given a circuit whose controlled powers you can apply, and a routine preparing a state with non-negligible overlap on one of its eigenvectors, return that eigenvector's phase as a number with an error bar. The phase is read out of an ancilla, never out of the system register — the system is only ever the thing the controlled powers act on.

  The detector asks phase estimation one question — is the eigenvalue exactly $1$ — and everything it costs is in the precision that question is asked at. Algorithm 2 applies "phase estimation to the operator $R_{B}R_{A}$ with precision $\beta/\sqrt{Tn}$" and accepts when the eigenvalue is $1$, repeating $K = \lceil\gamma\log(1/\delta)\rceil$ times and answering "marked vertex exists" when at least $3K/8$ of the runs accept. So the state prepared for it is the root $|r\rangle$ rather than an eigenvector, and what the estimate reads is how close $|r\rangle$ is to an eigenvector of eigenvalue one: when a marked vertex exists, $|r\rangle$ "is quite close to (a normalised version of) an eigenvector $|\varphi\rangle$ of $R_{B}R_{A}$ with eigenvalue 1" and phase estimation "returns the eigenvalue 1 with probability at least 1/2"; when none exists the same estimate "returns the eigenvalue 1 with probability at most 1/4". The $3K/8$ threshold sits between those two numbers, which is what makes counting acceptances an answer. assumption: the precision $\beta/\sqrt{Tn}$ is what fixes the query count, since phase estimation to precision $\chi$ costs $O(1/\chi)$ controlled applications of the operator — which is where $O(\sqrt{Tn})$ comes from and why a tighter bound on $T$ is worth having. The whole subroutine is used $O(\sqrt{Tn}\log(1/\delta))$ times, and the paper attributes the result it is a special case of to Belovs. assumption: $T$ must be a real upper bound on the vertex count, or "the correctness proof of Algorithm 2 no longer holds" and the detector can report a marked vertex where there is none — which is why the caller checks the vertex it is finally handed.

  assumption

Example

given  a predicate P over partial assignments, returning true, false or
           indeterminate                                        (Alg. 1)
       a heuristic h returning the next index to branch on       (Alg. 1)
       n, the depth bound; a guess T for the number of vertices

# the tree is never built and its structure is not known in advance. All that
# is needed of a vertex is its neighbours and its distance from the root

detect(subtree, T, delta):                                       (Alg. 2)
    repeat K = ceil(gamma log(1/delta)) times:
        run phase estimation on R_B R_A with precision beta/sqrt(T n)
        accept if the eigenvalue is 1
    return 'marked vertex exists' if at least 3K/8 accepted, else 'none'

for T = 1, 2, 4, 8, ... doubling until an answer survives its check:
    if detect(whole tree, T, delta) says none: return 'not found'

# returning here on the FIRST negative, at T = 1, is deliberate and is the one
# place the two directions are not symmetric. A marked vertex is detected with
# probability at least 1/2 whether or not the guess for T is large enough, so a
# negative answer is trustworthy at any T; only a positive one is not
    x = root
    while x is not marked:
        y = the first child of x whose subtree detect() says holds one
        if there is no such child: break
        x = y
    if x is marked: return x

# the break is not defensive tidiness. A detection above can be a false
# positive when T is guessed too low, and then no child confirms anything;
# leaving the descent is what lets the doubling loop resume

# T is left unchanged when the detector is applied to a subtree. The tree can
# be very unbalanced, so a subtree may still hold most of the vertices

# the doubling is why no bound on T has to be known in advance. A guess that is
# too low can make the detector claim a solution where there is none, which is
# exactly what checking the returned vertex catches

# there are O(n) steps down to a leaf and O(1) subtrees tested at each. That
# is one of the two factors between detecting and finding; the other is a
# log n, because O(n^2) detector calls in all must each run at failure
# probability O(1/n^2)

# do not use this listing for the unique-solution case. That bound comes from
# an eigenvector argument on the walk, not from this binary search

Cost, as the source states it

Detection and finding are priced separately and the gap between them is the cost of turning one into the other. Theorem 1 evaluates $P$ and $h$ $O(\sqrt{Tn}\log(1/\delta))$ times each to say whether a solution exists; Theorem 2 evaluates them $O(\sqrt{T}n^{3/2}\log n \log(1/\delta))$ times each to "output $x$ such that $P(x)$ is true, or 'not found' if no such $x$ exists". A promise that the solution is unique buys most of that back — $O(\sqrt{T}n\log^{3} n \log(1/\delta))$ — through an eigenvector argument rather than through the binary search. Finding all $k$ solutions costs $O(k\sqrt{T}n^{3/2}\log n\log(k/\delta))$. The speedup claim is scoped, in the paper's own sentence: "we usually think of $T$ as being exponential in $n$; in this regime this complexity is a near-quadratic speedup over the classical algorithm." The bound is instance-dependent, and the paper draws the consequence: "for instances on which the classical algorithm runs quickly, the quantum algorithm also runs quickly." Space is $\mathrm{poly}(n)$ with $O(1)$ auxiliary operations per use of $P$ and $h$.

Implementations

• Qrisp's QuantumBacktrackingTree, applied to Sudoku

  • Quantum Backtracking in Qrisp Applied to Sudoku Problems

  Montanaro's paper leaves the circuit-level construction unspecified, and this paper says so directly: "the author refrains from providing any specific details regarding its implementation" and "there is little to no literature on how such an implementation ... could look like." The authors, based at Fraunhofer FOKUS and building the open-source Qrisp framework, close that gap by deriving a gate-level diffuser for an arbitrary backtracking instance and then applying it to solving 4x4 Sudoku puzzles, reduced to a graph-colouring constraint satisfaction problem.

  The step operator follows the paper's two-part construction of $D_x$ (paper Eq. 4-8; the code's module docstring derives the same construction independently, in its own notation). An accepted node's diffuser is rewritten as $D_x = U_x(1 - (1+(-1)^{accept(x)})|x\rangle\langle x|)U_x^{-1}$ for a state-preparation unitary $U_x$, so that in a computational-basis node encoding the middle term becomes a controlled Z-gate on $accept(x)$, flanked by $U_x$ and its inverse -- the paper's $O_1(x)$. A rejected node must instead act as $D_x = -I$ so the walk never descends past it, which needs a second controlled Z-gate, this one on the parent's reject flag lifted onto the child subspace -- the paper's $O_2(x)$, giving $D_x = U_x O_1(x) O_2(x) U_x^{-1}$ overall. A node is encoded as a one-hot height register (distance from a leaf, the opposite end from the paper's distance-from-root convention) together with the reversed root-to-node path; the caller supplies a maximum depth, a branch-variable type, and accept/reject predicates returning quantum booleans, in place of the paper's predicate $P$. The two diffusers are composed as $R_BR_A$, and quantum phase estimation on that operator reports the same two thresholds as the paper's detector: above 3/8 acceptance the tree is reported to hold a solution, below 1/4 it is reported empty, and in between the precision is insufficient. Finding a solution differs from the paper's descent in one respect: rather than testing each child subtree for a marked vertex in turn, the code measures the whole tree once, sorts every branch whose phase-estimation outcome is consistent with eigenvalue 1 by height, and recurses into each candidate in that order -- the code's own comment calls this a heuristic that "proved to be the case in every situation we tested," not a proven substitute for the paper's descent. The paper's user-supplied branching heuristic is not implemented: branch order is fixed by the node encoding.

  The benchmark inputs are 4x4 Sudoku boards, reduced to a constraint graph by connecting each empty cell to the other cells in its row, column and 2x2 subgrid, and separating the resulting comparisons into quantum-quantum and classical-quantum cases; the benchmarked instances leave up to 9 of the 16 cells empty.

  `qrisp.quantum_backtracking.QuantumBacktrackingTree`, in `src/qrisp/algorithms/quantum_backtracking/backtracking_tree.py` of github.com/eclipse-qrisp/Qrisp (Eclipse Public License 2.0) -- the repository the paper names as "the source code." Attributes `h` and `branch_qa`; methods `qstep_diffuser`, `quantum_step` and `estimate_phase` on the class, plus the module-level `find_solution` function. The Sudoku accept/reject oracles and the graph-reduction helpers, including `sudoku_to_graph` and `extract_comparisons`, ship in the same repository's `tests/algorithms_tests/test_sudoku.py` and `documentation/source/general/tutorial/Sudoku.ipynb` -- that notebook is the paper's own cited source, not a separate repository. A later repository under the GitHub handle renezander90 (matching co-author René Zander), created in November 2025 -- more than a year after this paper's final arXiv revision -- reproduces the same oracle functions under the title "Examples and Benchmarking for Sudoku paper"; it postdates the paper's own reported experiments and is not their source.

  "For a single controlled diffuser of a binary backtracking tree with depth $n$, our implementation requires only $6n+14$ CX gates" (abstract). Experiments ran on the cloud-based IBM `simulator_mps` matrix-product-state simulator, using 10000 shots per phase-estimation circuit at precision $2^{-3}$; the paper reports detecting and finding solutions for 4x4 Sudoku instances with up to 9 empty cells, with the 9-empty-cell circuit needing 91 qubits and reaching circuit depth 3968 (Section 5, Figure 1) -- stated by the authors to be, to their knowledge, the first compilable implementation of Montanaro's algorithm at this generality.

What it needs

Every step this method names is listed under Requires above. It walks its own span in one hop and calls out to the rest — that is a fact about the recorded route, not a claim that the span is simple.

Other ways to fill the same slot

Different approaches

• Walk over subsets that remember their queries

  Make each vertex a subset of the input together with the values already queried for it, so that stepping to a neighbouring subset costs one query rather than a fresh batch. Grover diffusion over which element to add or remove supplies the moves, and a phase flip on subsets that already contain the answer supplies the direction.

In the Atlas

• 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.

Sources

• Quantum walk speedup of backtracking algorithms↗Ashley Montanaro · 2015theory yes · simulation ? · hardware no