Pith. sign in

REVIEW 3 major objections 5 minor 27 references

Practical implementation of a quantum backtracking algorithm

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper constructs a space-efficient implementation of quantum backtracking for constraint satisfaction, using O(n log d) data qubits and an O(log m)-qubit predicate, and tests it on graph coloring.

desk verdict The predicate circuit collapses 'valid partial' and 'solution', so the implementation as written does not implement Montanaro's walk; the space-efficient counter is a real contribution, but the paper needs a fix. read the letter →

arxiv 1908.11291 v1 pith:OOLVUCIG submitted 2019-08-29 cs.DM cs.ETquant-ph

Simon Martiel , Maxime Remaud This is my paper · ORCID
classification cs.DMcs.ETquant-ph MSC 68Q1281P68
keywords quantumbacktrackingconstraintsatisfactionproblemwalkspace-efficientcircuitgraphcoloringSATvariableorderingheuristiccounter
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Quantum backtracking algorithms have promised speedups for constraint satisfaction, but earlier implementations assumed huge qubit budgets and optimized depth. This paper asks how few qubits the walk-based quantum backtracking method can use, and answers: with a static variable ordering, data qubits cost $O(n\log d)$ and the predicate can be checked with an extra $O(\log m)$ qubits by counting violated constraints in a logarithmic counter. The authors give explicit reversible circuits for graph coloring and SAT, report simulation probabilities for the phase-estimation detection step, and argue that a static ordering is a sensible space saver in the parameter range where the algorithm might first run. If the resource bound holds, a CSP with $n$ variables, domain size $d$, and $m$ constraints becomes implementable in a total of $O(n\log d + \log n + \log m)$ qubits, which is what makes small instances classically emulable.

What carries the argument

The load-bearing object is the pair of walk operators $R_A$ and $R_B$ from [22], now realized with explicit reversible circuitry. The new constructions are: an index register $\ell$ that marks how many variables are assigned; data registers storing each value in $\lceil\log(d+1)\rceil$ qubits; a comparison rule using $M_i = \max_{x_i \in Y_i} i - 1$ so a constraint is checked only when $M_i \le \ell$; and a quantum counter of $\lceil\log(m+1)\rceil$ qubits that accumulates violated constraints and is reversed after use. The counter is what removes the $m+1$-qubit predicate overhead, and the static ordering is what removes the $O(n\log n)$ storage needed for choosing the next variable dynamically.

What would settle it

Implement the published circuits on a simulator for growing $n$ with fixed $d$ and count the width of the data registers; if the width grows like $n\log n$ rather than $n\log d$ even under a static ordering, the central claim is wrong. The comparison rule and the counter circuit are specified concretely enough that this qubit count can be checked directly.

Watch

Extended reading notes

Core claim

The central discovery is a space-efficient circuit family for the walk operators used in the algorithm of [22]. With a static variable ordering, a partial assignment is encoded as an index $\ell$ plus $n$ registers of width $\lceil\log(d+1)\rceil$, so the data register costs $O(n\log d)$. The predicate is built around a quantum counter of width $\lceil\log(m+1)\rceil$: each violated constraint increments the counter, and the final value zero marks a solution or a valid partial assignment. A modular subtraction-and-overflow comparator decides, from $\ell$ and the classical values $M_i$, whether a constraint must be checked, so deeper nodes check fewer constraints. The paper instantiates the generic checkers for graph coloring edges and for SAT clauses, describes a parallel version of the predicate, and reports simulation probabilities for detecting eigenvalues on small coloring trees.

Load-bearing premise

The whole qubit budget depends on fixing the variable order before the search starts, so a partial assignment is always the first $\ell+1$ variables; with a dynamic order, storing which variables remain would add $O(n\log n)$ qubits and the $O(n\log d)$ data bound falls.

Editorial extensions

