aiqbench analysis
This research identifies a fundamental feasibility bottleneck in standard QAOA for constrained problems, where generic circuits fail to concentrate probability mass on valid solution manifolds. The authors propose a constraint-enhanced kernel that operates within a restricted subspace, offering a provable exponential improvement in feasible mass over standard approaches for permutation-based NP-Hard problems. This work establishes a critical design principle for future quantum optimization algorithms: effective constraint handling requires co-designing the ansatz to respect the problem's geometric structure rather than relying on generic mixers.
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
arXiv:2511.17259v4 Announce Type: replace Abstract: We study fundamental limitations of the generic Quantum Approximate Optimization Algorithm (QAOA) on constrained problems where valid solutions form a low dimensional manifold inside the Boolean hypercube, and we present a provable route to exponential improvements via constraint embedding. Focusing on permutation constrained objectives, we show that the standard generic QAOA ansatz, with a transverse field mixer and diagonal r local cost, faces an intrinsic feasibility bottleneck: even after angle optimization, circuits whose depth grows at most sublinearly with n cannot raise the total probability mass on the feasible manifold much above the uniform baseline suppressed by the size of the full Hilber space. Against this envelope we introduce a minimal constraint enhanced kernel (CE QAOA) that operates directly inside a product one hot subspace and mixes with a block local XY Hamiltonian. For permutation constrained problems, we prove an angle robust, depth matched exponential enhancement where the ratio between the feasible mass from CE QAOA and generic QAOA grows exponentially in $n^2$ for all depths up to a linear fraction of n, under a mild polynomial growth condition on the interaction hypergraph. Thanks to the problem algorithm co design in the kernel construction, the techniques and guarantees extend beyond permutations to a broad class of NP-Hard constrained optimization problems.
Abstract:We study fundamental limitations of the generic Quantum Approximate Optimization Algorithm (QAOA) on constrained problems where valid solutions form a low dimensional manifold inside the Boolean hypercube, and we present a provable route to exponential improvements via constraint embedding. Focusing on permutation constrained objectives, we show that the standard generic QAOA ansatz, with a transverse field mixer and diagonal r local cost, faces an intrinsic feasibility bottleneck: even after angle optimization, circuits whose depth grows at most sublinearly with n cannot raise the total probability mass on the feasible manifold much above the uniform baseline suppressed by the size of the full Hilber space. Against this envelope we introduce a minimal constraint enhanced kernel (CE QAOA) that operates directly inside a product one hot subspace and mixes with a block local XY Hamiltonian. For permutation constrained problems, we prove an angle robust, depth matched exponential enhancement where the ratio between the feasible mass from CE QAOA and generic QAOA grows exponentially in $n^2$ for all depths up to a linear fraction of n, under a mild polynomial growth condition on the interaction hypergraph. Thanks to the problem algorithm co design in the kernel construction, the techniques and guarantees extend beyond permutations to a broad class of NP-Hard constrained optimization problems.
Quantum Physics (quant-ph); Computational Complexity (cs.CC); Computational Engineering, Finance, and Science (cs.CE); Discrete Mathematics (cs.DM); Mathematical Physics (math-ph)
arXiv:2511.17259 [quant-ph]
(or arXiv:2511.17259v4 [quant-ph] for this version)
Full text under the publisher's open licence · 236 words
Related coverage
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
arXiv · Oct 15, 2026
Problems of Proliferation
LessWrong · Sep 29, 2026
FNOs Predict All Local Observables From Subset Measurements
Quantum Zeitgeist · May 29, 2026
Researchers Cut Signal-Learning Measurements by Seven Million-Fold
Quantum Zeitgeist · Aug 17, 2026