aiqbench analysis
This paper proposes a constraint-aware variant of QAOA that keeps the search inside a one-hot subspace, aiming to avoid wasting shots on infeasible solutions. The proven shot-complexity gains are measured against specific classical baselines, such as uniform sampling from the feasible set or raw bitstring sampling, not against strong heuristic solvers. The empirical results come from noiseless simulations on TSP instances with 4 to 10 cities, so hardware noise and practical scaling remain open questions for readers judging near-term relevance.
Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
arXiv:2511.14296v4 Announce Type: replace-cross 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 [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 and 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(S n^2) time, where S is a polynomial shot budget. We obtain two advantages. First, when CE-QAOA fixes r >= 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 traveling salesman problem instances with n in {4,...,10} locations from the QOPTLib benchmark library, we recover the global optimum at depth p = 1 using polynomial shot budgets and coarse parameter grids defined by the problem size.
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 [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 and 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(S n^2) time, where S is a polynomial shot budget. We obtain two advantages. First, when CE-QAOA fixes r >= 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 traveling salesman problem instances with n in {4,...,10} locations from the QOPTLib benchmark library, we recover the global optimum at depth p = 1 using polynomial shot budgets and coarse parameter grids defined by the problem size.
Emerging Technologies (cs.ET); Discrete Mathematics (cs.DM); Mathematical Physics (math-ph); Applied Physics (physics.app-ph); Quantum Physics (quant-ph)
arXiv:2511.14296 [cs.ET]
(or arXiv:2511.14296v4 [cs.ET] for this version)
Full text under the publisher's open licence · 280 words
Related coverage
The Signal Horizon: Local Blindness and the Contraction of Pauli-Weight Spectra in Noisy Quantum Encodings
arXiv · Aug 5, 2026
Long Range Frequency Tuning for QML
arXiv · Jul 21, 2026
News
Quantum Computing Report · Jun 7, 2026
Running Variational Quantum Eigensolver with Qiskit Aer on AMD Instinct
AMD · May 29, 2026