1. QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Author
-
Gian Giacomo Guerreschi and A. Y. Matsuura
- Subjects
FOS: Computer and information sciences ,0301 basic medicine ,Speedup ,Quantum information ,Computer science ,Maximum cut ,FOS: Physical sciences ,lcsh:Medicine ,Upper and lower bounds ,Article ,03 medical and health sciences ,0302 clinical medicine ,lcsh:Science ,Quantum ,Quantum computer ,Quantum Physics ,Computer Science - Performance ,Multidisciplinary ,Computational science ,lcsh:R ,TheoryofComputation_GENERAL ,Performance (cs.PF) ,Quantum technology ,030104 developmental biology ,Computer engineering ,ComputerSystemsOrganization_MISCELLANEOUS ,Qubit ,lcsh:Q ,Quantum Physics (quant-ph) ,Error detection and correction ,030217 neurology & neurosurgery ,Coherence (physics) - 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.
- Published
- 2019
- Full Text
- View/download PDF