Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2502.08853 v4 pith:2O65AC2E submitted 2025-02-12 quant-ph

Bai Xujun , Shang Yun This is my paper · ORCID
classification quant-ph MSC 68Q1268Q1705C4590C27 PACS 03.67.Ac
keywords quantumcomputingTravelingSalesmanProblemTSPsearchdynamicprogrammingHamiltoniancyclegenerationGrover'salgorithmquerycomplexity
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Section II.C, Theorem 2 and Fig. 4] 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.
  2. [Section II.C, Fig. 4 caption; Section IV] 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.
  3. [Abstract; Section IV, Discussion and Table III] 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.
  4. [Section III, Table II; Section IV] 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.
minor comments (5)
  1. [Throughout] The terms 'Hamiltonian circle' and 'Hamiltonian cycle' are used interchangeably; please standardize to one term and define it at first use.
  2. [Figures 1 and 2] 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.
  3. [Section II.C, Theorem 1] 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.
  4. [Section II.C, Eqs. (2)-(5)] 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.
  5. [Section III and Table II] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the HC-generation construction and query-complexity argument are self-contained; the unproven circuit modules are a rigor gap, and the known-optimum simulation presets are benchmarks, not inputs to the theoretical claim.

full rationale

The central derivation does not assume its target conclusion. Theorem 2 is a constructive recursion that builds longer Hamiltonian cycles by a 'match and replace' bijection on basis states; the uniform HC superposition is intended to follow from the bijectivity and counting of that map together with the uniform state prepared by amplitude amplification. No parameter of this construction is fitted from the final query complexity O(sqrt((N-1)!)), which is obtained by the standard Grover/Durr-Hoyer argument over the (N-1)!-element HC space. The paper contains no load-bearing self-citations: references [29]-[31] and [37] are external prior work, not the authors' own. Section III's simulations preset the threshold to the known optimum (CT = w* + 1) and choose iteration counts empirically, so the reported accuracies are post-hoc benchmarks rather than end-to-end predictions; the paper itself notes that the threshold is unknown in practice and should be updated. The main weakness is that the abstract modules A-D of Fig. 4 are only asserted to implement the match-and-replace map for arbitrary N, with no complete gate-level proof of the ancilla-reset invariant; this is a missing-proof or correctness risk, not a circular use of the target result. Thus no step reduces by construction to its own input.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central algorithm introduces no new physical entities or free model parameters; the theoretical derivation is constructive. The free parameters listed are all confined to the numerical demonstrations, where the known optimum is used to set thresholds and iteration counts. The main burden is the unproven correctness of the HC-generation circuit for arbitrary N.

free parameters (3)
  • Threshold C_T in numerical demonstrations = w*+1 (optimal total weight plus 1)
    Set using the known optimal solution for each benchmark instance, so the oracle marks exactly the optimal solutions; this is a demonstration choice, not part of the algorithm's general procedure.
  • Grover iteration counts in Table II = e.g., 5x+1, 3x+1, 5x+13 with x = ceil(sqrt((N-1)!/opt_num))
    Hand-chosen per instance to maximize measured accuracy; the general algorithm would use Dürr-Høyer exponential searching with a constant-factor overhead.
  • Value register size M = M=5 for N=4..7, M=6 for N=8
    Chosen for simulation convenience to fit small integer edge weights; not a free parameter of the core algorithm, but affects the reported qubit counts.
assumptions (4)
  • standard math All Hamiltonian cycles on N nodes can be generated by starting from the 2-cycle on {N-2,N-1} and repeatedly inserting vertex k-1 into every edge of every existing cycle (Theorem 1).
    The statement is a true combinatorial fact, but the proof in the paper is sketchy; it is the basis of the recursive enumeration.
  • ad hoc to paper The circuit modules A-D in Fig. 4 realize the 'match and replace' transformation for arbitrary N and leave the ancilla registers clean.
    This is asserted with a prose explanation and numerical checks for N=4,5 only; no complete gate-level specification or inductive proof is given.
  • domain assumption Any TSP instance can be reduced to a complete TSP by adding large-weight edges without changing the optimal tour and without exceeding the value-register range.
    Stated in Section II.A; standard, but relies on sufficient bits to store the large weights, which the paper does not fully analyze for sparse instances.
  • ad hoc to paper The value registers can serve as the log N ancillary qubits required by HC-generation by uncomputing the weight circuit.
    Claimed in Section II.A and Discussion; relies on reversibility and M > log N, but the interleaving of HCg with the weight computation is not fully specified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits." pith.science (2026). https://pith.science/paper/2O65AC2E

