{"id":"22de2ae6-ed8c-4a00-ac2f-8500b0ce5835","arxiv_id":"1908.11291","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper shows Montanaro's quantum backtracking algorithm can be implemented with O(n log d) data qubits and an O(log m) predicate counter.","lead":"This paper describes a memory-efficient way to build a known quantum algorithm for solving constraint satisfaction problems, using fewer qubits than earlier proposals. If correct, it could help researchers estimate quantum resources and test the algorithm on small instances.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The predicate circuit in §4.1 collapses 'indeterminate' and 'solution' into one bit, so Algorithm 4 step 3 makes D_x=I for every valid partial node; the walk's phase estimation then accepts unconditionally.","rationale":"The reader's weakest assumption, static variable ordering, is a scope limitation that the paper explicitly acknowledges; it does not make the circuit internally wrong. My concern is more direct: the manuscript conflates the three-valued predicate from §2.1 with the Boolean 'not invalid' bit computed in §4.1. Because the central claim is that the presented circuits implement Montanaro's backtracking algorithm, this conflation invalidates the implementation as written. The resource-counting parts and the honest SVO/DVO discussion are not the problem. The fix is small and testable, so the paper has a clear path to revision, but the current version should not be accepted as a correct implementation. Hence I recommend rejecting this version rather than leaving the verdict as conditional pending formal proof or code release.","tokens_in":8301,"tokens_out":23238,"duration_ms":238470,"concrete_test":"Implement the published §4.1 predicate and Algorithm 4 for an unsatisfiable 2-coloring instance (a triangle with d=2). At the root ℓ=0, circuit 3c sets p=1 because no constraint is fully assigned; step 3 then makes R_A and R_B identity, so phase estimation returns eigenvalue 1 with probability 1 and algorithm 2 outputs 'Solution exists'. Repeating with the added completeness condition p_solution = p_not_false ∧ (ℓ==n) should give nontrivial acceptance-vs-precision curves and reject the triangle. This single simulation distinguishes the two readings of the circuit.","verdict_should_be":"REJECT","load_bearing_attack":"The three-valued predicate P of §2.1 (true for complete solutions, indeterminate for valid partials, false otherwise) is implemented in §4.1 by a single Boolean p. Figure 3c's caption says p=1 whenever the partial assignment is 'not invalid'. Algorithm 4 step 3 then reads 'If P(x) is true, go to step 8', and step 8 is the identity branch of D_x. Thus every valid partial node is treated as a solution and D_x=I on all internal nodes. At the root (empty assignment, ℓ=0) p=1 for any CSP without unary constraints, so R_B R_A is the identity; algorithm 2's phase estimation sees eigenvalue 1 and always accepts 'Solution exists', even for unsatisfiable instances. This is not merely a missing proof: as written, the circuits do not implement Montanaro's diffusion operators. A missing completeness condition, e.g. p_solution = p_not_false ∧ (ℓ=n), would repair the construction, but it is absent from the manuscript.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8527,"tokens_out":6482,"duration_ms":67059,"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":[{"comment":"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.","section":"§4.1, Fig. 3c, Algorithm 4 step 3"},{"comment":"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.","section":"§4.1, Fig. 3b"},{"comment":"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.","section":"§5, Tables 6c and 7c"}],"minor_comments":[{"comment":"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.","section":"§2"},{"comment":"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.","section":"§4 and Algorithm 4"},{"comment":"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.","section":"§3"},{"comment":"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.","section":"References"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is not acceptable in its present form because the predicate implementation collapses the three-valued logic required by Montanaro's algorithm, making the walk trivially accept. However, the flaw is localized and appears repairable by introducing an explicit solution bit with the completeness condition ℓ=n, along with a correct comparison circuit and regenerated simulations. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stress-test note holds up. Circuit 3c sets p=1 for any 'not invalid' partial assignment, and Algorithm 4 makes D_x identity when p=1. Montanaro's walk needs identity only for complete solutions. With that encoding, on any CSP without unary constraints the root gets p=1, R_B R_A acts trivially on the start state, and phase estimation accepts unconditionally. The simulation tables in Section 5 cannot be reconciled with this unless the simulator used a different predicate than the one described; no code is released to check. This is not a missing proof or a subtlety; it's a load-bearing bug.\n\nWhat is worth keeping: the O(n log d) data-qubit encoding, the O(log m) quantum counter, the comparison-overflow trick for skipping constraints, and the SVO/DVO analysis. The counter construction is a genuine engineering contribution and goes beyond a routine translation of Montanaro's algorithm. Section 3's argument that dynamic variable ordering may not pay off for small instances is reasonable, and the paper is honest that its depth is not asymptotically competitive.\n\nBeyond the central bug, the comparison-overflow circuit in Figure 3b is asserted rather than proven; the simulation evidence is limited to small graph-coloring instances with no error analysis; and the resource counts assume SVO without a full proof that static ordering is not significantly worse. These are secondary. The main fix needed is to make the predicate distinguish 'complete solution' from 'valid partial' — for example, p_solution = p_not_false AND (ell = n). Once that is added, the O(n log d) claim becomes plausible and the counter construction stands on its own.\n\nFor peer review: I would not desk-reject this. The counter construction and the space analysis are novel and potentially useful, and the flaw is clearly identifiable and repairable. I would send it to referees with the expectation of major revision, and ideally the authors should release code or machine-checked circuits so the resource counts and the corrected predicate can be verified. A reader who wants to build on the counter will need more than this manuscript, but the kernel of the idea is worth refereeing.","headline":"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.","tokens_in":9018,"tokens_out":4730,"would_cite":false,"duration_ms":44222,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum backtracking","constraint satisfaction problem","quantum walk","space-efficient circuit","graph coloring","SAT","variable ordering heuristic","quantum counter"],"falsifier":"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.","tokens_in":121,"feed_emoji":"🧩","tokens_out":8364,"duration_ms":144936,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quantum backtracking fits in O(n log d) qubits","feed_subtitle":"A static ordering and a logarithmic counter let a quantum CSP solver run on much smaller hardware.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the walk-based backtracking algorithm whose walk operators this paper implements with reduced space.","marker":"[22]"},{"why":"Gives the depth-optimized implementation that sets the baseline; this paper trades depth for qubits.","marker":"[7]"},{"why":"Provides the tree-count script and ratios used to estimate the break-even between static and dynamic ordering.","marker":"[23]"},{"why":"Introduces the improved backtracking algorithm that depends on [22], showing the walk remains a necessary component.","marker":"[3]"}],"fun_headline_variants":["Quantum backtracking slims to O(n log d) qubits","Log-counter shrinks quantum backtracking to O(n log d)","Quantum CSP solver needs only O(n log d) qubits","Tiny register runs quantum backtracking: O(n log d)"],"cache_read_input_tokens":11136,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum backtracking slims to O(n log d) qubits","Log-counter shrinks quantum backtracking to O(n log d)","Quantum CSP solver needs only O(n log d) qubits","Tiny register runs quantum backtracking: O(n log d)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000285,"raw_usage":{"total_tokens":1640,"prompt_tokens":867,"completion_tokens":773,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":483,"completion_tokens_details":{"reasoning_tokens":701}},"tokens_in":483,"tokens_out":773,"duration_ms":7099,"temperature":1.0,"reasoning_tokens":701,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:19:32.986270+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Montanaro","cited_arxiv_id":null,"evidence_quote":"Supplies the walk-based backtracking algorithm whose walk operators this paper implements with reduced space."},{"cited_title":"Campbell, A","cited_arxiv_id":null,"evidence_quote":"Gives the depth-optimized implementation that sets the baseline; this paper trades depth for qubits."},{"cited_title":"Montanaro","cited_arxiv_id":null,"evidence_quote":"Provides the tree-count script and ratios used to estimate the break-even between static and dynamic ordering."},{"cited_title":"Ambainis and M","cited_arxiv_id":null,"evidence_quote":"Introduces the improved backtracking algorithm that depends on [22], showing the walk remains a necessary component."}],"review_version":1}