Quantum Backtracking in Qrisp Applied to Sudoku Problems

Quantum Backtracking in Qrisp Applied to Sudoku Problems

Background and implementation problem

Classical backtracking solves constraint satisfaction problems by exploring a tree of partial assignments and stopping the exploration of branches that already violate constraints. Montanaro's quantum backtracking algorithm replaces this traversal with a quantum walk and offers a near-quadratic theoretical speedup over classical backtracking under its algorithmic assumptions. The paper builds on this established algorithm, related work on quantum tree-size estimation and branch-and-bound, and earlier applications to lattice enumeration, constraint satisfaction, traveling-salesperson problems, and exact satisfiability. Its research problem is therefore the implementation of a known algorithm, rather than the invention of Sudoku solving or quantum backtracking.

The authors argue that the gap between the abstract quantum-walk formulation and executable circuits has prevented broad practical experimentation. Even simple classical predicates become difficult quantum software components because they must work coherently on superpositions, preserve reversibility, and release temporary qubits correctly. At the same time, the limited resources of simulators and quantum processors make inefficient implementations hard to test. The paper uses Qrisp's quantum variables, functions, automatic uncomputation, and dynamic qubit management to separate the general walk machinery from problem-specific predicates while retaining circuit compilation. The discussion of competing programming frameworks motivates this design, but the paper does not present a controlled comparison of programmer productivity or maintainability across frameworks.

Quantum walk and tree representation

The algorithm operates on basis states representing nodes of a rooted backtracking tree. A local diffusion operator acts on a parent and its children, leaving accepted nodes unchanged and preventing rejected nodes from leading to further exploration. For an ordinary unmarked node, the reflection is

$$D_x = I-2|\psi_x\rangle\langle\psi_x|, \qquad |\psi_x\rangle \propto |x\rangle+c\sum_{y:x\to y}|y\rangle,$$

where $c=\sqrt{n}$ at the root of a depth-$n$ tree and $c=1$ otherwise. Reflections over alternating levels form the walk step $R_B R_A$. Quantum phase estimation detects the eigenvalue $1$ associated with the presence of an accepted node, and recursive searches of subtrees recover a solution.

The central QuantumBacktrackingTree abstraction receives a maximum depth, a quantum variable describing the branch choices, and accept and reject functions. Each predicate must return a QuantumBool, preserve the tree state, uncompute its temporary variables, and never accept and reject the same node. The implementation represents a node as $|\mathrm{branch\_qa}\rangle|h\rangle$. The branch array stores the reversed path from the root, while a one-hot register stores the node's remaining height, with zero at a leaf. Height remains meaningful when the search switches to a subtree, unlike a distance measured from the original root. For a branch variable of $m$ qubits, unrejected internal nodes have $2^m$ possible children. The implementation includes rejected children as terminal nodes, trading a larger search space for a simpler step operator.

The psi_prep routine prepares the parent-and-children superposition using controlled $XX+YY$ rotations to move the one-hot height bit and controlled Hadamard gates to introduce branch choices. The diffuser then combines this state preparation with phase operations determined by the accept and reject predicates. To evaluate rejection of a child's parent, a lifting operation temporarily increments the height and, when necessary, removes the final branch entry into a temporary register before restoring it. For predicates such as the Sudoku checker that behave correctly on the relevant non-algorithmic states, the subspace_optimization option avoids the physical branch swaps and performs the height change through compiler-level wire reassignment. This optimization depends on a property of the supplied predicate; it is not unconditional for arbitrary problems.

Circuit engineering and Sudoku oracles

The implementation exploits the structure of reversible computations to reduce controlled-gate overhead. For a conjugated operation $W=UVU^\dagger$, its controlled version can control only $V$, since $U$ and $U^\dagger$ cancel when that central operation is inactive. The appendices apply this principle to the diffuser, swap operations, and equality checks, and explain specialized $XX+YY$ decompositions that use the one-hot register's restricted state space. Figure 9 illustrates a controlled-swap construction with a CX count of 8 instead of 18 for the generic construction shown alongside it. Phase-tolerant synthesis provides another reduction when a computation will later be uncomputed on the same input, allowing temporary extra phases to cancel. The abstract reports $6n+14$ CX gates for a single controlled binary-tree diffuser; this component-level statement must be distinguished from the complete Sudoku phase-estimation circuits, which also depend on the problem oracles and repeated walk applications.

For Sudoku, the authors map the board to a graph-coloring problem. Each cell is a vertex, and edges encode the requirement that values in a row, column, or subgrid differ. Only comparisons involving an initially empty cell need quantum evaluation, since given cells are classical data. Comparisons between two assigned quantum values use equality circuits, while comparisons between a quantum value and several classical clues are batched into a QuantumDictionary lookup synthesized as a quantum circuit. Temporary comparison results are combined and automatically uncomputed. Figure 10 illustrates the truth-table transformation used to synthesize a controlled classical-quantum lookup directly.

