Recognition: unknown
Exhaustive and feasible parametrisation with applications to the travelling salesperson problem
Pith reviewed 2026-05-08 04:15 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- 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)
- 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.
- 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
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
-
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
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
axioms (2)
- domain assumption Existence of a transitive group action on the feasible set of the optimization problem.
- domain assumption Group representation theory can be combined with the group action to construct quantum circuits.
invented entities (2)
-
Exhaustively parametrised, feasibility-respecting quantum circuits
no independent evidence
-
Generating sequences
no independent evidence
Reference graph
Works this paper leans on
-
[1]
A Quantum Approximate Optimization Algorithm
E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” 2014, [arXiv preprint arXiv:1411.4028]
work page internal anchor Pith review arXiv 2014
-
[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]
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]
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]
Available: https://doi.org/10.1145/192115.192124
[Online]. Available: https://doi.org/10.1145/192115.192124
-
[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]
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]
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]
work page Pith review arXiv 2000
-
[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]
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]
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]
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]
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]
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]
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]
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]
“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]
“neural” com- putation of decisions in optimization problems,
[Online]. Available: https://doi.org/10.1007/bf00339943
-
[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]
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]
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]
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]
Available: https://doi.org/10.1088/2058-9565/add61d
[Online]. Available: https://doi.org/10.1088/2058-9565/add61d
-
[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]
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]
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]
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]
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]
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]
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]
Available: https://doi.org/10.1088/2058-9565/ae1e9a
[Online]. Available: https://doi.org/10.1088/2058-9565/ae1e9a
-
[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]
work page Pith review arXiv 1996
-
[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]
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]
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]
L. Binkowski and M. Schwiering, “Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations,” 2025, [arXiv preprint arXiv:2504.17965]
-
[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]
Quantum algorithms for combinatorial optimisation,
L. Binkowski, “Quantum algorithms for combinatorial optimisation,”
-
[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]
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
2024
-
[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]
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]
Available: https://doi.org/10.1109/tc.1985.5009382
[Online]. Available: https://doi.org/10.1109/tc.1985.5009382
-
[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]
work page internal anchor Pith review Pith/arXiv arXiv 2026
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.