{"id":"arxiv/2609.39922","url":"https://arxiv.org/abs/2609.39922","tags":["quant-ph"],"score":0,"title":"Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems","domain":"quant-ph","source":"arxiv","authors":["Jernej Rudi Finžgar","Martin Leib","Elisabeth Wybo"],"reviews":0,"subject":"quant-ph","summary":"Montanaro and Zhou proved that depth-one Quantum Approximate Optimization Algorithm (QAOA) finds the planted solution of certain near-symmetric constraint satisfaction problems with probability $Ω(1)$, and observed exponential runtimes for general-purpose classical solvers on explicit realizations, providing strong evidence of an empirical exponential speedup of low-depth QAOA. We ask what such a circuit costs fault-tolerantly. Although the cost Hamiltonian carries $Θ(n^\\ell)$ clauses, the rotation angle at which QAOA succeeds shrinks as $n^{1-\\ell}$, and we show that small-angle…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}