Computational complexity, step by step

See allHide authors and affiliations

Science  19 Oct 2018:
Vol. 362, Issue 6412, pp. 289
DOI: 10.1126/science.aau9555

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


It is widely believed that large-scale quantum computers, when they are built, will outperform their standard, “classical” counterparts. This supposition has inspired huge public interest and very substantial state and private investment in the development of quantum computing hardware. Yet, is it actually correct? On page 308 of this issue, Bravyi et al. (1) prove the first rigorous separation between two analogous and natural quantum and classical computational-complexity classes.