pith. machine review for the scientific record. sign in

arxiv: 2604.24297 · v1 · submitted 2026-04-27 · 🪐 quant-ph

Recognition: unknown

Exhaustive and feasible parametrisation with applications to the travelling salesperson problem

Authors on Pith no claims yet

Pith reviewed 2026-05-08 04:15 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum circuitstravelling salesperson problemcombinatorial optimizationgroup actionsfeasible solutionsparametrised circuitsquantum optimizationgenerating sequences
0
0 comments X

The pith

Exhaustively parametrised quantum circuits reach every feasible solution to constrained problems like the travelling salesperson problem with a fixed number of parameters.

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

The paper introduces quantum circuits that can produce any feasible solution to certain combinatorial optimisation tasks exactly, including the global optimum, by setting a fixed collection of parameters to the right values. These circuits are built so they remain inside the feasible subspace at every step and never generate invalid outputs. The construction begins with a group that acts transitively on the feasible solutions, then uses unitary representations of group elements together with a fixed generating sequence to create the circuit. The authors carry this out for the travelling salesperson problem and test the resulting circuits numerically on instances with up to nine cities, comparing their behaviour during parameter optimisation to standard mixers.

Core claim

By taking a transitive group action on the set of feasible solutions, choosing a generating sequence of group elements, and representing each element by a unitary operator, one obtains a parametrised quantum circuit whose reachable states are exactly the feasible solutions. For any feasible solution there exists a choice of the fixed number of parameters that maps the initial state to that solution with certainty. The same circuit never produces an infeasible state, in contrast to conventional quantum alternating operator ansatzes whose reach is only guaranteed asymptotically.

What carries the argument

The abstract pipeline that converts a transitive group action on the feasible set, together with a generating sequence, into a feasibility-respecting parametrised quantum circuit via unitary representations of the group elements.

If this is right

  • Every feasible solution is reachable with certainty for some choice of the fixed parameters.
  • The circuit produces only feasible states for any parameter values.
  • A fixed number of parameters suffices to cover the entire feasible set exactly.
  • Concrete constructions exist for the travelling salesperson problem and can be compared numerically to established quantum mixers on small instances.

Where Pith is reading between the lines

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

  • The same pipeline may apply directly to other combinatorial problems whose feasible sets carry a transitive group action, such as certain scheduling or routing tasks.
  • Removing the need for penalty terms to enforce feasibility could simplify the design of quantum optimisation algorithms on near-term hardware.
  • The notion of generating sequences might be used to derive circuit-depth bounds or to construct alternative ansatzes for symmetric constraint sets.

Load-bearing premise

The set of feasible solutions must admit a transitive group action that can be generated by a finite sequence of group elements whose unitary representations produce a circuit covering all feasible states.

What would settle it

For one of the nine-city TSP instances, optimise the parameters of the constructed circuit and check whether the output state corresponds to a feasible tour and whether the known optimal tour is recovered with high probability.

Figures

Figures reproduced from arXiv: 2604.24297 by Benjamin Sambale, Lennart Binkowski, Marvin Schwiering, Timo Ziegler.

Figure 1
Figure 1. Figure 1: High-level overview of our abstract pipeline for constructing exhaustively parametrised, feasibility-respecting quantum circuits for combinatorial view at source ↗
Figure 2
Figure 2. Figure 2: Abstract pipeline for constructing an exhaustively parametrised, feasibility-respecting quantum circuit from a transitive group action on the feasible view at source ↗
Figure 3
Figure 3. Figure 3: Implementation of e−iθU , where U is a Hermitian unitary. level, and by reorganising the iterations i 7→ n−i, bubble sort is able to apply all the permutations nY−1 i=1  τ bi,i i ◦ · · · ◦ τ bi,1 1  , (3) where τi := τi,i+1 is an adjacency transposition, and the bits bi,j , i ∈ [n − 1] and j ∈ [i], determines whether two neighbouring elements j and j + 1 are swapped in the i-th iteration (bi,j = 1) or no… view at source ↗
Figure 5
Figure 5. Figure 5: Approximation ratios obtained after each COBYLA iteration, using view at source ↗
read the original abstract