If this is right

  • A CSP with $n$ variables, domain size $d$, and $m$ constraints fits in $O(n\log d + \log n + \log m)$ qubits, so quantum backtracking can be simulated classically on small instances.
  • The predicate needs only $\lceil\log(m+1)\rceil$ counter qubits rather than $m+1$ work qubits, which removes the dominant linear space overhead of a naive predicate.
  • Because only constraints whose maximum variable index is below the current level are checked, working deeper in the backtracking tree consumes fewer gates and can reuse the same comparison and counter circuitry.
  • Graph coloring and SAT get explicit reversible implementations, so the savings apply directly to two standard NP-hard problems.
  • For instances around the size where a graph could be colored in a day, static variable ordering is competitive because no dynamic heuristic has been shown to shrink the tree enough to pay for its $O(n\log n)$ overhead.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A useful next step is to search for a dynamic variable ordering that provably beats the break-even ratio $c_T/c_{T'} \ge 1 + d_h/d_R$; if such a heuristic exists, the same circuits would run with an extra $O(n\log n)$ data register, but the practical question of whether static ordering is sufficient would then hinge on measured tree sizes rather than on the absence of a proof.
  • The parallel predicate described in the paper points to a depth–space tradeoff: splitting the $m$ constraints into $k$ groups and fanning out the assignment in $O(\log k)$ depth divides predicate depth by $k$ at a cost of $O(kn\log n)$ qubits, so on hardware with many qubits one could trade the space saving back for speed.
  • For SAT, the two-qubit encoding of boolean values means classical order-selection heuristics can be imported without designing a reversible heuristic circuit; this suggests a practical recipe for quantum backtracking solvers, but the recipe's performance still hinges on the size of the original backtracking tree.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a space-efficient implementation of Montanaro's quantum backtracking algorithm for constraint satisfaction problems (CSPs). The main technical claims are that, using a static variable ordering, the data can be stored in O(n log d) qubits and that the predicate can be implemented with an additional register of O(log m) qubits via a quantum counter. The authors give circuits for graph coloring and SAT, present small simulation results for graph coloring, and discuss the trade-off between static and dynamic variable ordering heuristics.

Significance. If correct, the space-efficient encoding would be a useful step toward emulating Montanaro's algorithm on small instances, which is a practical goal given current hardware constraints. The basic accounting of the data register is transparent, and the paper deserves credit for benchmarking against the external acceptance threshold of [22] without introducing fitted parameters. However, the central predicate implementation does not faithfully implement the three-valued predicate required by Montanaro's walk, and therefore the claimed resource bounds are not currently supported by a correct circuit. The space bound itself is plausible, but the main algorithmic construction needs substantial repair before the paper can be accepted.

major comments (3)
  1. [§4.1, Fig. 3c, Algorithm 4 step 3] The circuit in Fig. 3c produces a single Boolean bit p that is 1 whenever the partial assignment is 'not invalid', but Algorithm 4 step 3 routes the case 'P(x) is true' to step 8, which is the identity branch. In Montanaro's algorithm, D_x must be the identity only for complete solutions, while valid partial nodes must receive a diffusion over their children. As written, every valid partial node is treated as a solution: for ℓ=0 the root has p=1 for any CSP without unary constraints, so R_B R_A is the identity and Algorithm 2 accepts with probability 1 even for unsatisfiable instances. A completeness condition such as p_solution = p_not_false ∧ (ℓ=n) is missing, and without it the circuits do not implement the diffusion operators on which the walk is based.
  2. [§4.1, Fig. 3b] The comparison-overflow circuit is asserted rather than proved. The text says that subtracting or adding (M_i−M_{i−1}) modulo 2^{ν+1} and detecting overflow flips |a> iff M_i > ℓ, but it does not specify a reversible circuit for the case where the increment is negative, nor does it prove that the modular arithmetic behaves correctly when combined with the value in |ℓ−M_{i−1}>. Since this circuit underpins the claimed O(log m) predicate register, the construction is not yet established.
  3. [§5, Tables 6c and 7c] Because of the predicate flaw in Algorithm 4, the simulated acceptance probabilities in Tables 6c and 7c do not demonstrate that the implementation reproduces Montanaro's algorithm; they only show the behavior of the modified identity walk. The simulation results should be regenerated after correcting the predicate, and ideally should be checked on an unsatisfiable instance where the algorithm is expected to reject with high probability.
minor comments (5)
  1. [§2] The symbol D is used both for the domain [1,d] and for the extended domain D∪{∗}; this is confusing and should be renamed in one of the two roles.
  2. [§4 and Algorithm 4] The text alternates between saying that the index ℓ indicates that the first ℓ+1 variables are assigned and saying that the first ℓ variables are assigned; for example, Section 4 uses the former while Algorithm 4's Require line uses the latter. This inconsistency must be fixed because the comparison and diffusion logic depend on the exact level index.
  3. [§3] The derivation of the condition c_T/c_T' ≥ 1 + d_h/d_R is given without stating the implicit assumption that all other cost contributions scale identically; writing out the full equation would make the comparison easier to verify.
  4. [References] Reference [23] is cited as a script for computing the algorithm's complexity, but no URL, version, or retrieval date is given; a stable reference would be helpful.
  5. [Throughout] There are several minor typos (e.g., 'is sufficient' instead of 'it is sufficient') and the figures in the appendix are captioned only in general terms; adding explanatory text for the control logic in Figs. 9 and 10 would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the resource bounds are direct constructions and the benchmarks are external.

full rationale

No circular step is present. The paper's central claim is an explicit circuit construction: the O(n log d) data-qubit count follows directly from encoding each of n variables as one of d values or the unassigned symbol * in ceil(log(d+1)) qubits (Sections 2 and 4), and the O(log m) predicate register follows from the quantum counter that counts up to m violated constraints and tests whether the count is zero (Section 4.1). These are resource counts of a presented construction, not predictions fitted to data. The simulation results are checked against the acceptance threshold 0.375 from Montanaro [22], an external benchmark; no parameter is fitted to make the simulation agree. The only citation to Montanaro's script [23] is an auxiliary estimate of heuristic depth overhead in Section 3 and is not load-bearing for the central space bound. The possible concern visible in the manuscript's own figures — circuit 3c setting p=1 for all non-invalid partial assignments, which would collapse Montanaro's three-valued predicate into a Boolean — is a correctness/completeness issue rather than circularity: it would make the implementation fail to implement the intended diffusion operators, but it does not make the claimed result equivalent to its input by construction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central resource bound depends on (i) the validity of Montanaro's algorithm as an external framework, (ii) the correctness of the proposed circuits (counter and comparison), and (iii) the restriction to static variable ordering. None of these are formally verified in the paper.

assumptions (5)
  • domain assumption Montanaro's quantum backtracking algorithm, including the phase-estimation-based detection (Algorithm 2) and the find procedure (Algorithm 3), is correct as stated.
    The paper builds directly on [22] and does not reprove the algorithm; Section 2.2 summarizes it and all subsequent resource claims assume its correctness.
  • domain assumption The backtracking tree for a CSP has depth at most n and size T, and the quantum walk operators RA and RB act on the space described in Section 2.2.
    These are inherited from the CSP structure and Montanaro's definitions; the implementation does not derive them.
  • ad hoc to paper The comparison-overflow circuit (Fig. 3b) correctly flips the ancilla |a> iff M_i > l, using modular arithmetic modulo 2^(nu+1), and is reversible.
    This is the key primitive of the predicate implementation (Section 4.1). The paper describes the procedure but gives no formal proof that overflow occurs exactly when M_i > l and that no interference between successive comparisons arises.
  • ad hoc to paper The Boolean encoding (|10>, |11>, |00>) for SAT supports the required negation and disjunction operations.
    Section 4.2 introduces this encoding; its correctness for the described circuits is asserted but not proven.
  • domain assumption The static variable ordering is fixed classically and the partial assignment always consists of the first l+1 variables.
    Section 3 restricts to SVO to achieve the O(n log d) data-qubit bound; the implementation depends on this ordering property.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Practical implementation of a quantum backtracking algorithm." pith.science (2026). https://pith.science/paper/OOLVUCIG

@misc{pith2026190811291,
  author       = {Pith},
  title        = {Pith review of: Practical implementation of a quantum backtracking algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OOLVUCIG}},
  note         = {Machine review of arXiv:1908.11291}
}
abstract

