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.

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.

1. Search graph with a marked set → A marked item, with its query billreflect at even depths, then at odd

   The walk lives on the space spanned by the vertices themselves — "unlike many discrete-time quantum walk algorithms, it does not use a separate 'coin' space" — and starts at $|r\rangle$. Vertices are split by parity of depth: $A$ is the set at even distance from the root, including the root, and $B$ the set at odd distance. At each vertex sits a diffusion operator $D_{x}$ acting on the span of $|x\rangle$ and its children. If $x$ is marked, $D_{x}$ is the identity — the walk stops there, which is what the eigenvalue-one eigenvector detects. Otherwise $D_{x} = I - 2|\psi_{x}\rangle\langle\psi_{x}|$ with $|\psi_{x}\rangle = \frac{1}{\sqrt{d_{x}}}\left(|x\rangle + \sum_{y : x \to y}|y\rangle\right)$, $d_{x}$ being the degree of $x$ in the undirected graph. The root is the exception and carries an extra weight: $|\psi_{r}\rangle = \frac{1}{\sqrt{1 + d_{r}n}}\left(|r\rangle + \sqrt{n}\sum_{y : r \to y}|y\rangle\right)$. One step is $R_{B}R_{A}$, where $R_{A} = \bigoplus_{x \in A}D_{x}$ and $R_{B} = |r\rangle\langle r| + \bigoplus_{x \in B}D_{x}$. assumption: the root is taken to be unmarked — "assume for simplicity in what follows that the root is promised not to be marked" — which is a convenience of the proof rather than a requirement of the method: a marked root is returned before the descent begins. assumption: every $D_{x}$ "can be implemented with only local knowledge, i.e. based only on whether $x$ is marked and the neighbourhood structure of $x$" — this is the property that lets the walk run on a tree nobody has laid out, and it is what the predicate and the branching heuristic supply. The paper offers a second reading of the same operator: "a quantum walk on the graph given by the edges of the tree, where we identify each vertex with the edge from its parent in the tree, and add an additional 'input' edge into the root" — though it never connects that added edge to the root's extra $\sqrt{n}$ weight, which appears here as a definition and later only inside the proof, in $|\varphi\rangle$ and $|\eta\rangle$. Detection alone is Belovs's result specialised to a tree; finding is Montanaro's own extension of it, and the two theorems differ by exactly the two factors it costs: $O(n)$ because "there are at most $O(n)$ repetitions to reach a leaf and $O(1)$ subtrees are checked at each repetition", and a further $O(\log n)$ because the descent makes $O(n^{2})$ uses of the detector in all, so each must be run at failure probability $O(1/n^{2})$ — "an additional time factor of $O(\log n)$ per use". $O(\sqrt{Tn}\log(1/\delta))$ times $n\log n$ is $O(\sqrt{T}n^{3/2}\log n\log(1/\delta))$, which is Theorem 2.

   assumption

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.

• 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

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

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

• Qrisp's QuantumBacktrackingTree, applied to Sudoku

  • Quantum Backtracking in Qrisp Applied to Sudoku Problems

    Raphael Seidel, René Zander, Matic Petrič, Niklas Steinmann, David Q. Liu, Nikolay Tcholtchev, Manfred Hauswirth · 2024

  About

  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.

  Methods

  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.

  Data

  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.

  Code

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

  Results

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

• Quantum walk speedup of backtracking · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  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.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

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