Quantum Computing

Proof that noisy quantum computers can outperform classical machines

Share this post:

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.

Practical Magic

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.

Bravyi, S., Gosset, D., König, R., Tomamichel, M. Quantum advantage with noisy shallow circuits. Nat. Phys. (2020).


IBM Quantum

Quantum starts here


Researcher in quantum information and computation, IBM Quantum

More Quantum Computing stories

We’ve moved! The IBM Research blog has a new home

In an effort better integrate the IBM Research blog with the IBM Research web experience, we have migrated to a new landing page: https://research.ibm.com/blog

Continue reading

Pushing the boundaries of human-AI interaction at IUI 2021

At the 2021 virtual edition of the ACM International Conference on Intelligent User Interfaces (IUI), researchers at IBM will present five full papers, two workshop papers, and two demos.

Continue reading

From HPC Consortium’s success to National Strategic Computing Reserve

Founded in March 2020 just as the pandemic’s wave was starting to wash over the world, the Consortium has brought together 43 members with supercomputing resources. Private and public enterprises, academia, government and technology companies, many of whom are typically rivals. “It is simply unprecedented,” said Dario Gil, Senior Vice President and Director of IBM Research, one of the founding organizations. “The outcomes we’ve achieved, the lessons we’ve learned, and the next steps we have to pursue are all the result of the collective efforts of these Consortium’s community.” The next step? Creating the National Strategic Computing Reserve to help the world be better prepared for future global emergencies.

Continue reading