pith. sign in

arxiv: 2606.11843 · v1 · pith:QOMHJRBTnew · submitted 2026-06-10 · 🪐 quant-ph

Quantum iterative approach to the Traveling Salesman Problem

Arturo Rodr\'iguez-Almaz\'an , Guillermo Rivas , Ricardo S. Alonso , Daniela Falc\'o , Mir Amir Hosseini This is my paper

Pith reviewed 2026-06-27 09:53 UTC · model grok-4.3

classification 🪐 quant-ph
keywords traveling salesman problemquantum phase estimationGrover algorithmamplitude amplificationquantum computingcombinatorial optimization
0
0 comments X

The pith

Encoding TSP route costs as quantum phases allows iterative use of phase estimation and Grover-Long amplification to identify the shortest route.

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

The paper develops a quantum iterative framework for the traveling salesman problem that encodes the costs of possible routes as phases in a quantum register. Quantum phase estimation evaluates these costs while the Grover-Long algorithm supplies amplitude amplification to iteratively shrink the solution space toward the optimal tour. A small-scale demonstration confirms the method recovers the correct route, and an expectation-based analysis yields the complexity bound O(m² log₂(m) log₂(1/ε) / √ε) that depends on the target error tolerance ε. The work positions this combination as an alternative to quantum annealing for combinatorial optimization.

Core claim

By encoding the costs of routes in the traveling salesman problem as quantum phases, quantum phase estimation can evaluate them directly, and repeated application of the Grover-Long amplitude-amplification procedure refines the state until the shortest route is isolated, producing the stated complexity under an expectation analysis that treats initialization as subdominant.

What carries the argument

Encoding of TSP route costs as quantum phases, integrated with quantum phase estimation and iterated Grover-Long amplitude amplification.

If this is right

  • The method scales with the square of the number of cities while the error tolerance enters only through the square-root denominator.
  • The same phase-encoding and iterative amplification steps apply to other route-selection problems once costs are represented as phases.
  • Future circuit optimizations are expected to render the omitted initialization term negligible relative to phase estimation.
  • The approach supplies a non-annealing quantum pathway for NP-hard combinatorial tasks whose complexity can be tuned via ε.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same phase-encoding strategy could be tested on other permutation-based problems such as the assignment problem or the quadratic assignment problem.
  • Hardware runs would reveal whether decoherence limits the number of safe amplification iterations below the theoretical schedule.
  • Choosing ε adaptively during iteration might reduce the overall cost below the worst-case bound given in the paper.

Load-bearing premise

Route costs can be encoded as quantum phases so that phase estimation evaluates them efficiently and the amplification iterations do not let initialization dominate the total cost.

What would settle it

A direct count of quantum gates on a simulator for a known TSP instance with m cities that exceeds the O(m² log₂(m) log₂(1/ε) / √ε) bound while still recovering the optimal route, or failure to recover the optimal route within that resource budget.

Figures

Figures reproduced from arXiv: 2606.11843 by Arturo Rodr\'iguez-Almaz\'an, Daniela Falc\'o, Guillermo Rivas, Mir Amir Hosseini, Ricardo S. Alonso.

