Title: QAOA for Max-Cut requires hundreds of qubits for quantum speed-up,
Abstract: Computational quantum technologies are entering a new phase in which noisy
intermediate-scale quantum computers are available, but are still too small to
benefit from active error correction. Even with a finite coherence budget to
invest in quantum information processing, noisy devices with about 50 qubits
are expected to experimentally demonstrate quantum supremacy in the next few
years. Defined in terms of artificial tasks, current proposals for quantum
supremacy, even if successful, will not help to provide solutions to practical
problems. Instead, we believe that future users of quantum computers are
interested in actual applications and that noisy quantum devices may still
provide value by approximately solving hard combinatorial problems via hybrid
classical-quantum algorithms. To lower bound the size of quantum computers with
practical utility, we perform realistic simulations of the Quantum Approximate
Optimization Algorithm and conclude that quantum speedup will not be
attainable, at least for a representative combinatorial problem, until several
hundreds of qubits are available.