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

Understand

Optimization is often cited as a promising application of quantum computers.

• However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyses to conclude that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions.
• In this work, we compile and analyze the Quantum Approximate Optimization Algorithm (QAOA) combined with Amplitude Amplification (AA) applied to random 8-SAT at the satisfiability threshold.
• Our compilation involves careful optimization of circuits for Hamiltonian simulation, which may be of independent interest.