Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

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) clauses, the rotation angle at which QAOA succeeds shrinks as n 1-, and we show that small-angle Clifford +T rotation synthesis reduces the non-Clifford cost per circuit to O(n 2) for every clause locality. 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.