@misc{pith2026250208853,
  author       = {Pith},
  title        = {Pith review of: A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2O65AC2E}},
  note         = {Machine review of arXiv:2502.08853}
}
read the original abstract

The Traveling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation. Our work provides a meaningful research case on how to fully utilize the structures of specific problems to unleash the acceleration capability of the quantum search algorithms.

Figures

Figures reproduced from arXiv: 2502.08853 by the authors.

Figure 2
Figure 2. FIG. 2. Illustration of the quantum circuit of our algorithm’s searching module, which will be executed many times to amplify [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. Obtain an HC of length 5 from an HC of length 4. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. FIG. 4. Partial quantum circuit of HC-generation algorithm, where the first set of qubits is auxiliary register initialized [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figures from the paper (3 more)
Figure 5
Figure 5. Figure 5: FIG. 5. Quantum circuit of [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 7
Figure 7. Figure 7: FIG. 7. The controlled- ()⟩ (2)⟩ [PITH_FULL_IMAGE:figures/full_fig_p008_7.png]
Figure 6
Figure 6. Figure 6: FIG. 6. Quantum circuit for getting the geometric sequence [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation

    quant-ph 2025-11 conditional novelty 6.0 of 10

    A variational quantum solver encodes TSP routes in the correlation matrix of two entangled registers, using O(log N) qubits, and is demonstrated for four cities on a silicon photonic chip.

Reference graph

Works this paper leans on

56 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [31]

    This idea can be ex- tended to our problem

    provides a detailed introduction to GAS for Constrained Polynomial Binary Optimization (CPBO), which employs a shortcut of QF T. This idea can be ex- tended to our problem. In the previous section, we realized the HC-generation algorithm as the HCg -gate in Fig. 1 and Fig. 2. In the following, we will realize the Uw−CT -gate to compute difference value be...

    work page

  2. [21]

    & Tapp, A

    Boyer, M., Brassard, G., Høyer, P. & Tapp, A. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics46, 493–505 (1998)

    work page 1998

  3. [1]

    It is clear that a quantum state encoding a feasible solution should rep- resent a N -cycle as an element of N -order permutation group

    Take a 4-node TSP as example, the quantum state |2031⟩ represents the tour route 0 → 2 → 3 → 1 → 0 because the 0-th set of qubits is in state |2⟩, the 2- th set of qubits is in state |3⟩, etc. It is clear that a quantum state encoding a feasible solution should rep- resent a N -cycle as an element of N -order permutation group. There are ( N − 1)! cycles ...

    work page

  4. [2]

    Encoding operators. All registers |index⟩ |value⟩, as a group of qubits, are initialized to the uni- form superposition state of all HCs with corre- sponding total weights by these operators, which are showed in Fig.1. HCg -gate can gener- ate the uniform superposition state of all HCs as |index⟩. H ⊗M , U w−CT and inverse Quan- tum Fourier Transform QF T...

    work page

  5. [3]

    Label the states whose total weights are less than threshold CT

    Oracle operators. Label the states whose total weights are less than threshold CT . In Fig.2, the Z-gate acting on the last qubit (i.e., sign bit) can mark negative values, that is, label the HCs whose total weights are below the threshold CT

    work page

  6. [4]

    indexing unitary

    Diffusion operators. See the part behind the Z- gate in Fig.2; QF T, U† w−cT and H ⊗M can release the value registers to assist the HCg †-gate, thereby our whole algorithm does not need extra auxiliary registers. The part inside the dashed box in Fig.2 is standard Grover’s diffusion operator HCg (I − 2|0⟩⟨0|)HCg † where H ⊗mN is replaced with HCg - gate, ...

    work page

  7. [5]

    The above enumeration process has a terrible time complexity of O((N − 1)!), which makes it a NP-hard problem to find all valid HCs [38]

    → (N − 2) corresponding to permutation σ = ( N − 1, N− 2) to generate all N -length HCs, where in order to facilitate the achievement of quantum circuits later the last vertex added is 0. The above enumeration process has a terrible time complexity of O((N − 1)!), which makes it a NP-hard problem to find all valid HCs [38]. However, based on the proof of ...

    work page

  8. [6]

    , N− 1} and a new permutation eσ = (k − 1, σ)

    Add en element k − 1 to V , which produces a new set eV = {k − 1, k, k+ 1, . . . , N− 1} and a new permutation eσ = (k − 1, σ)

    work page

Show all 56 references
  1. [7]

    By performing the above steps for each HC of length N − k, we obtain (N − k − 1)! × (N − k) = (N − k)! new HCs, that is, all ( N − k + 1)-length HCs

    Swap k − 1 and each digit in σ in order from small to large, which generates N − k new HCs of length N − k + 1. By performing the above steps for each HC of length N − k, we obtain (N − k − 1)! × (N − k) = (N − k)! new HCs, that is, all ( N − k + 1)-length HCs. We can easily 5...

  2. [8]

    The function is to match the second and third sets of registers

    Module A. The function is to match the second and third sets of registers. If the numbers in the second and third sets of registers are exactly the same, three qubits of the first set of registers will become |111⟩

  3. [9]

    The function is to set the third set of registers to |0⟩ by performing XOR operation on the second and third sets of registers when the first set of registers is in state |111⟩

    Module B. The function is to set the third set of registers to |0⟩ by performing XOR operation on the second and third sets of registers when the first set of registers is in state |111⟩

  4. [10]

    The function is to free up the first set of registers

    Module C. The function is to free up the first set of registers. This module must be combined with the repeat-gate behind it. The repeat-gate is a simple repetition of module A. If the third set of registers is not in state |000⟩, we only need to execute the repeat-gate to fre...

  5. [11]

    Discussion

    Module D. The function is to execute the second step in (1), i.e., |042⟩ → |142⟩, which only needs an ancillary qubit. This module can be modified according to the number changing from 0, that is, modifying the target qubit of the second gate and the control qubit of the third...

  6. [12]

    Ising formulations of many np problems

    Lucas, A. Ising formulations of many np problems. Fron- tiers in Physics2 (2014). URL http://dx.doi.org/10. 3389/fphy.2014.00005

    2014

  7. [13]

    frame- work

    use UG(θ) controlled by boolean variables to solve CPBO problems. We can extend this method to our quantum algorithm for the TSP. Under our TSP encod- ing, every index register encodes the result σ(i) pro- duced after an HC as a permutation σ acts on i ∈ {0, 1, . . . , N− 1}. ...

  8. [14]

    Initialize l = 1 and set λ = 6 /5

    Randomly select an HC and take its total weight as the initial threshold. Initialize l = 1 and set λ = 6 /5. (Any value of λ strictly between 1 and 4/3 will perform. Parameters l and λ are used to determine the number of iteration steps.)

  9. [15]

    (Grover’s searching module can be seen in Fig.2

    Repeat the following and interrupt it when the total number of executions of Grover’s searching module is more than 22 .5 p (N − 1)!. (Grover’s searching module can be seen in Fig.2. The constant coeffi- cient 22.5 depends on λ.) a Execute the encoding module shown in Fig.1 to...

  10. [16]

    The probability finding the optimal solution for the above quantum algorithm is at least 1 /2 by computing the expected running time to find the minimum value, given by [33, 34]

    Return the final measurement result. The probability finding the optimal solution for the above quantum algorithm is at least 1 /2 by computing the expected running time to find the minimum value, given by [33, 34]. Therefore, we can run c times to ensure a success probability...

  11. [17]

    Quantum algorithms: an overview

    Montanaro, A. Quantum algorithms: an overview. npj Quantum Information 2, 1–8 (2016)

    2016

  12. [18]

    Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). URL https://www.nature.com/ articles/s41586-019-1666-5

    2019

  13. [19]

    Shor, P. W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, 124–134 (IEEE, 1994)

    1994

  14. [20]

    Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth an- nual ACM symposium on Theory of computing, 212–219 (1996)

    1996

  15. [22]

    W., Hassidim, A

    Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum al- gorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009). URL https://link.aps.org/doi/ 10.1103/PhysRevLett.103.150502

    2009 doi

  16. [23]

    & Sipser, M

    Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quan- tum Computation by Adiabatic Evolution.arXiv e-prints quant–ph/0001106 (2000). quant-ph/0001106

    2000

  17. [24]

    Nielsen, M. A. & Chuang, I. Quantum computation and quantum information (2002)

    2002

  18. [25]

    & Gutmann, S

    Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. arXiv: Quantum Physics (2014). URL https://api.semanticscholar. org/CorpusID:118149905

    2014

  19. [26]

    Martoˇ n´ ak, R., Santoro, G. E. & Tosatti, E. Quantum annealing of the traveling-salesman problem. Phys. Rev. E 70, 057701 (2004). URL https://link.aps.org/doi/ 10.1103/PhysRevE.70.057701

    2004 doi

  20. [27]

    & Chakrabarti, B

    Das, A. & Chakrabarti, B. K. Colloquium: Quantum annealing and analog quantum computation. Rev. Mod. Phys. 80, 1061–1081 (2008). URL https://link.aps. org/doi/10.1103/RevModPhys.80.1061

    2008 doi

  21. [28]

    A., Schmelcher, P

    Goswami, K., Veereshi, G. A., Schmelcher, P. & Mukher- jee, R. Solving the travelling salesman problem using a single qubit (2024). URL https://arxiv.org/abs/ 2407.17207. 2407.17207

    2024

  22. [29]

    & Bahrampour, A

    Ramezani, M., Salami, S., Shokhmkar, M., Moradi, M. & Bahrampour, A. Reducing the number of qubits from n2 to n log2(n) to solve the traveling salesman problem with quantum computers: A proposal for demonstrating quantum supremacy in the nisq era (2024). URL https: //arxiv.org...

    2024 arXiv

  23. [30]

    The traveling salesman problem: An overview of exact and approximate algorithms

    Laporte, G. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research59, 231–247 (1992)

    1992

  24. [32]

    & Pathak, K

    Chauhan, C., Gupta, R. & Pathak, K. Survey of meth- ods of solving tsp along with its implementation using dynamic programming approach. International journal of computer applications52 (2012)

    2012

  25. [33]

    Worst-case analysis of a new heuristic for the travelling salesman problem

    Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. Rep., Carnegie- Mellon Univ Pittsburgh Pa Management Sciences Re- search Group (1976)

    1976

  26. [34]

    An effective implementation of the Lin– Kernighan traveling salesman heuristic

    Helsgaun, K. An effective implementation of the Lin– Kernighan traveling salesman heuristic. European Jour- nal of Operational Research126, 106–130 (2000)

    2000

  27. [35]

    Johnson, D. S. Local optimization and the traveling sales- man problem. In International colloquium on automata, languages, and programming, 446–461 (Springer, 1990)

    1990

  28. [36]

    & Prouvost, A

    Bengio, Y., Lodi, A. & Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research 290, 405–421 (2021)

    2021

  29. [37]

    & Milano, M

    Lombardi, M. & Milano, M. Boosting combinatorial problem modeling with machine learning. arXiv preprint arXiv:1807.05517 (2018)

    2018 arXiv

  30. [38]

    Ambainis, A. et al. Quantum Speedups for Exponential-Time Dynamic Programming Algo- rithms, 1783–1793. URL https://epubs.siam. org/doi/abs/10.1137/1.9781611975482.107. https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.107

    doi

  31. [39]

    & Gonz´ alez, F

    Vargas-Calder´ on, V., Parra-A., N., Vinck-Posada, H. & Gonz´ alez, F. A. Many-qudit representation for the travelling salesman problem optimisation. Journal of the Physical Society of Japan90, 114002 (2021). URL http://dx.doi.org/10.7566/JPSJ.90.114002

    2021 doi

  32. [40]

    Quantum Annealing and GNN for Solv- ing TSP with QUBO, 134–145 (Springer Nature Sin- gapore, 2024)

    He, H. Quantum Annealing and GNN for Solv- ing TSP with QUBO, 134–145 (Springer Nature Sin- gapore, 2024). URL http://dx.doi.org/10.1007/ 978-981-97-7801-0_12

    2024

  33. [41]

    A., Willsch, D., Maldonado-Romo, A

    Monta˜ nez-Barrera, J. A., Willsch, D., Maldonado-Romo, A. & Michielsen, K. Unbalanced penalization: a new ap- proach to encode inequality constraints of combinatorial problems for quantum optimization algorithms. Quan- tum Science and Technology 9, 025022 (2024). URL http://d...

    2024 doi

  34. [42]

    & Day-Evans, J

    Goldsmith, D. & Day-Evans, J. Beyond qubo and hobo formulations, solving the travelling salesman problem on a quantum boson sampler (2024). URL https://arxiv. org/abs/2406.14252. 2406.14252

    2024 arXiv

  35. [43]

    M., Delgado, I

    Ali, A. M., Delgado, I. P. & de Leceta, A. M. F. Trav- eling salesman problem from a tensor networks perspec- tive (2024). URL https://arxiv.org/abs/2311.14344. 2311.14344

    2024 arXiv

  36. [44]

    & Ya- mashiro, Y

    Liu, C.-Y., Matsuyama, H., hao Huang, W. & Ya- mashiro, Y. Quantum local search for traveling sales- man problem with path-slicing strategy (2024). URL https://arxiv.org/abs/2407.13616. 2407.13616. 12

    2024 arXiv

  37. [45]

    Zhu, J., Gao, Y., Wang, H., Li, T. & Wu, H. A realiz- able gas-based quantum algorithm for traveling salesman problem (2022). URL https://arxiv.org/abs/2212. 02735. 2212.02735

    2022 arXiv

  38. [46]

    Sato, R. et al. Circuit design of two-step quantum search algorithm for solving traveling salesman problems (2024). URL https://arxiv.org/abs/2405.07129. 2405.07129

    2024 arXiv

  39. [47]

    & Gonciulea, C

    Gilliam, A., Woerner, S. & Gonciulea, C. Grover adap- tive search for constrained polynomial binary optimiza- tion. Quantum 5, 428 (2021). URL http://dx.doi.org/ 10.22331/q-2021-04-08-428

    2021 doi

  40. [48]

    Chen, Y. et al. A low failure rate quantum algorithm for searching maximum or minimum. Quantum Information Processing 19 (2020)

    2020

  41. [49]

    & Hoyer, P

    Durr, C. & Hoyer, P. A quantum algorithm for find- ing the minimum (1999). URL https://arxiv.org/abs/ quant-ph/9607014. quant-ph/9607014

    1999 arXiv

  42. [50]

    & Tapp, A

    Boyer, M., Brassard, G., Høyer, P. & Tapp, A. Tight bounds on quantum searching. Fortschritte der Physik 46, 493–505 (1998). URL http: //dx.doi.org/10.1002/(SICI)1521-3978(199806)46: 4/5<493::AID-PROP493>3.0.CO;2-P

    1998 doi

  43. [51]

    & Ruskey, F

    Myrvold, W. & Ruskey, F. Ranking and unranking per- mutations in linear time. Information Processing Letters 79, 281–284 (2001). URL https://www.sciencedirect. com/science/article/pii/S0020019001001417

    2001

  44. [52]

    & Wang, J

    Marsh, S. & Wang, J. B. Combinatorial optimization via highly efficient quantum walks. Physical Review Re- search 2 (2020). URL http://dx.doi.org/10.1103/ PhysRevResearch.2.023302

    2020

  45. [53]

    H., Marsh, S

    Chiew, M., de Lacy, K., Yu, C. H., Marsh, S. & Wang, J. B. Graph comparison via nonlinear quan- tum search (2018). URL https://arxiv.org/abs/1810. 01647. 1810.01647

    2018 arXiv

  46. [54]

    & Saito, N

    Akiyama, T., Nishizeki, T. & Saito, N. NP-completeness of the Hamiltonian cycle problem for bipartite graphs. Journal of Information processing3, 73–76 (1980)

    1980

  47. [55]

    & Tapp, A

    Brassard, G., Høyer, P., Mosca, M. & Tapp, A. Quan- tum amplitude amplification and estimation (2002). URL http://dx.doi.org/10.1090/conm/305/05215

    2002 doi

  48. [56]

    Long, G. L. Grover algorithm with zero theoretical failure rate. Physical Review A64 (2001). URL http://dx.doi. org/10.1103/PhysRevA.64.022307. 13 SUPPLEMENT AR Y NUMERICAL RESUL TS FIG. S1. Simulation results of 1000 samples for each of six graphs, corresponding to X1 ∼ X6 in...

    2001 doi

Pith tools

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