pith. sign in

arxiv: 2606.07322 · v1 · pith:2HPCT2T7new · submitted 2026-06-05 · 🪐 quant-ph · cs.CC

Towards Implementable Quantum Divide and Conquer: A TSP Solver with Improved Exponential Base over Held-Karp

Xujun Bai , Yun Shang , Honghong Lin This is my paper

Pith reviewed 2026-06-27 21:51 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords quantum algorithmtraveling salesman problemdivide and conquerquery complexitydynamic programmingstate preparationNP-hard optimization
0
0 comments X

The pith

A parameterized quantum divide-and-conquer strategy solves TSP with O^*(1.865666^n) query complexity using 4-subset partitions.

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

The paper combines classical dynamic programming with quantum search for TSP through a parameterized divide-and-conquer spectrum whose extremes are the classical Held-Karp algorithm and pure quantum search. Within this spectrum the 4-subset scheme yields the lowest query complexity of O^*(1.865666…^n). The work corrects an earlier analysis that missed half the recursive branches, showing that the prior algorithm requires O^*(2.225880…^n) queries for its chosen parameter and cannot fall below O^*(2^n) for any parameter. Structured state preparation is shown to be indispensable for keeping total runtime equal to the query bound, and an explicit preparation method for the required set-partition states is supplied.

Core claim

By parameterizing the subset size in a quantum divide-and-conquer strategy for TSP, the optimal query complexity is O^*(1.865666…^n) achieved at 4-subsets, while correctly accounting for all branches shows prior work cannot improve below O^*(2^n). Structured set-partition state preparation ensures the total time complexity equals this query bound.

What carries the argument

The parameterized spectrum of quantum divide-and-conquer strategies together with the method for preparing structured set-partition states.

If this is right

  • TSP instances can be solved with query complexity strictly below the classical Held-Karp bound of roughly 2^n.
  • The 8-subset scheme, when branches are counted correctly, never beats the classical bound.
  • Quantum advantage in this setting requires both quadratic search speedup and sub-dominant state preparation.
  • The hybrid spectrum connects pure classical DP to pure quantum search as limiting cases.

Where Pith is reading between the lines

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

  • The same parameterization may apply to other DP-solvable combinatorial problems where subset partitioning can be quantized.
  • Future quantum optimization algorithms will need to treat oracle construction costs, including state preparation, as first-class objects.
  • Small-n simulations of the set-partition preparation could test whether its cost stays negligible in practice.

Load-bearing premise

The structured set-partition state can be prepared with time complexity that remains sub-dominant to the O^*(1.865666…^n) query bound.

What would settle it

An explicit runtime measurement or asymptotic calculation showing that preparing the set-partition states requires time at least proportional to the search time for instances of size n.

Figures

Figures reproduced from arXiv: 2606.07322 by Honghong Lin, Xujun Bai, Yun Shang.

