QAOA for Max-Cut requires hundreds of qubits for quantum speed-up

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...

Full description

Saved in:
Bibliographic Details
Published in:Scientific reports 2019-05, Vol.9 (1), p.6903-6903, Article 6903
Main Authors: Guerreschi, G. G., Matsuura, A. Y.
Format: Article
Language:English
Subjects:
639/705/1042
639/766/483/481
Algorithms
Computer applications
Computers
Humanities and Social Sciences
Information processing
MATHEMATICS AND COMPUTING
multidisciplinary
Quantum theory
Science
Science (multidisciplinary)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2045-2322
2045-2322
DOI:10.1038/s41598-019-43176-9