Partial assignments require additional care because an unassigned entry is stored as zero, which must not be mistaken for an actual assignment. The one-hot height register controls the comparisons involving the most recently assigned variable. For a quantum-quantum comparison, the controlling height bit corresponds to the later-assigned operand, so comparisons with fields that are still unassigned remain inactive. Figure 5 shows four cases using explicit assignment, height, control, and operand columns, including the false conflict that would arise from comparing two unused zero entries without this control. For $k$ empty cells, the authors use a tree of depth $k+1$ and define acceptance by height zero. The extra level ensures that conflicting complete assignments can be rejected before they reach the level accepted by this simple predicate.

Visual explanations and programming workflow

The paper includes an implemented visualize_statevector() method for inspecting small quantum-backtracking trees. Figures 2 and 3 depict nodes as circles connected by directed, branch-labeled edges, with the root near the center and the tree expanding outward. Green and purple encode the signs of nonzero node amplitudes. Figure 2 shows initialization at the root, while Figure 3 uses four snapshots to show successive applications of $R_A$ and $R_B$, the spread into deeper levels, and the lack of further exploration below the rejected node with path $[0]$. These views associate amplitudes with semantic search states rather than displaying only raw computational-basis bitstrings.

Figure 4 links this tree representation to the circuit representation by showing a depth-four tree before and after psi_prep, together with its controlled rotations and Hadamard gates. The supported workflow described in the paper is programmatic: initialize a node, call an operator, and request a statevector visualization. The article presents these outputs as explanations of the implementation and does not describe an interactive visual editor, a coordinated visual-analysis interface, or a user study of the graphics. The Sudoku grids in Figures 1 and 6 show the problem and its solution, and the line plot in Figure 7 and table in Figure 8 communicate resource measurements rather than interactive analysis features.

Experiments and findings

The authors compile and simulate $4\times4$ Sudoku instances with one through nine empty cells using IBM's matrix-product-state simulator. The benchmark family progressively removes cells labeled $a$ through $i$ in Figure 6. No classical Sudoku preprocessing is applied beyond the graph-coloring transformation. For solution detection, the measured circuits implement quantum phase estimation at precision $2^{-3}$ on $R_B R_A$ and are transpiled into the gate set $\{U_3,\mathrm{CX}\}$. The one-empty-cell circuit uses 15 qubits, 1,434 $U_3$ gates, 1,157 CX gates, and depth 1,396, with a reported simulator runtime of 5.51 seconds. The nine-empty-cell circuit uses 91 qubits, 13,074 $U_3$ gates, 10,901 CX gates, and depth 3,968, with a runtime of 97.58 seconds. Figure 7 shows the rising gate counts and depth, while Figure 8 provides the exact counts and runtimes. These are simulator and compilation measurements for detection circuits, not physical processor timings or total timings for every recursive step of the solver.

The separate solution-finding demonstration uses 10,000 shots and the same phase-estimation precision. It selects new subtree roots from measured node states for which the phase register is zero, then recursively continues the search. The authors report finding valid solutions for instances with up to nine empty cells and show a completed grid in Figure 6. They explain that using fewer ancillas can reduce qubit demand but increase gate counts and circuit depth, because ancillas support efficient multi-controlled Toffoli decompositions. The evidence establishes an executable implementation and small-instance functionality; it does not establish a practical runtime advantage over a classical Sudoku solver.

Contributions, limitations, and further work

The main contribution is a detailed, compilable realization of quantum backtracking with a reusable accept/reject interface, specialized circuit constructions, and a complete Sudoku oracle example. The implementation also demonstrates how high-level resource management and automatic uncomputation can support an algorithm with several interacting reversible components. The visualizations make the tree encoding and individual walk operations inspectable, but their explanatory value is illustrated through examples rather than empirically evaluated with users.

The reported experiments remain limited to small Sudoku instances and simulation. The authors state that larger circuits can be generated, but their selected cloud simulator at the time restricted execution to 100 qubits, which constrained the tested instances. That limit is a condition of their experimental setup, not a general limit of matrix-product-state simulation or a claim about current services. The paper provides no hardware execution, noise study, classical runtime comparison, or empirical benchmark across other constraint satisfaction problems. Its claim of a general implementation therefore rests on the interface and construction, while the demonstrated application is Sudoku.

The authors explicitly identify phase-estimation precision and measurement count as parameters that must be chosen carefully before pursuing practical advantage, referring to quantum tree-size estimation as relevant prior work. Their conclusion emphasizes coherence, reversibility, resource limits, and the need for better programming tools as continuing obstacles. Applying the interface to other constraint satisfaction problems is a stated broader opportunity, but those applications and a demonstrated end-to-end quantum advantage remain beyond the evaluation reported here.