About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Nature Physics
Paper
Quantum advantage with noisy shallow circuits
Abstract
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.