QIP2021 | Compilation of Fault-Tolerant Q-Heuristics for Combinatorial Optimization (Yuval Sanders)

Authors: Yuval Sanders, Dominic Berry, Pedro Costa, Louis Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven and Ryan Babbush
Affiliations: Macquarie University | Macquarie University | Macquarie University | Macquarie University | University of Washington | Google | Google | Google

Abstract
We compile explicit circuits and evaluate the computational cost for heuristic-based quantum algorithms for combinatorial optimization. We consider several variants of quantum-accelerated simulated annealing as well as adiabatic algorithms, quantum-enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. We provide novel methods for executing the bottleneck subroutines for these heuristics, and our methods can easily be applied to other algorithms where numerical performance matters. We estimate how quickly the subroutines could be executed on a modestly sized superconducting-qubit-based quantum computer with surface code error correction. We conclude that quadratic speedups for heuristic-based quantum optimization algorithms are insufficient for early quantum computers to beat present day classical computers.''Get entangled with us!