Can the full computational power of noisy near-term quantum devices be unleashed, without paying the price of quantum error correction? In the new paper, “Quantum advantage with noisy shallow circuits,” an international team of researchers including myself seek to answer that question by proving a separation between the power of noisy quantum and that of noiseless classical computations, which obey certain technical restrictions.
Published in Nature Physics, our paper proposes a computational problem related to the so-called Mermin-Peres Magic Square game, which can be efficiently solved on a noisy quantum computer provided that the noise level is below a certain constant threshold value. We consider the parallel computational model, in which a layer of non-overlapping gates can be executed in a single clock cycle. The paper shows that the number of clock cycles required to solve the Magic Square problem is upper bounded by a small constant independent of the problem size. Put another way, the problem can be solved by a parallel quantum algorithm in a constant time independent of the problem size, even if the algorithm is implemented on a noisy hardware.
The main technical result of the paper is establishing the classical hardness of the Magic Square problem. My co-authors from Canada’s University of Waterloo, Germany’s Technical University of Munich, and Singapore’s Centre for Quantum Technologies, and I show that any classical parallel algorithm solving the Magic Square problem takes longer and longer time as the problem size n grows (more precisely, the classical runtime grows at least logarithmically with n). From the complexity theory perspective, this result constitutes the first rigorous separation between the computational power of noisy constant-depth quantum circuits and noiseless constant-depth classical circuits.
As a bonus, we demonstrate that the constant-depth quantum circuit solving the Magic Square problem possesses a certain geometric locality: the qubits can be placed at sites of a three-dimensional grid such that the circuit contains only nearest-neighbor two-qubit gates. Such geometrically local circuits are expected to be more amenable to experimental implementation.
Solving Magic Squares
The original Magic Square game proposed by David Mermin and Asher Peres about 30 years ago demonstrates how quantum entanglement can enable certain information processing tasks impossible in the classical world. The game can be viewed as a short conversation between a referee and two cooperating players named Alice and Bob. To win the game, the players have to convince the referee of a certain mathematical property. Crucially, Alice and Bob are not allowed to communicate with each other once the game begins. Each player can only talk to the referee.
This restriction prevents Alice and Bob from winning the game in the classical world. However, the game can be won if each player holds a small quantum computer such that Alice’s and Bob’s qubits are initially prepared in a suitable entangled state.
Our Nature Physics paper shows that a certain multi-player version of the Magic Square game cannot be won classically even if each player is allowed to talk with a few other players. Such a multi-player game leads to a computational problem which is hard for constant-depth classical circuits, but easy for constant-depth quantum circuits, even in the presence of noise.
Although the Magic Square problem is mostly of theoretical interest, we hope that our work will invigorate the search for more practical computational problems that can be tackled with the near-term noisy quantum devices.
We still lack the quantum error correction (QEC) technology to make large-scale quantum computers a reality. In theory, QEC enables building reliable quantum circuits from unreliable components that are “good enough”, as quantified by the error threshold theorem. This is achieved by redundantly encoding a few logical qubits into many physical qubits and repeatedly measuring parity check operators to detect and correct errors.
The next generation of quantum devices is expected to achieve sub-threshold error rates enabling experimental demonstration of QEC. A major challenge in this area is implementing a computationally universal set of logical gates on the encoded qubits in a fault-tolerant fashion. Some very simple logical gates such as a single-qubit rotation by 45 degrees may require hundreds or even thousands of physical gates which rules out near-term implementation.
Our approach avoids most of this overhead by working with a non-universal gate library known as Clifford gates. While Clifford gates alone are not sufficient to express some quantum algorithms, such as Shor’s integer factoring, they provide enough computational power to solve the Magic Square problem. At the same time, logical fault-tolerant Clifford gates are relatively cheap and can be implemented in a single clock cycle using the previously known QEC methods.
Looking ahead, we will continue working on new quantum algorithms that can achieve a quantum advantage while solving practically important problems on noisy devices, either without or with a limited quantum error correction.