Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
We introduce the \emph{Constraint–Enhanced Quantum Approximate Optimization Algorithm} (CE–QAOA), a shallow, constraint-aware ansatz that operates \emph{inside} the one–hot product space \(\OH=[n]^m\), where \(m\) is the number of blocks and each block is initialized in an \(n\)-qubit \(W_n\) state. We give an ancilla-free, depth-optimal encoder that prepares \(W_n\) using \(n{-}1\) two-qubit rotations per block, and a two-local block-XY mixer that preserves the one–hot manifold and has a constant spectral gap on the one-excitation sector. At the level of expressivity, we establish per-block controllability, implying approximate universality per block. At the level of distributional behavior, we show that (after natural block/symbol permutation twirls) shallow CE–QAOA realizes an encoded unitary \(1\)-design and supports approximate second-moment (\(2\)-design) behavior; combined with a Paley--Zygmund argument, this yields finite-shot anticoncentration guarantees. Algorithmically, we wrap constant-depth sampling with a deterministic feasibility checker to obtain a polynomial-time hybrid quantum--classical solver (PHQC) that returns the best observed feasible solution in \(O(Sn^2)\) time, where \(S=\poly n\) is the shot budget. We obtain two advantages. First, when CE--QAOA fixes \(r\ge 1\) locations different from the start city, we achieve a \(\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(\Theta(n^{2}))\) minimax separation. In noiseless circuit simulations of TSP instances with \(n\in\{4,\dots,10\}\) locations from the QOPTLib benchmark library, we recover the global optimum at \(p{=}1\) using polynomial shot budgets and coarse parameter grids defined by the problem size, as suggested by Theorem~\ref{thm:exist-params} and Algorithm~\ref{alg:PHQC1}.
Institutions
- Volkswagen Group (Germany) (DE)
- Forschungszentrum Jülich (DE)
Publication Details
- Journal
- Research Square
- Published
- 2026-11-19
- DOI
- https://doi.org/10.21203/rs.3.rs-11396245/v1
- Citations
- 12
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- preprint