{"id":"8780fd86-7f55-488d-bcfd-41c6930e794d","arxiv_id":"2502.08853","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A quantum dynamic programming circuit prepares the uniform superposition of all Hamiltonian cycles in polynomial gates, reducing Grover-based TSP search complexity to O(sqrt((N-1)!).","lead":"This paper proposes a quantum algorithm that builds a uniform superposition of all Hamiltonian cycles (valid TSP routes) for N cities using a polynomial number of gates and only O(N log N) qubits. Combined with Grover search, it reaches the unstructured-search query bound O(sqrt((N-1)!)) for TSP, with small-scale Qiskit demonstrations on 4 to 8 nodes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"HC-generation correctness is asserted, not proven: modules A-D of Fig. 4 implement the 'match and replace' bijection for arbitrary N, and ancilla/value registers are never proved to reset to |0>. The O(sqrt((N-1)!)) claim collapses if this gate is wrong.","rationale":"The paper's main theorem (Theorem 2) is the load-bearing component. The query-complexity claim O(sqrt((N-1)!)) is derived by assuming the HCg gate exactly prepares the uniform HC superposition; without that gate, the search starts from a wrong or entangled state, and the Grover diffusion HCg(I-2|0><0|)HCg-dagger also fails because it relies on HCg mapping the prepared superposition back to |0>. The recursive enumeration itself is a bijection: inserting a new vertex into a cycle is reversible, and distinct insertions yield distinct cycles, so the combinatorial skeleton is sound. The unproven part is the unitary implementation: modules A-D must locate the unique position of the matched digit in a superposition of permutations, rewrite that position to the new vertex, put the matched digit into the new register, and reset all work qubits, for all basis states simultaneously. The paper gives no inductive proof and only a verbal description of the release modules. This is exactly the kind of place where a subtle controlled-operation error (wrong control qubit, failure to uncompute, or extra entanglement) would break the algorithm. The proposed test—an independent statevector simulation for N=6—would settle whether the circuit family exists as described. If it passes, the main algorithmic contribution stands; if it fails, the central claim collapses. The 'theoretical minimum' overclaim is real but secondary and can be corrected by rewording; it does not affect the soundness of the HC-generation construction.","tokens_in":16535,"tokens_out":16993,"duration_ms":183309,"concrete_test":"Independently reconstruct the HCg circuit for N=6 from the Sec. II.C module descriptions without using the authors' code, and run a statevector simulation in Qiskit or Cirq: apply HCg to |0>^(N ceil(log N)+log N), then verify (i) the index-register state has exactly 120 nonzero amplitudes, all equal to 1/sqrt(120), supported on the six-vertex Hamiltonian cycles; and (ii) the reduced state of all ancillary/value registers is exactly |0>. If the reconstruction cannot be completed or the fidelity is below 1, the match-and-replace modules are not established for general N.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—polynomial-gate preparation of the uniform HC superposition—rests entirely on Theorem 2 and the unproven assertion (Sec. II.C) that modules A-D of Fig. 4 implement the 'match and replace' transformation for arbitrary N. No gate-level specification of these modules is given; the text states that their functions 'can be verified' and are promoted 'by expanding qubits.' The recursive construction also requires that after every level the ancillary registers (or borrowed value registers) are exactly |0> and disentangled from the index register; otherwise the next amplitude-amplification step does not start from the tensor-product uniform state assumed in the proof. No inductive invariant is stated or proved. Numerical support is limited to explicit checks for 4- and 5-vertex HC generation; the N=6-8 TSP simulations use preset thresholds and iteration counts and are not a clean test of the HCg gate. If this gate is wrong or leaks ancilla entanglement, the output is not the uniform HC superposition and the claimed O(sqrt((N-1)!)) query complexity does not follow.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Grover-based TSP algorithm whose initial state is the uniform superposition of all Hamiltonian cycles, prepared by a recursive quantum dynamic programming construction (the 'HCg gate') claimed to run in O(N^{5/2}) gates using only O(log N) ancillary qubits, which are then reused from the value registers. Weights are computed with a controlled-phase QFT shortcut, and the optimal tour is found by amplitude amplification, with a claimed query complexity of O(sqrt((N-1)!). The authors report Qiskit implementations for N=4 through 8. The core technical issue is that the HCg circuit is only sketched and is not proved correct for arbitrary N.","tokens_in":16744,"tokens_out":8624,"duration_ms":82835,"significance":"If the missing proof can be supplied, the paper would make a useful contribution to the GAS/TSP literature: it eliminates the Hamiltonian-cycle-detection oracle, provides a polynomial-gate initial-state preparation with logarithmic ancilla overhead, and gives an explicit weight-computation circuit with a concrete qubit count and small-scale simulations. The strengths are the constructive recursive enumeration idea, the low qubit count (N*ceil(log N)+M), and the explicit implementation effort using a QFT shortcut. However, the headline query-complexity claim needs qualification, and the numerical results are conditional on knowledge of the optimal solution.","major_comments":[{"comment":"The quantum implementation of the recursive enumeration is the load-bearing step, but it is not proved. The text describes modules A-D informally and states that their functions 'can be verified' and can be promoted to handle more nodes 'by expanding qubits.' No gate-level specification is given, no inductive invariant is stated for arbitrary N, and no argument establishes that the auxiliary register is returned to |0> after each insertion, or that registers not targeted by module D remain untouched. These properties are needed both for the next recursion level and for the Grover diffusion HCg(I-2|0><0|)HCg† in Fig. 2 to act on a clean product state. The supplemental check for 4- and 5-vertex HCs does not substitute for a proof for general N. As it stands, Theorem 2's conclusion is an assertion rather than a proven result.","section":"Section II.C, Theorem 2 and Fig. 4"},{"comment":"There is an unresolved tension about qubit usage: the Fig. 4 caption says the HC-generation algorithm 'requires additional log N auxiliary qubits except for the index registers,' while the Introduction and Section IV claim that the value registers can serve as these ancillas so that no extra qubits are needed. This reuse is plausible only if the value registers are exactly |0> and disentangled before each HCg/HCg† application. The uncomputation order QFT, U†_{w-CT}, H^{⊗M} in Fig. 2 is described only in words; its correctness depends both on the exactness of U_{w-CT} and on the HCg subcircuits leaving borrowed registers clean. Neither is proved. The paper should state the ancilla invariant precisely and prove it together with Theorem 2.","section":"Section II.C, Fig. 4 caption; Section IV"},{"comment":"The claim that O(sqrt((N-1)!)) is 'the theoretical minimum query complexity of quantum search algorithms for a general TSP' is not correct as stated. The paper itself cites reference [21], which reports a quantum algorithm for TSP with query complexity O*(1.728^N); for large N this is asymptotically smaller than sqrt((N-1)!) ~ exp((N ln N)/2). The informal argument 'we have to find the shortest one among (N-1)! HCs' is a lower bound only for algorithms that query an unstructured oracle over that candidate set; it does not lower-bound all quantum algorithms for general TSP. The claim should be qualified, for example as the minimum among Grover-type searches over Hamiltonian-cycle encodings, and the relationship to [21] should be discussed explicitly.","section":"Abstract; Section IV, Discussion and Table III"},{"comment":"The numerical demonstrations are not tests of the full minimum-finding algorithm. The threshold is set to C_T = w* + 1 using the known optimal weight, and the 'iterations' column lists hand-tuned values (for example, 5x+13 for N=8). The reported accuracies therefore validate the Grover subroutine conditional on knowledge of the optimum, not the threshold-updating procedure described in the Discussion. This limitation should be stated in the results section, and the simulations should either implement Dürr-Høyer-style updating or be presented explicitly as a subroutine demonstration.","section":"Section III, Table II; Section IV"}],"minor_comments":[{"comment":"The terms 'Hamiltonian circle' and 'Hamiltonian cycle' are used interchangeably; please standardize to one term and define it at first use.","section":"Throughout"},{"comment":"In the submitted text, Figures 1 and 2 appear with the same circuit diagram and nearly identical captions; please replace with the intended distinct figures.","section":"Figures 1 and 2"},{"comment":"The counting justification 'any two different HCs of the same length must have at least two different edges' is not a sufficient proof of injectivity of the insertion map; please spell out the one-to-one correspondence between length-(N-1) HCs with a chosen edge and length-N HCs.","section":"Section II.C, Theorem 1"},{"comment":"The formula for the Grover iteration count n in Eq. (5) appears to be missing a closing parenthesis, and the definitions of S0 and Sx are split awkwardly across the text; please reformat and check the mathematical typesetting.","section":"Section II.C, Eqs. (2)-(5)"},{"comment":"The phrase 'Sterling's approximation' appears twice and should be 'Stirling's approximation'; also, providing a code repository or explicit gate-level circuit files would strengthen reproducibility.","section":"Section III and Table II"}],"recommendation":"major_revision","confidential_remarks":"The main risk is that the HCg circuit may not be correct for larger N, but this is fixable with a precise construction and proof rather than requiring a fundamentally new algorithm. I would not recommend rejection on the current evidence; I would ask for a complete specification and proof before publication. The 'theoretical minimum' overstatement should be corrected, since the paper's own reference [21] directly contradicts the unqualified version of the claim and is likely to be noticed by readers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is real: instead of detecting Hamiltonian cycles after a brute-force search, recursively prepare the uniform superposition of all HCs using a match-and-replace circuit with only log N ancillas. That is a genuine departure from the indexing-function approaches in [35-37], and the QFT shortcut for weight computation is cleanly adapted from [31]. The small-N checks (4- and 5-vertex HC generation, 4-8 node TSP) plausibly show the construction works at that scale. For that reason the paper deserves to be read, not dismissed.\n\nThe soft spots are exactly where the reader put them. Theorem 2 is the load-bearing result, and its proof is a verbal description of modules A-D plus \"can be verified.\" There is no gate-level specification, no inductive invariant showing the ancillas return to |0>, and no argument that the match-and-replace circuit is unitary and leak-free for arbitrary N. The numerical checks stop at N=5 for the HC generator itself; the N=6-8 TSP runs preset the threshold and iteration count using the known optimum, so they demonstrate the circuit under favorable conditions rather than testing it blind. That is a real gap, and it is the difference between a plausible algorithm and a proven one.\n\nThe other issue is the \"theoretical minimum query complexity\" claim. If read as \"the minimum for a Grover search over the space of HCs,\" it is true by the unstructured search lower bound. But the paper states it without that qualifier, which contradicts the existence of Ambainis et al.'s O*(1.728^N) dynamic-programming algorithm—a quantum search algorithm for TSP with a strictly better query complexity. The authors cite [21] but do not reconcile the two statements. That needs to be fixed.\n\nUnderneath the overclaim, the contribution is still meaningful: a polynomial-gate preparation of the uniform HC superposition would convert TSP into a minimum-finding problem with query complexity O(sqrt((N-1)!)), which is a practical improvement over the HCD-oracle approach in the complete-graph regime. The gate complexity is high (O(N^(5/2)) per Grover iteration), but the qubit count is genuinely low.\n\nMy recommendation: send it to peer review. A serious referee can ask for the missing inductive proof or a complete circuit decomposition, and the authors should release the Qiskit code and data for the HC-generation checks. If the circuit proof materializes, this becomes a solid paper; if not, the referee report will make the gap explicit. Either way, it is the right kind of paper to put in front of an expert.","headline":"The recursive HC-generation idea is genuinely new and worth a serious look, but the paper's central theorem is only sketched and the 'theoretical minimum' claim overreaches.","tokens_in":17293,"tokens_out":2744,"would_cite":false,"duration_ms":29605,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17","05C45","90C27"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"A polynomial-gate circuit prepares the uniform superposition of all Hamiltonian cycles, letting Grover search solve TSP at the theoretical minimum query complexity of $O(\\sqrt{(N-1)!})$ with only $\\log N$ ancillas.","keywords":["quantum computing","Traveling Salesman Problem","TSP","quantum search","quantum dynamic programming","Hamiltonian cycle generation","Grover's algorithm","query complexity"],"falsifier":"Run the HC-generation circuit for a 6- or 7-node complete graph and measure the index registers many times. If any non-Hamiltonian-cycle string appears, or if the $(N-1)!$ cycle frequencies are not equal within sampling error, the circuit is not preparing the claimed uniform superposition. For $N=6$ there are 120 cycles, so in 10000 shots each should appear about 83 times with binomial spread; observing an infeasible string or a cycle with frequency deviating by far more than the sampling fluctuation would refute the central claim. A full gate-level listing of modules A-D for general $N$ that either fails an exact simulation for $N=6$ or cannot be uncomputed without leaving residual entanglement in the ancillas would also settle the question.","tokens_in":16247,"feed_emoji":"⚛️","tokens_out":13531,"duration_ms":120388,"temperature":0.7,"pith_summary":"The paper's central claim is that the bottleneck of Grover-based TSP---the preparation of a uniform superposition of all feasible tours---can be removed entirely. It describes an HC-generation circuit that starts from a 2-vertex cycle and, in each recursive round, coherently inserts the next vertex into every edge of every existing cycle, so that the index register ends in the exact uniform superposition of all $(N-1)!$ Hamiltonian cycles. Because this preparation costs only polynomial gates and $\\log N$ ancillary qubits (or none at all, by reusing the value registers), the search space shrinks from all $N^{N}$ encodings to the cycles themselves, and Grover search over that space has query complexity $O(\\sqrt{(N-1)!})$, which the authors argue is the theoretical minimum for a general $N$-node TSP. The authors report simulations for 4- to 8-node complete graphs, with success rates from 98.7% to 100% in their examples. If the construction is correct for every $N$, it eliminates the Hamiltonian-cycle-detection oracle and turns TSP into a plain minimum-finding problem over tours.","feed_headline":"Quantum TSP search cost drops to sqrt((N-1)!)","feed_subtitle":"A polynomial-gate circuit prepares all Hamiltonian cycles at once, needing only log N ancillas and no detection oracle.","key_machinery":"The load-bearing object is the HCg gate, a quantum circuit that turns the classical recursive enumeration of Hamiltonian cycles into a coherent operation. Each recursion step first prepares a uniform superposition of candidate new vertices by amplitude amplification, then applies the four modules of Fig. 4: module A matches a register holding the candidate vertex against its occurrence in each encoded cycle, module B zeroes that matched register, module C releases the auxiliary qubit, and module D replaces it by the new vertex value. The counting identity that carries the argument is the bijection of Theorem 1: the $(N-2)!$ cycles of length $N-1$ each generate $N-1$ distinct length-$N$ cycles, together exhausting all $(N-1)!$ cycles. The second mechanism is the $U_G(\\theta)$ shortcut to the quantum Fourier transform, which encodes an integer's complement-code value as a phase sequence built from single-qubit phase gates, so the total weight of a cycle can be written into the value register without constructing a unitary whose eigenvalues are the weights.","core_discovery":"The authors' central discovery is that the set of all Hamiltonian cycles has a recursive insertion structure that can be made coherent: from every length-$(N-1)$ cycle, deleting one edge and connecting the new vertex through the two endpoints yields a length-$N$ cycle, and every length-$N$ cycle is obtained exactly once this way. The HCg gate implements this 'match and replace' bijection as a reversible circuit, so $N-2$ rounds produce the state $(1/\\sqrt{(N-1)!})\\sum_{\\sigma\\in\\mathrm{HC}}|\\sigma\\rangle$ exactly. With this initial state, the Grover diffusion operator acts only on feasible tours, the weight oracle is built from a QFT shortcut using controlled phase gates, and the full minimum-search algorithm has query complexity $O(\\sqrt{(N-1)!})$---the value the paper calls the lowest query complexity a pure quantum search algorithm can have for a general TSP. The paper further claims that the value registers can double as the $\\log N$ auxiliary qubits, so no explicit ancillas are needed, and it demonstrates the complete circuit on 4- through 8-node instances with near-unit success probabilities.","pith_inferences":["The same insert-into-every-edge recursion is a template for generating superpositions over other edge-insertable combinatorial families, such as Hamiltonian paths or spanning trees; a test on such a family would show whether the match-and-replace modules are the scalable core of the construction.","The claimed minimum query complexity assumes the search uses only the number of feasible tours; if edge weights carry special structure (for instance Euclidean distances), a different search strategy might exploit that structure and achieve a lower bound on real instances.","The reuse of value registers as ancillas is safe only if the uncomputation in modules A-C is exact for every $N$; a direct verification that the reduced density matrix of the index registers is the uniform mixture for $N=6$ or $7$ would be a stronger check than the 4- and 5-vertex numerical tests reported in the supplementary material.","If the HC-generation circuit scales as claimed, it also provides a fast state-preparation subroutine for other permutation-based quantum optimization pipelines, not only for the TSP."],"forward_implications":["The Hamiltonian-cycle-detection oracle becomes unnecessary, because the prepared initial state contains only feasible tours; each Grover iteration therefore acts inside the subspace of Hamiltonian cycles.","The qubit count for a complete $N$-node TSP is $N\\lceil\\log N\\rceil+M$ with no separately allocated ancillas, since the value registers are reused as the auxiliary registers; the paper's eight-node example uses 30 qubits.","Initial-state preparation is polynomial in $N$---$O(N^{5/2})$ gates for the HC-generation step---an exponential gate-complexity improvement over the previous two-step-search preparation, whose query cost is about $O(e^{N/2}/N^{1/4})$.","The full minimum-finding procedure retains query complexity $O(\\sqrt{(N-1)!})$ and, with quantum exponential searching, returns the optimum with probability at least $1/2$ per run, so $c$ repetitions give success probability at least $1-2^{-c}$.","The weight oracle uses only $O(N^2M)$ controlled phase gates via the QFT shortcut, avoiding the construction of a weight-eigenvalue unitary required by phase-estimation approaches."],"supporting_citations":[{"why":"Supplies the Hamiltonian-cycle-detection oracle baseline and the sparse-graph encoding method that the new algorithm improves on or avoids.","marker":"[29]"},{"why":"The previous two-step quantum search whose initial-state preparation is exponential in queries; this is the preparation cost the paper claims to reduce to polynomial gate complexity.","marker":"[30]"},{"why":"Introduces the QFT shortcut used here to compute tour weights with controlled phase gates instead of quantum phase estimation.","marker":"[31]"},{"why":"Earlier permutation-superposition preparation via an indexing function that consumed many auxiliary registers; motivates the ancilla-light recursive construction.","marker":"[37]"},{"why":"Provides the amplitude-amplification routine used to prepare the uniform superposition of candidate vertices at each recursion step.","marker":"[39]"},{"why":"Supplies the zero-failure-rate Grover variant used to make the amplitude amplification exact.","marker":"[40]"},{"why":"The quantum minimum-finding procedure adapted for the threshold-update loop of the full TSP search.","marker":"[33]"},{"why":"Tight bounds on quantum searching that give the stopping rules and success probability of the repeated search.","marker":"[34]"}],"fun_headline_variants":["Quantum TSP search reaches optimal query complexity","All Hamiltonian cycles prepared in poly gates for TSP search","TSP quantum speedup with log N ancillas and optimal queries","Quantum dynamic programming prepares TSP tours in poly time","Minimal queries for TSP quantum search now feasible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the match-and-replace circuit modules A-D of Fig. 4 implement the recursive insertion bijection correctly for every $N$, and that the value registers can serve as the required $\\log N$ ancillary qubits without corrupting the computation; the paper asserts this in prose and checks it numerically only for 4- and 5-vertex cycles, with no complete gate-level inductive proof for general $N$.","fun_headline_variants_meta":{"raw":{"variants":["Quantum TSP search reaches optimal query complexity","All Hamiltonian cycles prepared in poly gates for TSP search","TSP quantum speedup with log N ancillas and optimal queries","Quantum dynamic programming prepares TSP tours in poly time","Minimal queries for TSP quantum search now feasible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000382,"raw_usage":{"total_tokens":2048,"prompt_tokens":990,"completion_tokens":1058,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":980}},"tokens_in":606,"tokens_out":1058,"duration_ms":9647,"temperature":1.0,"reasoning_tokens":980,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T23:29:34.110515+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the HC-generation circuit for a 6- or 7-node complete graph and measure the index registers many times. If any non-Hamiltonian-cycle string appears, or if the $(N-1)!$ cycle frequencies are not equal within sampling error, the circuit is not preparing the claimed uniform superposition. For $N=6$ there are 120 cycles, so in 10000 shots each should appear about 83 times with binomial spread; observing an infeasible string or a cycle with frequency deviating by far more than the sampling fluctuation would refute the central claim. A full gate-level listing of modules A-D for general $N$ that either fails an exact simulation for $N=6$ or cannot be uncomputed without leaving residual entanglement in the ancillas would also settle the question.","supporting_citations":[{"cited_title":"The traveling salesman problem: An overview of exact and approximate algorithms","cited_arxiv_id":null,"evidence_quote":"The previous two-step quantum search whose initial-state preparation is exponential in queries; this is the preparation cost the paper claims to reduce to polynomial gate complexity."},{"cited_title":"This idea can be ex- tended to our problem","cited_arxiv_id":null,"evidence_quote":"Introduces the QFT shortcut used here to compute tour weights with controlled phase gates instead of quantum phase estimation."},{"cited_title":"Boosting Combinatorial Problem Modeling with Machine Learning","cited_arxiv_id":"1807.05517","evidence_quote":"Earlier permutation-superposition preparation via an indexing function that consumed many auxiliary registers; motivates the ancilla-light recursive construction."},{"cited_title":"Quantum Annealing and GNN for Solv- ing TSP with QUBO, 134–145 (Springer Nature Sin- gapore, 2024)","cited_arxiv_id":null,"evidence_quote":"Supplies the zero-failure-rate Grover variant used to make the amplitude amplification exact."},{"cited_title":"Worst-case analysis of a new heuristic for the travelling salesman problem","cited_arxiv_id":null,"evidence_quote":"The quantum minimum-finding procedure adapted for the threshold-update loop of the full TSP search."},{"cited_title":"An effective implementation of the Lin– Kernighan traveling salesman heuristic","cited_arxiv_id":null,"evidence_quote":"Tight bounds on quantum searching that give the stopping rules and success probability of the repeated search."}],"review_version":1}