Finite-Depth, Finite-Shot Guarantees for Constrained Quantum Optimization via Fejér Filtering
For researchers in quantum optimization, this work offers theoretical guarantees for constrained QAOA variants, though the results are analytical and rely on specific conditions.
The paper provides finite-depth and finite-shot lower bounds on the success probability of sampling optimal solutions in constrained quantum optimization using the CE-QAOA ansatz, achieving a dimension-free guarantee of the form q0 ≥ x/(1+x) with x = (p+1)^2 sin^2(δ/2) C_β.
We study finite-layer alternations of the \emph{Constraint--Enhanced Quantum Approximate Optimization Algorithm} (CE--QAOA), a constraint-aware ansatz that operates natively on block one-hot manifolds. Our focus is on feasibility and optimality guarantees. We show that restricting cost angles to a harmonic lattice exposes a positive Fejér filter acting on the cost-phase unitary $U_C(γ)=e^{-iγH_C}$ \emph{in a cost-dephased reference model (used only for analysis)}. Under a wrapped phase-separation condition, this yields \emph{dimension-free} finite-depth and finite-shot lower bounds on the success probability of sampling an optimal solution. In particular, we obtain a ratio-form guarantee \[ q_0 \;\ge\; \frac{x}{1+x}, \qquad x \;=\; (p{+}1)^2 \sin^2(δ/2)\,C_β, \] where $q_0$ is the single-shot success probability, $C_β$ is the mixer-envelope mass on the optimal set, $δ$ is a phase-gap proxy, and $p$ is the number of layers. A Coherent equivalent is proved subsequently and a Riemann--Lebesgue averaging extends the discussion beyond exact lattice normalization. We conclude by outlining coherent realizations of near-term-hardware-efficient positive spectral filters as a main open direction for this framework.