Exhaustive and feasible parametrisation with applications to the travelling salesperson problem

Authors: Marvin Schwiering, Timo Ziegler, Lennart Binkowski, Benjamin Sambale · arXiv:2604.24297 · submission cycle 2026-04-28 · score 9/10 (HIGH)

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.

Executive summary

This is a structural advance over the QAOA / quantum alternating operator ansatz (QAOA-AO) for hard-constrained combinatorial problems. The authors define a parametrised quantum circuit as exhaustively parametrised if every feasible solution can be reached exactly at some parameter value with a fixed number of parameters, and feasibility-respecting if it never produces an infeasible state. They then give a clean group-theoretic recipe: given a transitive group action of G on the feasible set F, plus a generating sequence of involutions for G, the alternating circuit V(θ) = e^−iθ_dH_d...e^{−iθ₁H₁} W is automatically exhaustively parametrised and feasibility-respecting (Theorem). Two concrete TSP constructions are derived — a bubble-sort sequence with O(n²) parameters and a binary-insertion sequence with the asymptotically optimal n log(n) parameter count — and on a 9-city TSP test instance both reach approximation ratios (0.83, 0.91) substantially above what QAOA with Hadfield-style mixers attains. This is a direct attack on the same hard-constraint problem Y2 (quasi-binary portfolio QAOA) and Y4 (cardinality-constrained binary opt) tackle, but from a representation-theoretic angle that subsumes the "hard mixer" approach.

Main contribution

The main contribution is the abstract pipeline (Theorem on Main Result, Section IV) that maps {transitive group action on feasible set F} + {generating sequence of involutions} to an exhaustively parametrised, feasibility-respecting parametrised quantum circuit with one variational angle per generating-sequence element. Crucially, the parameters land at θ_i ∈ {0, π/2} (or full [0, π)) to express any feasible state exactly — in stark contrast to standard QAOA-AO, which can only reach the optimum in the infinite-depth limit. The TSP instantiations show the framework is non-empty: bubble-sort yields n(n-1)/2 parameters from adjacency transpositions; binary insertion combines disjoint transpositions to reach the asymptotic Stirling lower bound Ω(n log n).

Key theorems / lemmas / algorithms

• Definition (Exhaustively parametrised): for every x ∈ F there exist θ_x with |⟨x | V(θ_x)|0⟩| = 1.
• Definition (Feasibility-respecting): for every x ∈ B^m ∖ F and every θ, ⟨x | V(θ)|0⟩ = 0.
• Definition (Generating sequence): a fixed-order sequence (h_i)_{i ∈ [d]} in G such that every g ∈ G equals h_d^b_d···h₁^b₁ for some b ∈ B^d.
• Main Theorem: Given G acting transitively on F, a generating sequence of involutions (h_i), and W preparing some |x⟩ with x ∈ F, the circuit V(θ) = ∏_i e^−iθ_iH_i W is exhaustively parametrised and feasibility-respecting. (Proof exploits the involution identity e^−iθA = cosθ - i sinθ A for A² = I.)
• Corollary (Bubble-sort circuit): for n-city TSP, an exhaustively parametrised circuit exists with (n-1)(n-2)/2 parameters even on a star-augmented nearest-neighbour architecture.
• Lemma (Appending lemma): a generating sequence for S_n-1 can be extended to one for S_n by appending log n involutions (the π_l with j ↔ j + 2^l-1 swaps).
• Corollary (Binary-insertion circuit): for n-city TSP, an exhaustively parametrised circuit exists with log 2 + ... + log n ∈ O(n log n) parameters.
• Numerical result (Section V): on a 9-city TSP in the n log n encoding (24 qubits), bubble sort plateaus at approximation ratio 0.83 and binary insertion reaches 0.91 in < 600 COBYLA iterations — QAOA with Hadfield's mixers fails to improve from initialisations.

Detailed walkthrough

The conceptual move is to refuse the soft-constraint trade-off altogether. Standard QAOA either uses penalty terms (turning the constrained problem into a QUBO and accepting the resulting density of states), or uses constraint-preserving "Hadfield mixers" that confine evolution to the feasible subspace but only reach the optimum asymptotically as p → ∞. The authors observe that "expressivity in the feasible subspace" is a representation-theoretic statement: if a group G acts transitively on F, then to reach any feasible y from any other x it suffices to apply some g ∈ G. Implementing each generator g as a parametrised exponential e^−iθH_g with H_g the involutory unitary representation gives a parametrised circuit; the cost is one parameter per generator.

The technical content sits in the notion of a "generating sequence" rather than a generating set. Standard generators in S_n can be applied in arbitrary numbers and orders to express any element. A generating sequence fixes the order and lets each generator appear at most once (or some bounded number of times), as recorded by a single bit per slot. Section IV's proof exploits the involution identity e^−iθA = cosθ·I - i sinθ·A, so setting θ_i = π/2 "applies" the generator H_i exactly and θ_i = 0 skips it. The bit pattern b ∈ B^d in the generating sequence's expansion of any group element thus corresponds bijectively to a discrete parameter setting that prepares the corresponding feasible state.

