{"id":"arxiv/2609.31520","url":"https://arxiv.org/abs/2609.31520","tags":["quant-ph","cs.CC"],"score":0,"title":"Complexity Barriers to State Preparation in Quantum Approximate Optimization","domain":"quant-ph","source":"arxiv","authors":["Stuart Hadfield"],"reviews":0,"subject":"quant-ph","summary":"For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \\emph{any uniformly efficient quantum or hybrid procedure recovering a fixed…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}