Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

We introduce the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), a shallow, constraint-aware ansatz that operates inside the one-hot product space of size [n]^m, where m is the number of blocks and each block is initialized with an n-qubit W_n state. We give an ancilla-free, depth-optimal encoder that prepares a W_n state using n-1 two-qubit rotations per block, and a two-local XY mixer restricted to the same block of 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) time, where S is the number of shots. 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)) separation in the minimax sense. In noiseless circuit simulations of TSP instances ranging from 4 to 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 sizes.