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

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^ℓ) 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²) 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.

Signal-to-noise problems in fault-tolerant quantum computation
Hyunwoo Oh
arXiv10 Oct 2026PreprintarXiv licenceFull textHigh-energy & particle physics Nuclear physicsarXiv
Toward Fault-Tolerant Variational Optimization: QAOA under [[4,2,2]] Error Detection
Matteo Robert Child, Emanuele Dri, Giacomo Vitali +2
arXiv5 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Fault-tolerant quantum computation with static atomic buses
M. Bergonzoni, L. Pecorari, S. A. Norrell +3
PRX Quantum9 Oct 2026Peer-reviewedCC BY 4.0Quantum physics & quantum informationCrossref
Unitary fault-tolerant encoding of Pauli states in surface codes
Luis Colmenarez, Remmy Zen, Jan Olle +2
npj Quantum Information1 Oct 2026Peer-reviewedCC BY-NC-ND 4.0Full textQuantum physics & quantum informationCrossref
Enabling chemically accurate quantum phase estimation in the early fault-tolerant regime via unitary weight concentration
Shota Kanasugi, Riki Toshio, Kazunori Maruyama +1
PRX Quantum28 Oct 2026Peer-reviewedPublisher termsQuantum physics & quantum informationCrossref

Cite

BibTeX RIS

BibTeX

@misc{finzgar2026faulttolerant,
  title = {{Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems}},
  author = {Jernej Rudi Finžgar and Martin Leib and Elisabeth Wybo},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.39922},
  eprint = {2609.39922},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.39922},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems
AU  - Jernej Rudi Finžgar
AU  - Martin Leib
AU  - Elisabeth Wybo
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.39922
UR  - https://arxiv.org/abs/2609.39922
AB  - 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.
ER  -

Abstract

Related

Cite