This paper introduces the concept of exhaustively parametrised, feasibility-respecting quantum circuits for constrained combinatorial optimisation problems. Such circuits can reach, given the right parameter values, every feasible solution with certainty -- including the optimum -- with a fixed number of parameters, while avoiding infeasible solutions altogether. This is in sharp contrast to conventional quantum alternating operator ansatz schemes, which are merely guaranteed to reach the optimum asymptotically. We introduce an abstract pipeline for constructing exhaustively parametrised, feasibility-respecting circuits from a transitive group action on a problem's feasible set. Our constructions rely on the simple combination of the group action with group representation and the novel notion of generating sequences: group elements in fixed order, possibly with repetitions, that generate the entire group. That is, we trace expressivity of parametrised quantum circuits back to the most fundamental concepts of group theory. We apply this pipeline to two concrete examples for the travelling salesperson problem, thus showing that exhaustively parametrised, feasibility-respecting circuits are not an empty definition. Furthermore, we provide numerical proof-of-principles on instances with up to nine cities, comparing the suitability of our constructions for parameter optimisation purposes against established mixers.

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

1 major / 2 minor

Summary. The paper introduces exhaustively parametrised, feasibility-respecting quantum circuits for constrained combinatorial optimisation problems such as the travelling salesperson problem (TSP). These circuits are constructed via an abstract pipeline based on transitive group actions on the feasible set, combined with group representations and generating sequences, allowing them to reach every feasible solution with a fixed number of parameters while avoiding infeasible ones. Two concrete constructions for TSP are presented, and numerical proof-of-principles are provided for instances with up to nine cities, comparing against standard mixers.

Significance. If the constructions and numerical results hold, this represents a meaningful contribution to variational quantum algorithms by grounding circuit expressivity in group theory to achieve exact coverage of the feasible subspace with a bounded number of parameters. This contrasts with standard QAOA-style ansatzes and could improve trainability for combinatorial problems; the explicit TSP examples and small-scale numerical validation are strengths that demonstrate the framework is not merely formal.

major comments (1)
  1. Numerical Experiments section: the proof-of-principles on instances up to nine cities are central to supporting the claim of suitability for parameter optimisation, yet the manuscript provides insufficient details on the specific TSP instances used, the classical optimiser, number of runs, success probabilities, or error bars; without these, the comparison to established mixers cannot be rigorously assessed or reproduced.
minor comments (2)
  1. The definition and role of generating sequences would benefit from a short concrete example immediately after their introduction to improve accessibility for readers less familiar with the group-theoretic construction.
  2. Notation for the group action and representations should be consistently defined with explicit mappings to the TSP feasible set (e.g., permutations of cities) in the pipeline description.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment of the significance of our work and for the constructive feedback. We address the major comment below and will revise the manuscript to incorporate the requested details.

read point-by-point responses
  1. Referee: Numerical Experiments section: the proof-of-principles on instances up to nine cities are central to supporting the claim of suitability for parameter optimisation, yet the manuscript provides insufficient details on the specific TSP instances used, the classical optimiser, number of runs, success probabilities, or error bars; without these, the comparison to established mixers cannot be rigorously assessed or reproduced.

    Authors: We agree that the Numerical Experiments section requires additional details to support reproducibility and rigorous comparison. In the revised manuscript we will expand this section to specify the exact TSP instances (including distance matrices or city coordinates for all cases up to nine cities), the classical optimizer and its hyperparameters, the number of independent optimization runs, the observed success probabilities together with error bars or standard deviations, and the simulation methodology (exact state-vector or otherwise). These additions will allow the community to fully assess and reproduce the reported comparisons against standard mixers. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation grounded in standard group theory

full rationale

The paper defines exhaustively parametrised circuits via an abstract pipeline that combines a transitive group action on the feasible set with group representations and generating sequences. These are standard, externally verifiable group-theoretic primitives with no reduction to fitted parameters or self-referential definitions. Explicit TSP constructions are given as realizations, and numerical experiments are presented separately as validation rather than as part of the derivation. No load-bearing step collapses to a self-citation, ansatz smuggling, or renaming of a known result; the central claim follows directly from the stated assumptions without circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claim rests on group-theoretic assumptions and newly introduced concepts; no free parameters are apparent from the abstract.

axioms (2)
  • domain assumption Existence of a transitive group action on the feasible set of the optimization problem.
    The abstract pipeline starts from a transitive group action on the problem's feasible set.
  • domain assumption Group representation theory can be combined with the group action to construct quantum circuits.
    Relies on the combination of the group action with group representation.
