Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement

arXiv:2511.17259v5 Announce Type: replace Abstract: We study the feasibility limitations of generic QAOA for permutation-constrained optimization, where valid configurations occupy an exponentially small fraction of the Boolean hypercube. Using random edge-cost TSP/ATSP ensembles, we establish high-probability bounds showing that optimized generic QAOA retains exponentially small feasible probability over specified parameter domains. At depth one, the bound holds uniformly over all mixer angles and a cost-angle grid that may be exponentially large in n^2. The analysis combines Walsh-Fourier/Krawtchouk estimates, which suppress low- and high-degree contributions, with transition-feature collision bounds controlling objective-dependent interference. Complementary cost-angle averaging, fourth-moment estimates, and light-cone analysis characterize energy-fibre coherence, typical-angle concentration, and constraint-correlation geometry. We compare generic QAOA with a constraint-enhanced kernel (CE-QAOA) initialized in a product one-hot subspace and evolved with a block-local XY mixer. For N = n^2 binary variables, CE-QAOA attains feasible probability at least n!/n^n at every depth, yielding an exp[Omega(n^2)] advantage over optimized generic QAOA at depth one with high probability. For linked cost-angle schedules with independently optimized mixer angles, the generic feasibility obstruction and exponential CE-QAOA separation extend throughout linear-depth windows p 0. These parameter-uniform bounds also imply exponential raw-sample requirements for adaptive feasible sampling within the prescribed domains.

Abstract:We study the feasibility limitations of generic QAOA for permutation-constrained optimization, where valid configurations occupy an exponentially small fraction of the Boolean hypercube. Using random edge-cost TSP/ATSP ensembles, we establish high-probability bounds showing that optimized generic QAOA retains exponentially small feasible probability over specified parameter domains. At depth one, the bound holds uniformly over all mixer angles and a cost-angle grid that may be exponentially large in n^2. The analysis combines Walsh-Fourier/Krawtchouk estimates, which suppress low- and high-degree contributions, with transition-feature collision bounds controlling objective-dependent interference. Complementary cost-angle averaging, fourth-moment estimates, and light-cone analysis characterize energy-fibre coherence, typical-angle concentration, and constraint-correlation geometry. We compare generic QAOA with a constraint-enhanced kernel (CE-QAOA) initialized in a product one-hot subspace and evolved with a block-local XY mixer. For N = n^2 binary variables, CE-QAOA attains feasible probability at least n!/n^n at every depth, yielding an exp[Omega(n^2)] advantage over optimized generic QAOA at depth one with high probability. For linked cost-angle schedules with independently optimized mixer angles, the generic feasibility obstruction and exponential CE-QAOA separation extend throughout linear-depth windows p <= alpha*n, for fixed alpha > 0. These parameter-uniform bounds also imply exponential raw-sample requirements for adaptive feasible sampling within the prescribed domains.

Substantially revised manuscript. New high-probability feasibility bounds for TSP/ATSP ensembles, including uniform mixer-angle control and a linear-depth extension for linked cost-angle schedules. Added transition-feature analysis, adaptive sampling consequences, and an exponential CE-QAOA separation. Discussion and conclusion rewritten

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.17259v5 [quant-ph] for this version)

analiza aiqbench

Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement

Subiecte conexe