Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm

We present a comprehensive and realistic resource analysis for achieving fault-tolerant quantum advantage in combinatorial optimization, focusing on the Quantum Approximate Optimization Algorithm (QAOA) combined with amplitude amplification (AA) for random 8-SAT problems near the satisfiability threshold. Our work rigorously compiles and optimizes quantum circuits for Hamiltonian simulation, leveraging recent advances in surface code error correction and resource-state factories. We demonstrate that QAOA+AA can outperform state-of-the-art classical solvers under realistic hardware assumptions, including a physical error rate of 10⁻³ and a 1 μs code cycle time. Our analysis shows a crossover at 179 variables, requiring 73.9 million physical qubits and 15 hours of runtime, with further reductions possible through improved error rates and factory overheads. We benchmark leading classical solvers, such as Sparrow, and allow for energy-constrained parallelization, showing that quantum advantage persists even against massively parallel supercomputers. We detail the quantum-classical crossover, including the impact of hardware improvements such as magic state cultivation and algorithmic fault-tolerance, which can reduce quantum resources and runtime, enabling a crossover of 2.94 hours using 8.88 million physical qubits against a classical solver running on 725,760 CPU cores. Our findings establish practical thresholds for quantum optimization and highlight the importance of circuit and architectural optimizations, supporting the feasibility of large-scale fault-tolerant quantum computing for real-world optimization problems. This work provides the first complete and realistic resource estimate for quantum advantage in optimization, demonstrating that polynomial quantum speedups can be practical and transformative for challenging computational tasks, and paving the way for future advances in quantum hardware and algorithms.