arXiv:2609.31520
Complexity Barriers to State Preparation in Quantum Approximate Optimization
Stuart Hadfield
Abstract
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 positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.
AI Summary
The paper asks which worst-case performance guarantees efficient quantum optimization can achieve when measured by improvement over random guessing, rather than ordinary approximation ratio. For MaxCut with total edge weight $W$, it uses optimal gain $g^\star=C^\star-W/2$ as the reference scale. For the standard Ising encoding and two- or three-variable-per-qubit quantum random access optimization (QRAO), any uniform polynomial-cost quantum or hybrid procedure preparing states with encoded energy gain $E_\rho-W/2\ge\tau g^\star$, for fixed $\tau>0$ on every input with inverse-polynomial operational success probability, would imply $\mathrm{NP}\subseteq\mathrm{BQP}$. This includes reaching the classical optimum energy in QRAO, although a product state always attains that threshold. The proof combines the known NP-hard MaxCut-Gain gap with the known local-decoding identity: decoded mean gain equals encoded energy gain divided by $d^2$, where $d\in\{1,2,3\}$. Repetition converts the resulting output tail into a decision algorithm. A weighted-clique padding construction preserves hardness while making the relative quantum relaxation excess $\Theta(1/n)$. On the same families, the maximally mixed state has energy approximation ratio $1-\Theta(1/n)$ but zero encoded and decoded mean gain. The barriers concern end-to-end uniform efficiency, including training, precision, readout and repetition. They do not establish average-case hardness or exclude advantages on structured instances, supplied solution advice, or exponentially rare outcomes. In particular, fixed maximum degree $D$ admits classical recovery of at least $1/(2D-1)$ of optimal gain, so the all-input barrier does not transfer unchanged to bounded-degree families.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.