For TSP the natural choice is G = S_n acting on Hamiltonian cycles via permutation. Two encodings are considered: the wasteful n²-bit one-hot (each cell x_u,t encodes city u at time t), and the more compact n log n-bit encoding where each time slot t holds a log n-bit subregister giving the city visited at that time. The circuit constructions are independent of encoding: each adjacency transposition τ_i is implemented as r = m/n ∈ {n, log n} disjoint SWAP gates between contiguous subregisters, then exponentiated to e^−iθτ_i via the standard ancilla-controlled-Fredkin trick (Figure on circuit construction).

Section V-B's binary-insertion sequence is the more interesting instantiation. Starting from the empty sequence (which trivially generates S₁), apply the appending lemma n-1 times to grow up to S_n. Each appending step adds log n "level-l" elements π_l performing parallel transpositions j ↔ j + 2^l-1. These are disjoint, hence still involutions on the full register. Total length is ∑_i=2ⁿ log i ∈ O(n log n), asymptotically matching Stirling's lower bound on the bit-length needed to label n! states. This is a quantum-circuit analogue of binary representation of permutations.

Section V-C numerically benchmarks both constructions on a 9-city instance encoded with 24 qubits (one starting city fixed). To level the comparison with Hadfield-mixer QAOA, the authors equate "circuit length", letting QAOA have (n-1)/2 layers with the same number of exponentiated transpositions as the exhaustive circuits. COBYLA is the optimiser. The results in Figure (the only PDF figure that converted) are striking: both QAOA variants (single basis-state init and uniform-superposition init) plateau near the initial approximation ratio of 0.60, while binary-insertion reaches 0.91 in roughly 600 iterations and bubble-sort reaches 0.83 (though it does not terminate within 2300 steps). The authors are careful to note this is a single instance and that COBYLA still fails to find the exact optimum despite the reachability guarantee — the parameter landscape is unpredictable. So the framework removes the representational obstruction (every feasible state is reachable) but does not, by itself, solve the optimisation landscape problem.

For Yuan's programme, the key takeaways are: (1) the soft-cardinality constraint in Y3's DGMVP could in principle be replaced with an exhaustively parametrised feasibility-respecting circuit (the feasible set is the set of binary strings of fixed Hamming weight, and the symmetric group acts transitively on it), reducing the DGMVP search space exactly to feasible portfolios; (2) Y2's quasi-binary mixer is a special case of the "feasibility-respecting" construction here, but Y2 inherits QAOA-AO's asymptotic-only reachability — binary-insertion-style sequences for the cardinality-constraint group could give exact reachability instead; (3) Y4's cardinality-constrained Grover algorithm uses a different (amplitude-amplification) class of algorithms, but the state-preparation step there could benefit from the same exhaustive-parametrisation logic for the uniform feasible superposition.

Figures

Citations to Yuan's papers

Overlap with Y1–Y6

• Y1 (warm-started QAOA): Adjacent — Y1 starts QAOA from a problem-aware initial state; the exhaustive framework here uses a single-feasible-state preparation W as initial state. Y1's measurement-derived warm start could feed into W in this framework, replacing the trivial computational-basis init used in Section V.
• Y2 (quasi-binary portfolio QAOA): Direct method overlap. Y2's hard constraint-preserving mixer is a feasibility-respecting circuit by construction, but reaches the optimum only asymptotically. The symmetric group acts transitively on fixed-cardinality binary strings (or on the subset-of-size-k sets directly), so the binary-insertion construction here yields an exhaustively parametrised circuit for cardinality-constrained portfolio QAOA — the same problem class Y2 attacks. This is the most actionable connection.
• Y3 (QAOA DGMVP portfolio): Indirect — DGMVP feasibility (cardinality + integer weights) admits a transitive group action, so the framework applies. A re-implementation of Y3's DGMVP test-bed using exhaustive feasibility-respecting circuits would let Y3's empirical methodology (dual annealing, layerwise) be benchmarked on a strictly more expressive ansatz family.
• Y4 (Grover + ADMM cardinality-constrained): Method overlap on the feasible-state-preparation step. Y4 uses Grover-type amplification on the feasibility-restricted superposition; the framework here generates such superpositions exactly with O(n log n) gates, which could replace Bartschi-Eidenbenz Grover-mixer state preparation referenced in this paper's preliminaries.
• Y5 (GW + Pauli sparsity): Largely orthogonal — SDP relaxations work in continuous matrices, not discrete feasible sets.
• Y6 (PBR Heron2): Unrelated.

Recommended action for Yuan

• Read deeper. The Hannover/Binkowski group has been quietly building a representation-theoretic foundation for constrained QAOA (their open-shop scheduling paper, the bibliography's Binkowski2024 elementary proof of QAOA convergence, the upcoming Binkowski2026 textbook). The framework in this paper is the cleanest formulation yet of where Y2's hard-mixer approach sits in a larger picture.
• Adapt for Y2 / Y3 follow-ups. Construct an exhaustively parametrised circuit for the fixed-Hamming-weight feasible set used in DGMVP and benchmark side-by-side against Y2's quasi-binary mixer at matched circuit length. The expected outcome: same circuit cost, but exact reachability replaces asymptotic reachability. If Y2's iterative refinement on top of the new ansatz beats refinement on top of the asymptotic mixer, that is a publishable Y2-extension result.
• Email the authors — specifically Lennart Binkowski (Hannover) — if Yuan plans to extend Y3 with a new ansatz family. The companion code base on GitHub (linked in the paper) plus their theoretical framework would speed adoption considerably.

Deep analysis generated from LaTeX source · not peer review · author claims not verified.