Quantum advantage with shallow circuits

See allHide authors and affiliations

Science  19 Oct 2018:
Vol. 362, Issue 6412, pp. 308-311
DOI: 10.1126/science.aar3106

Quantum outperforms classical

Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of “steps” needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits.

Science, this issue p. 308; see also p. 289

View Full Text

Stay Connected to Science