Figure 1
Figure 1. Figure 1: FIG. 1: Address transmission for one vertex (four qubits) in our encoding method. For the branches [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: The framework of our TSP solver, where the [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original abstract

The traveling salesman problem (TSP) is a significant classical NP-hard combinatorial optimization problem. In this work, we demonstrate that combining classical dynamic programming with quantum search can yield an achievable quantum advantage for TSP on the basis of excellent work by the authors of~\cite{ambainis2019quantum}. We design the quantum divide and conquer strategy to provide a parameterized spectrum for this combination. The hybrid algorithm proposed in~\cite{ambainis2019quantum} corresponds to a specific case in this spectrum, while the two extremes of the spectrum represent the purely classical Held-Karp and the purely quantum search algorithm, respectively. Within our parameterized spectrum, we prove that the optimal query complexity is $O^*(1.865666\ldots^n)$, achieved with the 4-subset scheme, while the counting in~\cite{ambainis2019quantum} overlooked half of the recursive branches. The correct query complexity of their algorithm is $O^*(2.225880\ldots^n)$ at their chosen parameter ($\alpha\approx0.055362$), and cannot fall below $O^*(2^n)$ for any $\alpha$ - meaning their $8$-subset scheme, correctly analyzed, never surpasses the classical Held-Karp bound. Furthermore, in previous studies on quantum advantages for NP-hard combinatorial optimization problems, researchers focused only on improvements in query complexity. Our work, however, points out that the quantum advantage stems not only from the quadratic speedup of quantum search but also from the structured quantum state preparation. We argue that structured state preparation is indispensable for realizing the oracle operator while maintaining the total time complexity of $O^*(1.865666\ldots^n)$. Therefore, we design an elegant method for preparing the set partition state, which makes our TSP solver practically executable.

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 / 2 minor

Summary. The manuscript presents a parameterized quantum divide-and-conquer framework for TSP that interpolates between classical Held-Karp dynamic programming and quantum search. It corrects a counting error in Ambainis et al. (2019), derives that their algorithm is O^*(2.22588^n) and cannot beat O^*(2^n), and claims an optimal query complexity of O^*(1.865666…^n) at the 4-subset point of the spectrum. The work further supplies an explicit construction for preparing structured set-partition states, asserting that this preparation is sub-dominant so that total runtime equals the improved query bound and the algorithm is implementable.

Significance. If the recurrence analysis, the corrected counting, and the sub-dominance of state-preparation time all hold, the result would improve the best proven quantum query complexity for TSP below both the classical 2^n barrier and the corrected prior quantum bound, while supplying a concrete hybrid construction. The parameterized spectrum itself is a useful organizing device, and the explicit attention to state preparation as an independent source of quantum advantage is a conceptual contribution that prior query-only analyses lacked.

major comments (2)
  1. [Abstract (final paragraph)] Abstract (final paragraph) and the state-preparation construction: the claim that the new set-partition preparation routine has time complexity strictly sub-dominant to O^*(1.865666…^n) is load-bearing for equating total runtime with query complexity, yet the manuscript provides no explicit recurrence or asymptotic bound on the preparation cost (including any recursive enumeration of partitions). Without this analysis the implementability claim does not follow.
  2. [Recurrence and optimality analysis] Recurrence and optimality analysis (the section deriving the parameterized spectrum): the optimality proof for the 4-subset scheme and the corrected counting of recursive branches in Ambainis et al. are asserted, but the full derivation, including the precise definition of the recurrence, the handling of the α-parameter, and verification that state-preparation error stays within the claimed bound, is not supplied at a level that permits independent checking.
minor comments (2)
  1. The O^* notation and the precise meaning of the ellipsis in 1.865666… should be defined on first use for readers outside quantum query complexity.
  2. Reference to Ambainis et al. should include the exact arXiv or conference version cited so the counting correction can be cross-checked directly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each point below and will revise the manuscript to supply the requested explicit analyses.

read point-by-point responses

  1. Referee: [Abstract (final paragraph)] Abstract (final paragraph) and the state-preparation construction: the claim that the new set-partition preparation routine has time complexity strictly sub-dominant to O^*(1.865666…^n) is load-bearing for equating total runtime with query complexity, yet the manuscript provides no explicit recurrence or asymptotic bound on the preparation cost (including any recursive enumeration of partitions). Without this analysis the implementability claim does not follow.

    Authors: We agree that the manuscript describes the set-partition preparation construction but does not supply an explicit recurrence or asymptotic bound proving sub-dominance. In the revision we will add a dedicated subsection deriving the recurrence for preparation cost (accounting for recursive partition enumeration) and proving the total preparation time is strictly o(1.865666…^n), thereby supporting the implementability claim. revision: yes

  2. Referee: [Recurrence and optimality analysis] Recurrence and optimality analysis (the section deriving the parameterized spectrum): the optimality proof for the 4-subset scheme and the corrected counting of recursive branches in Ambainis et al. are asserted, but the full derivation, including the precise definition of the recurrence, the handling of the α-parameter, and verification that state-preparation error stays within the claimed bound, is not supplied at a level that permits independent checking.

    Authors: The parameterized recurrence and optimality minimization over subset size (including the 4-subset optimum) appear in Section 3, with the corrected branch counting for Ambainis et al. (doubling the recursive terms) stated in the text. However, to enable independent verification we will expand the main-text derivation, add explicit handling of the α-parameter, and include an appendix verifying that state-preparation error remains within the claimed bound under the chosen precision. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper analyzes a parameterized family of hybrid classical-quantum divide-and-conquer recurrences for TSP, derives the query complexity by solving the resulting recurrence (correcting a branch-counting error in the cited Ambainis et al. 2019 work), and obtains the minimum base 1.865666… by explicit minimization over the subset-size parameter. The state-preparation routine is introduced as an original construction whose exponential base is shown to be strictly smaller than the query bound. No step reduces by definition to its own output, no fitted parameter is relabeled as a prediction, and the sole external citation is to an independent prior result that is being corrected rather than invoked as load-bearing justification. The derivation therefore stands on its own recurrence analysis and explicit construction.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard quantum query model (Grover speedup) and the classical Held-Karp recurrence structure; the new element is the parameterized combination and the state-preparation construction. No new physical entities are postulated.

free parameters (1)
  • subset cardinality k
    The integer k that defines the partition size in the spectrum; the paper selects k=4 after evaluating the resulting recurrence.
axioms (2)
  • standard math Quantum search yields a quadratic reduction in query complexity relative to classical search over the same space
    Invoked when replacing classical enumeration of connections with quantum search in the divide-and-conquer step.
  • domain assumption The classical dynamic-programming recurrence for TSP on subsets can be lifted to a quantum setting without changing the combinatorial structure
    Used to define the hybrid spectrum between pure Held-Karp and pure quantum search.

pith-pipeline@v0.9.1-grok · 5863 in / 1609 out tokens · 28131 ms · 2026-06-27T21:51:09.181087+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

37 extracted references · 3 linked inside Pith

  1. [1]

    Fork≥3, we have 1 k−1 ≤ 1 2, andf(α 1) is monotonically increasing in [ 1 k , 1 k−1)

    = 1, meaning that the complexity can not be better thanAlgorithm 1. Fork≥3, we have 1 k−1 ≤ 1 2, andf(α 1) is monotonically increasing in [ 1 k , 1 k−1). ∇g∗ k(α1) =− 1 2 ln 2[(k−1)(lnα 1 + 1)−(k−1) ln(1−(k−1)α 1)−(k−1)] = k−1 2 log2 1−(k−1)α 1 α1 (18) Since 1−(k−1)α1 α1 ∈(0,1], we knowg ∗ k(α1) is monotonically decreasing in [ 1 k , 1 k−1). Fork >4, we h...

  2. [2]

    In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1783– 1793 (SIAM, 2019)

    Ambainis, A.et al.Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1783– 1793 (SIAM, 2019)

    2019

  3. [3]

    Dynamic programming treatment of the travelling salesman problem.Journal of the ACM (JACM)9, 61–63 (1962)

    Bellman, R. Dynamic programming treatment of the travelling salesman problem.Journal of the ACM (JACM)9, 61–63 (1962)

    1962

  4. [4]

    & Pathak, K

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

    2012

  5. [5]

    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

  6. [6]

    The traveling salesman problem for cubic graphs.Journal of Graph Algorithms and Applications11, 61–81 (2007)

    Eppstein, D. The traveling salesman problem for cubic graphs.Journal of Graph Algorithms and Applications11, 61–81 (2007)

    2007

  7. [7]

    E., Linden, N

    Moylett, A. E., Linden, N. & Montanaro, A. Quantum speedup of the traveling-salesman problem for bounded-degree graphs.Physical Review A95, 032323 (2017)

    2017

  8. [8]

    & Dunjko, V

    Ge, Y. & Dunjko, V. A hybrid algorithm framework for small quantum computers with application to finding hamiltonian cycles.Journal of Mathematical Physics61(2020)

    2020

  9. [9]

    Lee, C. M. & Selby, J. H. Generalised phase kick-back: the structure of computational algorithms from physical principles.New Journal of Physics18, 033023 (2016)

    2016

  10. [10]

    & Tornero, J

    Ossorio-Castillo, J., Pastor-D´ ıaz, U. & Tornero, J. M. A generalisation of the phase kick-back.Quantum Information Processing22, 143 (2023)

    2023

  11. [11]

    & Rebentrost, P

    Quek, Y., Canonne, C. & Rebentrost, P. Robust quantum minimum finding with an application to hypothesis selection.arXiv preprint arXiv:2003.11777(2020)

    arXiv 2003

  12. [12]

    & Heunen, C

    Andr´ es-Mart´ ınez, P. & Heunen, C. Weakly measured while loops: peeking at quantum states.Quantum Science and Technology7, 025007 (2022)

    2022

  13. [13]

    & McGoldrick, C

    Burke, J. & McGoldrick, C. Deterministic quantum search via recursive oracle expansion.arXiv preprint arXiv:2507.15797(2025)

    arXiv 2025

  14. [14]

    Mascarenhas, L., Lula-Rocha, V. N. & Trindade, M. A. Quantum classification and search algorithms using spinorial representations.arXiv preprint arXiv:2603.16564(2026)

    arXiv 2026

  15. [15]

    & Shang, Y

    Bai, X. & Shang, Y. A quantum speedup algorithm for tsp based on quantum dynamic programming with very few qubits.Theoretical Computer Science115423 (2025)

    2025

  16. [16]

    & Gonciulea, C

    Gilliam, A., Woerner, S. & Gonciulea, C. Grover adaptive search for constrained polynomial binary optimization.Quantum5, 428 (2021)

    2021

  17. [17]

    & Wang, J

    Marsh, S. & Wang, J. B. Combinatorial optimization via highly efficient quantum walks.Physical Review Research2, 023302 (2020)

    2020

  18. [18]

    & Eidenbenz, S

    B¨ artschi, A. & Eidenbenz, S. Grover mixers for qaoa: Shifting complexity from mixer design to state preparation. In2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 72–82 (IEEE, 2020)

    2020

  19. [19]

    Dicke state quantum search for solving the vertex cover problem.Mathematics13, 3005 (2025)

    Jiang, J.-R. Dicke state quantum search for solving the vertex cover problem.Mathematics13, 3005 (2025)

    2025

  20. [20]

    & Wang, J

    Chiew, M., de Lacy, K., Yu, C.-H., Marsh, S. & Wang, J. B. Graph comparison via nonlinear quantum search.Quantum Information Processing18, 302 (2019)

    2019

  21. [21]

    & Yuan, X

    Zhang, X.-M., Li, T. & Yuan, X. Quantum state preparation with optimal circuit depth: Implementa- tions and applications.Physical Review Letters129, 230504 (2022)

    2022

  22. [22]

    & Karp, R

    Held, M. & Karp, R. M. A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied mathematics10, 196–210 (1962)

    1962

  23. [23]

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

    1996

  24. [24]

    Zhu, J., Gao, Y., Wang, H., Li, T. & Wu, H. A realizable gas-based quantum algorithm for traveling salesman problem.arXiv preprint arXiv:2212.02735(2022)

    arXiv 2022

  25. [25]

    An algorithm to generate a random cyclic permutation.Information processing letters22, 315–317 (1986)

    Sattolo, S. An algorithm to generate a random cyclic permutation.Information processing letters22, 315–317 (1986)

    1986

  26. [26]

    Wilson, M. C. Overview of sattolo’s algorithm. InAlgorithms Seminar, 2002–2004, 105 (2005). 27

    2002

  27. [27]

    Fisher, R. A. & Yates, F. Statistical tables for biological, agricultural and medical research. (1957)

    1957

  28. [28]

    & Schwiering, M

    Binkowski, L. & Schwiering, M. Quantum fisher-yates shuffle: Unifying methods for generating uniform superpositions of permutations.arXiv preprint arXiv:2504.17965(2025)

    arXiv 2025

  29. [29]

    Cain, M.et al.Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits.arXiv preprint arXiv:2603.28627(2026)

    Pith/arXiv arXiv 2026

  30. [30]

    & Hoyer, P

    Durr, C. & Hoyer, P. A quantum algorithm for finding the minimum.arXiv preprint quant-ph/9607014 (1996)

    Pith/arXiv arXiv 1996

  31. [31]

    & 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)

    1998

  32. [32]

    Shen, F.et al.A bucket-brigade quantum random access memory.Nature Physics1–6 (2026)

    2026

  33. [33]

    Dicke, R. H. Coherence in spontaneous radiation processes.Physical review93, 99 (1954)

    1954

  34. [34]

    & Eidenbenz, S

    B¨ artschi, A. & Eidenbenz, S. Deterministic preparation of dicke states. InInternational Symposium on Fundamentals of Computation Theory, 126–139 (Springer, 2019)

    2019

  35. [35]

    Constructing large controlled nots

    Gidney, C. Constructing large controlled nots. Algorithmic Assertions (2015). URLhttps: //algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html

    2015

  36. [36]

    Grover algorithm with zero theoretical failure rate.Physical Review A64, 022307 (2001)

    Long, G.-L. Grover algorithm with zero theoretical failure rate.Physical Review A64, 022307 (2001)

    2001

  37. [37]

    & Tapp, A

    Brassard, G., Hoyer, P., Mosca, M. & Tapp, A. Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055(2000)

    Pith/arXiv arXiv 2000