2025/11/21 by Chinonso Onah, Onah, Chinonso, Kristel Michielsen +1 · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Engineering #Constraint (computer-aided design) #Discrete Mathematics (cs.DM) #Exponential function #Exponential growth #FOS: Computer and information sciences #FOS: Physical sciences #Finance #Kernel (algebra) #Manifold (fluid mechanics) #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Optimization problem #Permutation (music) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Subspace topology #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.2511.17259
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/11/21 · openalex created_date 2025/11/25 · openalex updated_date 2026/08/05
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 n2 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.