In previous work, Montanaro presented a method to obtain quantum speedups for backtracking algorithms, a general meta-algorithm to solve constraint satisfaction problems (CSPs). In this work, we derive a space efficient implementation of this method. Assume that we want to solve a CSP with $m$ constraints on $n$ variables and that the union of the domains in which these variables take their value is of cardinality $d$. Then, we show that the implementation of Montanaro's backtracking algorithm can be done by using $O(n \log d)$ data qubits. We detail an implementation of the predicate associated to the CSP with an additional register of $O(\log m)$ qubits. We explicit our implementation for graph coloring and SAT problems, and present simulation results. Finally, we discuss the impact of the usage of static and dynamic variable ordering heuristics in the quantum setting.

Figures

Figures reproduced from arXiv: 1908.11291 by the authors.

Figure 1
Figure 1. dh/dR according to finalcomplexity.py for graph coloring given in [23]. The modified algorithm for RA and RB is presented as algorithm 4. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Mean number of calls to algorithm 2 depending on the number of [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Circuit (a) computes P(v1 · · · vn). If the assignment is a solution, then p = 1, else p = 0. Circuit (b) is a comparison operator. The operation is done modulo 2 ν+1. Circuit (c) computes P(v1, . . . , v`+1). If the partial assignment is not invalid, then p = 1, else p = 0. 4.2 How to check a constraint The circuit 4a is used to check if the variable xi has been assigned a value (e.g. if the i-th vertex of a graph … view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Circuit (a) checks if the i-th variable has been assigned a value. If vi = 0, |c 0 i = |c + 1i, otherwise |c 0 i = |ci. Circuit (b) checks if the j-th and the k-th variables have different values. If vj = vk, |c 0 i = |c + 1i, otherwise |c 0 i = |ci. of the boolean var…
Figure 5
Figure 5. Figure 5: Circuit (a) is the negation of a boolean variable. The value as [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Fig. (a): a graph. Fig. (b): its associated classical backtracking [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Fig. (a): a graph. Fig. (b): a subtree of its associated classical [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: Example of parallelization of the predicate for [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]
Figure 9
Figure 9. Figure 9: Circuit corresponding to algorithm 4 for [PITH_FULL_IMAGE:figures/full_fig_p017_9.png]
Figure 10
Figure 10. Figure 10: Circuit corresponding to algorithm 4 for [PITH_FULL_IMAGE:figures/full_fig_p018_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 26 canonical work pages

  1. [22]

    Montanaro

    A. Montanaro. Quantum walk speedup of backtracking algorithms.The- ory of Computing14(15) 1–24, 2015

    work page 2015

  2. [1]

    Ambainis

    A. Ambainis. Quantum walks and their algorithmic applications.Inter- national Journal of Quantum Information01(04) 507–518, 2003

    work page 2003

  3. [2]

    Ambainis

    A. Ambainis. Quantum walk algorithm for element distinctness.SIAM J. Comput. 37(1) 210–239, 2007

    work page 2007

  4. [3]

    Ambainis and M

    A. Ambainis and M. Kokainis. Quantum algorithm for tree size esti- mation, with applications to backtracking and 2-player games. ACM, 2017

    work page 2017

  5. [4]

    Y. Aono, P. Q. Nguyen, and Y. Shen.Quantum Lattice Enumeration and Tweaking Discrete Pruning. Springer, 2018

    work page 2018

  6. [5]

    A. Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013

    arXiv 2013

  7. [6]

    Belovs, A

    A. Belovs, A. M. Childs, S. Jeffery, R. Kothari, and F. Magniez.Time- efficient quantum walks for 3-distinctness. Springer, 2013

    work page 2013

  8. [7]

    Campbell, A

    E. Campbell, A. Khurana, and A. Montanaro. Applying quantum algo- rithms to constraint satisfaction problems.Quantum 3(167), 2018. 13

    work page 2018

Show all 27 references
  1. [8]

    L. Chen, S. Jordan, Y.-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone. Report on post-quantum cryptography.NISTIR 8105, 2016

    2016

  2. [9]

    A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by a quantum walk. ACM, 2003

    2003

  3. [10]

    Davis, G

    M. Davis, G. Logemann, and D. Loveland. A machine program for theorem-proving. Communications of the ACM5(7) 394–397, 1962

    1962

  4. [11]

    Davis and H

    M. Davis and H. Putnam. A computing procedure for quantification theory. JACM 7(3) 201–215, 1960

    1960

  5. [12]

    de Werra

    D. de Werra. An introduction to timetabling. European Journal of Operational Research19(2) 151–162, 1985

    1985

  6. [13]

    Dechter and I

    R. Dechter and I. Meiri.Experimental evaluation of preprocessing tech- niques in constraint satisfaction problems. MorganKaufmannPublishers Inc., 1989

    1989

  7. [14]

    Eén and N

    N. Eén and N. Sörensson.An extensible SAT-solver. Springer, 2004

    2004

  8. [15]

    E. C. Freuder. A sufficient condition for backtrack-free search.JACM 29(1) 24–32, 1982

    1982

  9. [16]

    C. P. Gomes, H. Kautz, A. Sabharwal, and B. Selman. Satisfiability solvers. Elsevier, 2008

    2008

  10. [17]

    J. Gu, P. W. Purdom, J. Franco, and B. W. Wah.Algorithms for the satisfiability (SAT) problem: a survey. Amer Mathematical Society, 1997

    1997

  11. [18]

    J. Kempe. Quantum random walks: an introductory overview.Contem- porary Physics 44(4) 307–327, 2003

    2003

  12. [19]

    F. T. Leighton. A graph coloring algorithm for large scheduling prob- lems. Journal of research of the NBS84(6), 1979

    1979

  13. [20]

    Magniez, A

    F. Magniez, A. Nayak, J. Roland, and M. Santha.Search via quantum walk. Theory of Computing, 2007

    2007

  14. [21]

    Malaguti and P

    E. Malaguti and P. Toth. A survey on vertex coloring problems.Inter- national Transactions in Operational Research17, 2010. 14

    2010

  15. [23]

    Montanaro

    A. Montanaro. Data from Quantum algorithms for CSPs. 07 2019

    2019

  16. [24]

    Montanaro

    A. Montanaro. Quantum speedup of branch-and-bound algorithms. arXiv:1906.10375, 2019

    1906 arXiv

  17. [25]

    M. Santha. Quantum walk based search algorithms. Springer, 2008

    2008

  18. [26]

    Quantum speed-up of Markov chain based algorithms

    M.Szegedy. Quantum speed-up of Markov chain based algorithms. IEEE, 2004

    2004

  19. [27]

    van Beek.Backtracking search algorithms

    P. van Beek.Backtracking search algorithms. Elsevier, 2006. Appendix 15 Figure 8: Example of parallelization of the predicate fork = 4. {C (i),i ∈ [ [1, 4] ]} is a partition ofC and ⏐⏐C (i)⏐⏐≤ m k∀i∈ [ [1, 4] ]. The checking operation of an element inC (i) is denoted by Check(...

    2006

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.