invented entities (2)
  • Exhaustively parametrised, feasibility-respecting quantum circuits no independent evidence
    purpose: To reach every feasible solution with certainty using a fixed number of parameters while avoiding infeasible solutions.
    New concept introduced in the paper.
  • Generating sequences no independent evidence
    purpose: Group elements in fixed order, possibly with repetitions, that generate the entire group.
    Novel notion introduced to trace expressivity of the circuits.

pith-pipeline@v0.9.0 · 5511 in / 1527 out tokens · 39749 ms · 2026-05-08T04:15:43.866514+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

44 extracted references · 36 canonical work pages · 2 internal anchors

  1. [1]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” 2014, [arXiv preprint arXiv:1411.4028]

  2. [2]

    From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

    S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelliet al., “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz,”Algorithms, vol. 12, no. 2, p. 34, 2019. [Online]. Available: https://doi.org/10.3390/a12020034

  3. [3]

    Direct search algorithms for optimization calculations,

    M. J. D. Powell, “Direct search algorithms for optimization calculations,”Acta Numer., vol. 7, pp. 287–336, 1998. [Online]. Available: https://doi.org/10.1017/s0962492900002841

  4. [4]

    Algorithm 733: TOMP–Fortran modules for optimal control calculations,

    D. Kraft, “Algorithm 733: TOMP–Fortran modules for optimal control calculations,”ACM Trans. Math. Softw., vol. 20, no. 3, pp. 262–281,

  5. [5]

    Available: https://doi.org/10.1145/192115.192124

    [Online]. Available: https://doi.org/10.1145/192115.192124

  6. [6]

    A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack,

    A. Agirre, E. van Nieuwenburg, and M. M. Wauters, “A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack,” New J. Phys., vol. 27, no. 4, p. 043014, 2025. [Online]. Available: https://doi.org/10.1088/1367-2630/adc765

  7. [7]

    Fixed-angle conjectures for the quantum approximate optimiza- tion algorithm on regular MaxCut graphs

    J. Wurtz and D. Lykov, “Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs,”Phys. Rev., vol. 104, no. 5, 2021. [Online]. Available: https://doi.org/10.1103/physreva.104.052419

  8. [8]

    Quantum Computation by Adiabatic Evolution

    E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum Computation by Adiabatic Evolution,” 2000, [arXiv preprint arXiv:quant-ph/0001106]

  9. [9]

    Elementary proof of QAOA convergence,

    L. Binkowski, G. Koßmann, T. Ziegler, and R. Schwonnek, “Elementary proof of QAOA convergence,”New J. Phys., vol. 26, no. 7, p. 073001, 2024. [Online]. Available: https://doi.org/10.1088/1367-2630/ad59bb

  10. [10]

    Applegate, Robert E

    D. L. Applegate, R. E. Bixby, V . Chvátal, W. Cook, D. G. Espinoza et al., “Certification of an optimal TSP tour through 85,900 cities,” Oper. Res. Lett., vol. 37, no. 1, pp. 11–15, 2009. [Online]. Available: https://doi.org/10.1016/j.orl.2008.09.006

  11. [11]

    Dantzig, D

    G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a Large-Scale Traveling-Salesman Problem,”J. Oper. Res. Soc. Am., vol. 2, no. 4, pp. 393–410, 1954. [Online]. Available: https://doi.org/10.1287/opre.2.4.393

  12. [12]

    Cutting planes in integer and mixed integer programming,

    H. Marchand, A. Martin, R. Weismantel, and L. Wolsey, “Cutting planes in integer and mixed integer programming,”Discret. Appl. Math., vol. 123, no. 1-3, pp. 397–446, 2002. [Online]. Available: https://doi.org/10.1016/s0166-218x(01)00348-1

  13. [13]

    An Automatic Method of Solving Discrete Programming Problems,

    A. H. Land and A. G. Doig, “An Automatic Method of Solving Discrete Programming Problems,”Econometrica, vol. 28, no. 3, p. 497, 1960. [Online]. Available: https://doi.org/10.2307/1910129

  14. [14]

    Dynamic Programming Treatment of the Travelling Salesman Problem,

    R. Bellman, “Dynamic Programming Treatment of the Travelling Salesman Problem,”J. ACM, vol. 9, no. 1, pp. 61–63, 1962. [Online]. Available: https://doi.org/10.1145/321105.321111

  15. [15]

    A Dynamic Programming Approach to Sequencing Problems,

    M. Held and R. M. Karp, “A Dynamic Programming Approach to Sequencing Problems,”J. Soc. Ind. Appl. Math., vol. 10, no. 1, pp. 196–210, 1962. [Online]. Available: https://doi.org/10.1137/0110015

  16. [16]

    The unconstrained binary quadratic programming problem: a survey,

    G. Kochenberger, J. Hao, F. Glover, M. Lewis, Z. Lüet al., “The unconstrained binary quadratic programming problem: a survey,”J. Comb. Optim., vol. 28, no. 1, pp. 58–81, 2014. [Online]. Available: https://doi.org/10.1007/s10878-014-9734-0

  17. [17]

    “Neural” computation of decisions in optimization problems,

    J. J. Hopfield and D. W. Tank, ““Neural” computation of decisions in optimization problems,”Biol. Cybern., vol. 52, no. 3, pp. 141–152,

  18. [18]
  19. [19]

    Ising formulations of many NP problems

    A. Lucas, “Ising formulations of many NP problems,”Front. Phys., vol. 2, p. 5, 2014. [Online]. Available: https://doi.org/10.3389/fphy.2014.00005

  20. [20]

    Adapting the traveling salesman problem to an adiabatic quantum computer,

    R. H. Warren, “Adapting the traveling salesman problem to an adiabatic quantum computer,”Quantum Inf. Process., vol. 12, no. 4, pp. 1781–1785, 2012. [Online]. Available: https://doi.org/10.1007/s11128-012-0490-8

  21. [21]

    Space-efficient binary optimization for variational computing,

    A. Glos, A. Krawiec, and Z. Zimborás, “Space-efficient binary optimization for variational computing,” 2020, [arXiv preprint arXiv:2009.07309]

  22. [22]

    The travelling salesperson problem and the challenges of near-term quantum advantage,

    K. A. Smith-Miles, H. H. Hoos, H. Wang, T. Bäck, and T. J. Osborne, “The travelling salesperson problem and the challenges of near-term quantum advantage,”Quantum Sci. Technol., vol. 10, no. 3, p. 033001,

  23. [23]

    Available: https://doi.org/10.1088/2058-9565/add61d

    [Online]. Available: https://doi.org/10.1088/2058-9565/add61d

  24. [24]

    The Quantum Approximate Algorithm for Solving Traveling Salesman Problem,

    Y . Ruan, S. Marsh, X. Xue, Z. Liu, and J. Wang, “The Quantum Approximate Algorithm for Solving Traveling Salesman Problem,” Comput. Mater. & Contin., vol. 63, no. 3, pp. 1237–1247, 2020. [Online]. Available: https://doi.org/10.32604/cmc.2020.010001

  25. [25]

    Symmetry-based quantum algorithms for open-shop scheduling with hard constraints,

    L. Binkowski, G. Koßmann, C. Tutschku, and R. Schwonnek, “Symmetry-based quantum algorithms for open-shop scheduling with hard constraints,”Acad. Quantum, vol. 2, no. 3, 2025. [Online]. Available: https://doi.org/10.20935/acadquant7900

  26. [26]

    Classical symmetries and the Quantum Approximate Optimization Algorithm,

    R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro, “Classical symmetries and the Quantum Approximate Optimization Algorithm,” Quantum Inf. Process., vol. 20, no. 11, 2021. [Online]. Available: https://doi.org/10.1007/s11128-021-03298-4

  27. [27]

    Santoro, and Erio Tosatti

    R. Marto ˇnák, G. E. Santoro, and E. Tosatti, “Quantum annealing of the traveling-salesman problem,”Phys. Rev., vol. 70, no. 5, 2004. [Online]. Available: https://doi.org/10.1103/physreve.70.057701

  28. [28]

    Solving the traveling salesman problem on a quantum annealer,

    R. H. Warren, “Solving the traveling salesman problem on a quantum annealer,”SN Appl. Sci., vol. 2, no. 1, 2019. [Online]. Available: https://doi.org/10.1007/s42452-019-1829-x

  29. [29]

    Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution,

    Y . Chen and P. Zhang, “Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution,”Phys. A: Stat. Mech. its Appl., vol. 371, no. 2, pp. 627–632, 2006. [Online]. Available: https://doi.org/10.1016/j.physa.2006.04.052

  30. [30]

    Solving the travelling salesman problem using Bloch sphere encoding,

    K. Goswami, G. Anekonda Veereshi, P. Schmelcher, and R. Mukherjee, “Solving the travelling salesman problem using Bloch sphere encoding,”Quantum Sci. Technol., vol. 11, no. 1, p. 015007,

  31. [31]

    Available: https://doi.org/10.1088/2058-9565/ae1e9a

    [Online]. Available: https://doi.org/10.1088/2058-9565/ae1e9a

  32. [32]

    A fast quantum mechanical algorithm for database search

    L. K. Grover, “A fast quantum mechanical algorithm for database search,” 1996, [arXiv preprint arXiv:quant-ph/9605043]

  33. [33]

    Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems,

    R. Sato, C. Gordon, K. Saito, H. Kawashima, T. Nikuniet al., “Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems,”IEEE Trans. Quantum Eng., vol. 6, pp. 1–12, 2025. [Online]. Available: https://doi.org/10.1109/tqe.2025.3548706

  34. [34]

    A quantum heuristic algorithm for the traveling salesman problem,

    J. Bang, J. Ryu, C. Lee, S. Yoo, J. Limet al., “A quantum heuristic algorithm for the traveling salesman problem,”J. Korean Phys. Soc., vol. 61, no. 12, pp. 1944–1949, 2012. [Online]. Available: https://doi.org/10.3938/jkps.61.1944

  35. [35]

    Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation,

    A. Bartschi and S. Eidenbenz, “Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation,” in2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 2020, pp. 72–82. [Online]. Available: https://doi.org/10.1109/qce49297.2020.00020

  36. [36]

    Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations,

    L. Binkowski and M. Schwiering, “Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations,” 2025, [arXiv preprint arXiv:2504.17965]

  37. [37]

    Grover Adaptive Search with Problem-Specific State Preparation,

    M. Hess, L. Palackal, A. Awasthi, P. J. Eder, M. Schnauset al., “Grover Adaptive Search with Problem-Specific State Preparation,” 2026, [arXiv preprint arXiv:2602.08418]

  38. [38]

    Quantum algorithms for combinatorial optimisation,

    L. Binkowski, “Quantum algorithms for combinatorial optimisation,”

  39. [39]

    Available: https://www.itp.uni-hannover.de/fileadmin/itp/qinfo/Team_Tobias_ Osborne/Doctoral_Theses/Lennart_Binkowski_Doctoral_Thesis.pdf

    [Online]. Available: https://www.itp.uni-hannover.de/fileadmin/itp/qinfo/Team_Tobias_ Osborne/Doctoral_Theses/Lennart_Binkowski_Doctoral_Thesis.pdf

  40. [40]

    Quantum Optimization Algorithms for the Traveling Salesman Problem,

    M. Schwiering, “Quantum Optimization Algorithms for the Traveling Salesman Problem,” 2024. [Online]. Available: https://www.itp.uni-hannover.de/fileadmin/itp/qinfo/Team_Tobias_ Osborne/Masters_Theses/Marvin_Schwiering_Masters_Thesis.pdf

  41. [41]

    Sorting on Electronic Computer Systems,

    E. H. Friend, “Sorting on Electronic Computer Systems,”J. ACM, vol. 3, no. 3, pp. 134–168, 1956. [Online]. Available: https://doi.org/10.1145/320831.320833

  42. [42]

    Measures of Presortedness and Optimal Sorting Algorithms,

    H. Mannila, “Measures of Presortedness and Optimal Sorting Algorithms,”IEEE Trans. Comput., vol. C-34, no. 4, pp. 318–325,

  43. [43]

    Available: https://doi.org/10.1109/tc.1985.5009382

    [Online]. Available: https://doi.org/10.1109/tc.1985.5009382

  44. [44]

    Orkan: Cache-friendly simulation of quantum operations on hermitian operators

    T. Ziegler, “Orkan: Cache-friendly simulation of quantum operations on hermitian operators,” 2026, [arXiv preprint arXiv:2604.15765]