As larger and larger prototypes of quantum computers are being developed, one of the most exciting challenges in the theory of quantum computing is to find computational problems that can be solved by an noisy intermediate-scale noisy quantum devices, but are beyond the capabilities of existing classical computers. In joint work with Robert König, Sergey Bravyi and David Gosset, we show for the first time an unconditional separation between the computational power of noisy quantum circuits of constant depth and classical circuits of depth even growing slowly (but sub-logarithmically) with the problem size. The quantum advantage established in our paper holds for rather general noise models that may include correlated multi-qubit errors with long-range correlations.
Our new separation theorem for noisy devices requires various new tools that we believe to be of independent interest in quantum error correction and simplifies the required quantum circuits, making them more amenable for implementation in near-term devices.
Our work was presented at QIP 2020 and FOCS 2019 (see video of Sergey’s talk below). It was published in Nature Physics.