Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
Chinonso Onah, Roman Firt, Kristel Michielsen · 2025
Read Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs by Chinonso Onah, Roman Firt, Kristel Michielsen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14296.txt.
Introduction
Chinonso Onah, Roman Firt, and Kristel Michielsen build a quantum optimizer that lives inside the feasible set instead of visiting it by luck. Their constraint-enhanced QAOA works in a one-hot product space, where each block of qubits starts in a W state encoding one choice. A depth-optimal encoder prepares those states without ancilla qubits, and a special mixer moves within the one-hot manifold without leaving it.
The authors prove per-block controllability and show the shallow circuit behaves like a unitary design after symmetry averaging, which yields anticoncentration guarantees for finite sampling. Wrapped with a deterministic feasibility checker, the sampler becomes a polynomial-time hybrid solver, and they report advantages on routing-style problems.
Catalog record
| CREATOR | Chinonso Onah, Roman Firt, Kristel Michielsen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14296
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs Chinonso Onah, Roman Firt, Kristel Michielsen Abstract We introduce the Constraint–Enhanced Quantum Approximate Optimization Algorithm (CE–QAOA); a shallow, constraint-aware ansatz that operates inside the one–hot product space ℋ OH = [ n ] m \mathcal{H}_{\mathrm{OH}}=[n]^{m} where m m is the number of blocks, each initialized with n n qubit W n − W_{n}- state. We give an ancilla-free, depth-optimal encoder that prepares a W n W_{n} state using n − 1 n{-}1 two-qubit rotations per block, and a two-local XY mixer restricted to the same block of n n qubits with a constant spectral gap. Algorithmically, we wrap constant-depth sampling with a deterministic classical checker to obtain a polynomial-time hybrid quantum–classical solver (PHQC) that returns the best observed feasible solution in O ( S n 2 ) O(Sn^{2}) time where S = poly ( n ) S=\mathrm{poly}\bigl(n\bigr) is the number of shots. We obtain two advantages. First, when CE QAOA fixes r ≥ 1 r\geq 1 locations different from the start city, we achieve a Θ ( n r ) \Theta(n^{r}) reduction in shot complexity even against a classical sampler that draws uniformly from the feasible set. Second, against a classical baseline restricted to raw bitstring sampling, we show an exp ( Θ ( n 2 ) ) \exp(\Theta(n^{2})) separation in the minimax sense. In noiseless circuit simulations of TSP instances ranging from 4 4 to 10 10 locations from QOPTLib benchmark library, we recover the global optimum at p = 1 p{=}1 using polynomial shot budgets and coarse parameter grids defined by the problem sizes as suggested in Theorem 13 and Algorithm 4 . 1 Introduction Combinatorial optimization problems (COP) underpin modern logistics, manufacturing, finance, and drug discovery; and it surfaces throughout artificial intelligence and machine-learning workflows [ 1 , 2 , 3 , 4 ] . Classical solvers excel when they exploit problem structure—e.g., branch–and–bound and cutting planes [ 2 , 5 , 6 ] . In contrast, many near-term quantum approaches—notably QAOA [ 7 ] and its variants [ 8 , 9 , 10 ] —tend to explore the full Hilbert space in search of the (near) optimal solution(s), paying in measurement cost [ 11 , 12 ] , depth [ 11 , 12 ] , and barren plateaus [ 13 ] . A growing line of work mitigates this by encoding directly into symmetry-rich feasible subspaces and using feasibility-preserving mixers [ 14 , 15 , 16 , 17 , 19 , 20 ] . In this work we study Constraint–Enhanced Quantum Approximate Optimization Algorithm (CE–QAOA), a shallow, constraint-aware ansatz that natively operates on a block one-hot manifold. Our circuit constructions are based on an ancilla-free, depth-optimal encoder that prepares a block W_{n} state using exactly n{-}1 excitation preserving two qubit gates, and a two-local block–XY mixer that preserves the manifold. [ 14 ] These properties allow us to make contact with low-order moment analysis of random quantum circuits [ 21 ] in the encoded subspace and to subsequently study the emergence of approximate unitary t- designs. Why do unitary t -designs matter? In the context of variational optimization, unitary designs are a principled proxy for expressivity , anticoncentration , and typical-case trainability . A unitary t -design reproduces Haar moments up to degree t . Thus any degree- \leq t observable (e.g., overlaps, energies, and many gradient statistics) computed under the design agrees with the Haar baseline up to \varepsilon [ 21 ] . Secondly it suggests an instance-agnostic typical-case behaviour because second moments are insensitive to the fine details of the cost landscape. From the “landscape information” viewpoint, matching Haar second moments ensures that a nontrivial amount of task-relevant variance survives at shallow depth on the encoded space, which increases the effective information capacity of the ansatz [ 22 , 23 ] . Our circuit design inherit from prior work in Refs. [ 14 , 24 ] . Here we leverage additional problem specific strucutures through problem-algorithm codesign to capture a broad class of COPs (TSP/ATSP, QAP, CVRP, etc) via block one-hot encodings and shared constraint properties. We propose a unifying kernel in Def. 10 . Within this kernel, a block-permutation twirl yields a unitary 1 -design on the encoded space, reproducing the Haar baseline \mathbb{E}\,|\langle x|U|\phi\rangle|^{2}=1/D and a corresponding existence theorem for any target basis vector x^{\star} (and thus for the optimum) in Thm. 13 and Cor. 16 . Algorithmically, we introduce the the Polynomial time Hybrid Quantum-Classical Solver (PHQC) which wraps constant-depth quantum sampling over a coarse parameter grid with a deterministic classical checker that identifies the best sampled solutions, operationalizing these t- design bounds. PHQC identifies the optimal solution if it is sampled at least once. Our running examples are derived from the Travelling Salesman Problem (TSP) where the n^{2} qubits are imagined to be arranged in n blocks of size n and the double one-hot constraint restricts to a fixed-Hamming-weight manifold containing only n! basis states out of the encoded n^{n} basis vectors and 2^{n^{2}} vectors in the ambient Hilbert space [ 25 , 26 ] . Similar one-hot/capacity encodings arise for assignments [ 27 ] , matchings [ 28 ] , capacitated routing [ 3 ] , and graph coloring [ 25 ] . CE–QAOA exploits this structure at the encoder, mixer layers, phase layers, and classical feasibility checker; extending problem–algorithm co-design from quantum to classical stage [ 29 , 30 ] . The advertised quantum advanatge comes from direct utilization of problem structures at the classical and quantum levels of the algorithm. We present noiseless circuit simulations results for problem instances ranging from 4 to 10 locations drawn from the QOPTLib benchmark problems [ 31 ] . PHQC recovered the optimal solution in all instances considered while dramatically reducing the shot cost to a polynomial O(n^{k}) at depth p=1 as reported in Table 1 . 1.1 Relation to Prior Work Recently, Smith – Miles et al. [ 37 ] surveyed the obstacles to near-term quantum advantage on TSP—including resource inflation from generic encodings (e.g., QUBO), feasibility handling, noise/optimizer pathologies, and inconsistent benchmarking against strong classical solvers—and argue for structure-exploiting formulations and transparent, reproducible evaluations. Our CE – QAOA/PHQC approach aligns with this perspective but differs in emphasis because we treat global constraints as useful structure within an encoded manifold. Our formalism inherits from the preexisiting body of work in the alternating-operator literature (often called QAOA+) which develops mixers that commute with, or otherwise preserve, constraint projectors—e.g., one-hot, ring mixers, and null-swaps [ 14 , 32 ] . For routing families (e.g., CVRP), feasibility is frequently enforced via Grover-style oracles [ 20 , 16 , 33 ] , which introduce oracle/ancilla overhead and reflection-based subroutines. In contrast, our kernel uses a two-local, ancilla-free block–XY mixer that preserves all blockwise one-hot constraints, acts entirely within the encoded manifold, and is normalized to have a constant spectral gap on the one-excitation sector (Prop. 4 ). The initial state is the block- W product [ 34 ] prepared by an ancilla-free, depth-optimal cascade (Thm. 1 ), making the mixer’s top eigenvector the initial state. Our mixer design ensures invariance (excitation conservation) and block factorization, enabling quditization H_{M}\mapsto