Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization*

Here we explore which heuristic-based quantum algorithms for combinatorial optimization are practical on a small fault-tolerant quantum computer. We compile circuits for the bottleneck step of several heuristic approaches to combinatorial optimization and report for how long and for what size systems one can perform these heuristics in a superconducting quantum processor protected from error by the surface code. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup will achieve an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions, our analysis suggests that quantum accelerated simulated annealing would require roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about four CPU-minutes.