arXiv:2609.39922
Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems
Jernej Rudi Finžgar, Martin Leib, Elisabeth Wybo
Abstract
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 Clifford$+T$ rotation synthesis reduces the non-Clifford cost per circuit to $\widetilde O(n^2)$ for every clause locality $\ell$. Compiling the circuit, however, requires the explicit clause list. We find that the mechanism underlying constant QAOA success fixes the degree-one Fourier coefficients of the cost, whose signs reveal the planted solution. However, this leakage need not reveal the solution: we design families in which the quadratic non-Clifford scaling and hard exact optimization coexist.
AI Summary
The paper asks how much fault-tolerant implementation costs for depth-one QAOA on near-symmetric CSPs previously reported to exhibit constant planted-solution success and apparently exponential runtimes for benchmarked classical solvers. It also examines whether those instances remain hard when their explicit clause lists are available. For fixed clause locality $\ell$, the instances contain $m=\Theta(fn^\ell)$ clauses but use phase angles $\gamma=\Theta((fn^{\ell-1})^{-1})$. Applying existing randomized small-angle Clifford+$T$ synthesis gives expected non-Clifford cost $\widetilde O((m\gamma)^2)=\widetilde O(n^2)$ per circuit throughout the constant-success regime, where average degree $d_n=fn^{\ell-1}=\Omega(n)$. An unsigned-sampling argument for exact quasiprobability decompositions bounds solution-sampling overhead by $\Lambda$, rather than the $\Lambda^2$ variance overhead for expectation estimation. The same phase-matching condition fixes the degree-one Fourier coefficients: their signs reveal the planted bits. These coefficients are computable in one pass over the clause list. After independent sparsification, concentration bounds give recovery failure probability at most $ne^{-bd_n}$ for a family-dependent $b>0$, so sufficiently large logarithmic degree already permits recovery, below the QAOA guarantee’s density threshold. Finally, the paper constructs unplanted landscapes with an exponentially large favorable Hamming shell and NP-hard exact optimization within it. Depth-one QAOA concentrates within $O(\sqrt n)$ of the optimal weight at quadratic non-Clifford cost, but does not solve the hard within-shell problem. The shell is also identifiable by structure-aware classical methods; comparisons with local search and general-purpose MaxSAT solvers therefore do not establish quantum advantage.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 11+3 pages, 3 figures