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

Quantum Conundrum: Clifford Group Investigation Unexpectedly Reveals New Quantum Advantage Proof

When we began our current line of investigation, the goal was to study the structural property of the Clifford group, describing a set of transformations that generate entanglement, play an important role in quantum computing error correction, and are used in (randomized) benchmarking. In a series of one-thing-leads-to-another findings, however, we ended up discovering a new mathematical proof of quantum advantage – the elusive threshold at which quantum computers outperform classical machines in certain use cases.

Continue reading

IBM Roundtable: Building a Quantum Workforce Requires Interdisciplinary Education and the Promise of Real Jobs

The ability to harness quantum-mechanical phenomena such as superposition and entanglement to perform computation obviously poses a number of difficulties. Add in the need to make these systems perform meaningful work, and you’ve raised the stakes considerably. Creating a pipeline of talented, well-trained academics and professionals who can meet those challenges was the subject of IBM’s July 28 virtual roundtable, “How to Build a Quantum Workforce.” Watch the replay, here.

Continue reading

Quantum Computing Education Must Reach a Diversity of Students

IBM recently launched several initiatives to help inspire new students and begin building tomorrow’s quantum computing workforce. Our Quantum Educators program, in particular, provides professors and students with access to IBM quantum computers as well as the latest learning resources we’ve developed to help them get started programming and experimenting on quantum computers.

Continue reading