Journal
NATURE PHYSICS
Volume 16, Issue 10, Pages 1040-+Publisher
NATURE RESEARCH
DOI: 10.1038/s41567-020-0948-z
Keywords
-
Categories
Funding
- IBM Research Frontiers Institute
- MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert Space
- Technical University of Munich-Institute of Advanced Study - German Excellence Initiative
- European Union [291763]
- DFG Cluster of Excellence 2111 (Munich Center for Quantum Science and Technology)
- German Federal Ministry of Education [13N14776]
- Natural Sciences and Engineering Research Council of Canada (NSERC) [RGPIN-2019-04198]
- IBM Research
Ask authors/readers for more resources
As increasingly sophisticated prototypes of quantum computers are being developed, a pressing challenge is to find computational problems that can be solved by an intermediate-scale quantum computer, but are beyond the capabilities of existing classical computers. Previous work in this direction has introduced computational problems that can be solved with certainty by quantum circuits of depth independent of the input size (so-called 'shallow' circuits) but cannot be solved with high probability by any shallow classical circuit. Here we show that such a separation in computational power persists even when the shallow quantum circuits are restricted to geometrically local gates in three dimensions and corrupted by noise. We also present a streamlined quantum algorithm that is shown to achieve a quantum advantage in a one-dimensional geometry. The latter may be amenable to experimental implementation with the current generation of quantum computers. Uncorrected noise prevents quantum computers from running deep algorithms and outperforming classical machines. A method is now reported that allows noisy shallow quantum algorithms to be used to solve classically hard problems.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available