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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

12 citations
Research Square
Quantum Computing Algorithms and Architecture
preprint

Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

preprint en
12 citations

Abstract

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}.

Research Square
Volkswagen Group (Germany) (DE), Forschungszentrum Jülich (DE)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon