21 July 2020
An international team of researchers proves that imperfect devices can provide a quantum advantage by showing that noisy quantum computers can outperform classical machines.
Quantum Advantage with Noisy Shallow Circuits
Can faulty quantum computers surpass their classical counterparts? A collaboration between MCQST member Robert König from the Technical University of Munich and researchers from IBM Watson, the University of Waterloo, and the National University of Singapore succeeds in offering an answer to this question by establishing a quantum advantage of a noisy quantum computer. The results were published in Nature Physics on July 6, 2020.
A key challenge lying at the heart of quantum computing is to prove that quantum computers indeed provide computational advantages over comparable classical devices.
In order to do so, scientists face the task of finding computational problems that can be solved efficiently by a quantum circuit, but cannot be solved using similar classical computational resources. In a previous paper titled “ Quantum advantage with shallow circuits”, a theoretical result demonstrated that shallow quantum circuits are strictly more powerful than analogous classical circuits. While this result is of complexity-theoretic interest because it does not rely on any unproven hardness assumptions, its relevance to experimental quantum computing is limited – it is assumed that quantum circuits can be executed perfectly, i.e., without any errors (or noise).
This limitation has now been overcome as explained in the paper by the international collaborators. The team succeeded in proving that even faulty quantum circuits are superior to their classical (noise-free) counterparts.
Proving quantum advantage in a noisy quantum computer
Although a universal quantum computer is still a thing of the future, noisy intermediate-scale quantum (NISQ) computers are now being developed and used for experiments.
The challenge consisted in developing the right computational problem to test and prove a quantum advantage. The researchers’ team has proposed a computational problem that satisfies two conditions. Firstly, it can be solved by a constant-depth quantum circuit with overwhelming probability even if all building blocks (preparation, gates, and measurements) are imperfect. Secondly, it cannot be solved by any (ideal) constant-depth classical circuit with high probability.
The considered computational problem is motivated by the structure of long-range entanglement generated when measuring a 3-dimensional cluster state. It incorporates new fault-tolerance techniques related to surface codes.
The new result shows that quantum advantage experiments, that is, experimental demonstrations of quantum computational benefits, are possible, in principle, even if the hardware is noisy. These techniques are specifically developed for constant-depth quantum circuits and are likely to be of use for other NISQ applications. Future work may try to further reduce architectural requirements needed to realize quantum circuits demonstrating a quantum advantage.
Publication
Quantum advantage with noisy shallow circuits
Sergey Bravyi, David Gosset, Robert König and Marco Tomamichel
Nature Physics (2020)
DOI:
10.1038/s41567-020-0948-z
Related publication
Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, Robert König
Science Vol. 362, Issue 6412, pp. 308-311 (2018)
DOI:
10.1126/science.aar3106
Contact
Prof. Dr. Robert König
Technical University Munich
Boltzmannstrasse 3
85748 Garching
Tel: +49 89 289 17042
Email: robert.koenig[at]tum.de