Figure 1
Figure 1. Figure 1: Schematic diagram representing the quantum circuit to perform Quantum Phase Esti [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Schematic diagram representing the quantum circuit to perform the Grover-Long algo [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Map presenting the four towns of Salamanca we are using as toy model and the shortest [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original abstract

The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of $O(\frac{m^2\log_2(m)\log_2(1/\epsilon)}{\sqrt{\epsilon}})$ which depends on the error tolerance parameter $\epsilon$. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper proposes a quantum iterative framework for the TSP that encodes route costs as quantum phases for evaluation via Quantum Phase Estimation (QPE) and uses Grover-Long amplitude amplification to iteratively refine the solution space toward the optimal route. It reports a proof-of-concept demonstration on a small-scale instance and, under an expectation-based analysis, claims an expected complexity of O(m² log₂(m) log₂(1/ε)/√ε) that depends on the error tolerance ε, while omitting the initialization term as expected to become subdominant.

Significance. If the complexity derivation can be supplied and the initialization costs shown to be subdominant with an efficient phase-encoding oracle, the work would provide a concrete quantum heuristic for an NP-hard combinatorial problem that combines standard QPE and amplitude amplification in a new iterative setting. The proof-of-concept, if detailed, would at minimum establish basic feasibility.

major comments (2)
  1. [Abstract] Abstract, final sentence: the central claim of expected complexity O(m² log₂(m) log₂(1/ε)/√ε) is presented without any derivation steps, assumptions, or error analysis for the expectation-based analysis. This directly undermines verification of the claim that the omitted initialization term (preparing superposition over routes and implementing the cost unitary for QPE) remains subdominant.
  2. [Abstract] Abstract: the assumptions that route costs can be encoded as phases allowing efficient QPE and that Grover-Long iterations can be performed without initialization dominating are stated but unsupported by any circuit, gate-count, or query-complexity argument. Standard TSP permutation encodings typically require Ω(m² log m) gates per oracle call, which when multiplied by QPE and amplification iterations can dominate the stated bound.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major comment below and will revise the manuscript accordingly to improve clarity and support for the claims.

read point-by-point responses

  1. Referee: [Abstract] Abstract, final sentence: the central claim of expected complexity O(m² log₂(m) log₂(1/ε)/√ε) is presented without any derivation steps, assumptions, or error analysis for the expectation-based analysis. This directly undermines verification of the claim that the omitted initialization term (preparing superposition over routes and implementing the cost unitary for QPE) remains subdominant.

    Authors: We agree that the abstract states the complexity bound without derivation steps or explicit assumptions. The expectation-based analysis, including conditions under which the initialization term is subdominant, appears in Section 4 of the main text. In the revision we will update the abstract to reference the key assumptions and point to the detailed analysis and error bounds in the main body. revision: yes

  2. Referee: [Abstract] Abstract: the assumptions that route costs can be encoded as phases allowing efficient QPE and that Grover-Long iterations can be performed without initialization dominating are stated but unsupported by any circuit, gate-count, or query-complexity argument. Standard TSP permutation encodings typically require Ω(m² log m) gates per oracle call, which when multiplied by QPE and amplification iterations can dominate the stated bound.

    Authors: The framework assumes an efficient phase-encoding oracle, a standard modeling choice in quantum combinatorial optimization. We acknowledge that the manuscript does not supply explicit gate counts or circuit arguments for the TSP oracle. In the revision we will add a discussion of oracle complexity, explain the iterative amortization that is expected to keep initialization subdominant, and note the conditions required for the stated scaling to hold. revision: yes

Circularity Check

0 steps flagged

No circularity; complexity bound asserted without exhibited derivation chain

full rationale

The paper states an expected complexity O(m² log₂(m) log₂(1/ε)/√ε) under 'expectation-based analysis' and notes omission of the initialization term (abstract). No equations, self-citations, fitted parameters, or ansatzes are quoted that reduce this bound to its inputs by construction. The claim is presented as an analysis result rather than a self-referential loop, and the provided text contains no load-bearing steps matching the enumerated circularity patterns. The derivation details are omitted, but absence of a shown reduction means no circularity is exhibited.

Axiom & Free-Parameter Ledger

1 free parameters · 0 axioms · 0 invented entities

Only the abstract is available, so the ledger is populated from stated elements only. The complexity formula introduces epsilon as a free parameter whose value is chosen by the user. No explicit axioms or invented entities are named.

free parameters (1)
  • epsilon
    Error tolerance parameter appearing in the stated complexity bound; its value controls the scaling and is not derived from first principles.

pith-pipeline@v0.9.1-grok · 5737 in / 1240 out tokens · 8114 ms · 2026-06-27T09:53:51.266868+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 6 linked inside Pith

  1. [1]

    Merrill M. Flood. The Traveling-Salesman Problem.Operations Research, 4(1):61–75, 1956. Publisher: INFORMS

    1956

  2. [2]

    Quantum mechanics helps in searching for a needle in a haystack.Physical review letters, 79(2):325, 1997

    Lov K Grover. Quantum mechanics helps in searching for a needle in a haystack.Physical review letters, 79(2):325, 1997

    1997

  3. [3]

    Quantum measurements and the abelian stabilizer problem.arXiv preprint quant-ph/9511026, 1995

    A Yu Kitaev. Quantum measurements and the abelian stabilizer problem.arXiv preprint quant-ph/9511026, 1995

    Pith/arXiv arXiv 1995

  4. [4]

    Branch and bound methods for the traveling salesman problem

    Egon Balas and Paolo Toth. Branch and bound methods for the traveling salesman problem. 1983

    1983

  5. [5]

    Dynamic Programming Treatment of the Travelling Salesman Problem.J

    Richard Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem.J. ACM, 9(1):61–63, January 1962

    1962

  6. [6]

    A dynamic programming approach to sequencing prob- lems.Journal of the Society for Industrial and Applied mathematics, 10(1):196–210, 1962

    Michael Held and Richard M Karp. A dynamic programming approach to sequencing prob- lems.Journal of the Society for Industrial and Applied mathematics, 10(1):196–210, 1962

    1962

  7. [7]

    An effective heuristic algorithm for the traveling-salesman problem.Operations research, 21(2):498–516, 1973

    Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling-salesman problem.Operations research, 21(2):498–516, 1973. 11

    1973

  8. [8]

    Quantum annealing of the traveling- salesman problem.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(5):057701, 2004

    Roman Martoňák, Giuseppe E Santoro, and Erio Tosatti. Quantum annealing of the traveling- salesman problem.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(5):057701, 2004

    2004

  9. [9]

    Adapting the traveling salesman problem to an adiabatic quantum com- puter.Quantum information processing, 12(4):1781–1785, 2013

    Richard H Warren. Adapting the traveling salesman problem to an adiabatic quantum com- puter.Quantum information processing, 12(4):1781–1785, 2013

    2013

  10. [10]

    Solving the travelling salesman problem using a single qubit.arXiv preprint arXiv:2407.17207, 2024

    Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, and Rick Mukherjee. Solving the travelling salesman problem using a single qubit.arXiv preprint arXiv:2407.17207, 2024

    arXiv 2024

  11. [11]

    Efficient quantum algorithm for solving travelling salesman problem: An ibm quantum experience

    Karthik Srinivasan, Saipriya Satyajit, Bikash K Behera, and Prasanta K Panigrahi. Efficient quantum algorithm for solving travelling salesman problem: An ibm quantum experience. arXiv preprint arXiv:1805.10928, 2018

    Pith/arXiv arXiv 2018

  12. [12]

    P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, November 1994

    1994

  13. [13]

    Cambridge university press, 2010

    Michael A Nielsen and Isaac L Chuang.Quantum computation and quantum information. Cambridge university press, 2010

    2010

  14. [14]

    An approximate fourier transform useful in quantum factoring.arXiv preprint quant-ph/0201067, 2002

    Don Coppersmith. An approximate fourier transform useful in quantum factoring.arXiv preprint quant-ph/0201067, 2002

    Pith/arXiv arXiv 2002

  15. [15]

    Lov K. Grover. A fast quantum mechanical algorithm for database search. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96, pages 212–219, Philadelphia, Pennsylvania, United States, 1996. ACM Press

    1996

  16. [16]

    Grover algorithm with zero theoretical failure rate.Physical Review A, 64(2):022307, 2001

    Gui-Lu Long. Grover algorithm with zero theoretical failure rate.Physical Review A, 64(2):022307, 2001

    2001

  17. [17]

    Quantum computers can search rapidly by using almost any transformation

    Lov K Grover. Quantum computers can search rapidly by using almost any transformation. Physical Review Letters, 80(19):4329, 1998

    1998

  18. [18]

    A quantum algorithm for finding the minimum.arXiv preprint quant-ph/9607014, 1996

    Christoph Durr and Peter Hoyer. A quantum algorithm for finding the minimum.arXiv preprint quant-ph/9607014, 1996

    Pith/arXiv arXiv 1996

  19. [19]

    Creating superpositions that correspond to efficiently inte- grable probability distributions.arXiv preprint quant-ph/0208112, 2002

    Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently inte- grable probability distributions.arXiv preprint quant-ph/0208112, 2002

    Pith/arXiv arXiv 2002

  20. [20]

    Wenjie Liu, Qingshan Wu, Jiahao Shen, Jiaojiao Zhao, Mohammed Zidan, and Lian Tong. An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq.Journal of Ambient Intelligence and Humanized Computing, 12(11):10425–10434, November 2021

    2021

  21. [21]

    Tight bounds for quantum phase estimation and related problems.arXiv preprint arXiv:2305.04908, 2023

    Nikhil S Mande and Ronald de Wolf. Tight bounds for quantum phase estimation and related problems.arXiv preprint arXiv:2305.04908, 2023

    Pith/arXiv arXiv 2023

  22. [22]

    Multiphase matching in the grover algorithm.Physical Review A—Atomic, Molecular, and Optical Physics, 77(4):042324, 2008

    FM Toyama, W Van Dijk, Y Nogami, M Tabuchi, and Y Kimura. Multiphase matching in the grover algorithm.Physical Review A—Atomic, Molecular, and Optical Physics, 77(4):042324, 2008

    2008

  23. [23]

    F. M. Toyama, W. van Dijk, and Y. Nogami. Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters.Quantum Information Processing, 12(5):1897–1914, May 2013

    1914

  24. [24]

    Scatteringbyafiniteperiodicpotential.American Journal of Physics, 61(12):1118–1124, December 1993

    D.W.L.Sprung, HuaWu, andJ.Martorell. Scatteringbyafiniteperiodicpotential.American Journal of Physics, 61(12):1118–1124, December 1993. 12

    1993