How to show quantum advantage in a noisy quantum computer

In their work on quantum advantage, CQT Principal Investigator Marco Tomamichel and his collaborators investigated shallow circuits, which have constant circuit depth and are found in noisy quantum devices. Image: Quardia/Shutterstock.com

Quantum advantage can survive noise in the machine, according to research by CQT Principal Investigator Marco Tomamichel and his collaborators. The researchers have shown the first known separation in computational power between noisy quantum computers and classical computers that does not rely on assumptions about the classical hardness of the underlying problem.

The team published their findings in Nature Physics on 6 July 2020. Marco holds a joint appointment with CQT and the Department of Electrical and Computer Engineering at the National University of Singapore, where he is an Associate Professor. Marco’s collaborators are Sergey Bravyi from the IBM T J Watson Research Center in the United States, David Gosset from the Institute for Quantum Computing at the University of Waterloo in Canada and Robert König from the Institute for Advanced Study and Zentrum Mathematik at the Technical University of Munich in Germany.

While a universal practical quantum computer is still many decades, and millions of qubits, away, noisy intermediate-scale quantum computers – otherwise known as NISQ devices – are already here. Noise shows up as errors in the qubits arising from imperfect control and influence of their physical environment on their delicate states.

There is a push to find out where NISQ devices may have a quantum advantage over classical computers. To demonstrate quantum advantage, researchers need to show that a quantum computer can solve a given computational problem much more efficiently than a classical computer could manage.

Advantage quantum

In October 2019, the quantum team at Google reported quantum advantage in a calculation run on 53 qubits. They achieved an experimental speed-up over the best-known classical algorithms for a particular problem, but that leaves a question mark over whether better classical algorithms could yet be discovered. This relates to the computational complexity class of the problem. The problem the Google team considered is widely believed to be hard for classical computers, but nobody knows how to show this conclusively.

In their work, Marco and his collaborators consider a simpler problem for which an advantage could be definitively shown because they can prove that the problem is not too easy for classical computers. They do not have to make any complexity-theoretic assumptions.

Specifically, Marco and his collaborators looked at a variant of a problem known as the quantum magic square game, embedded in circuits of qubits. The magic square game is won when two players, without communicating with each other, achieve a common goal. In the circuit version, potential players are inputs to the circuit and the game needs to be won for all possible combinations of players. The more potential players, the more difficult the problem becomes.

The researchers were able to show that a noisy quantum device could win the game using a constant circuit depth, also known as a shallow circuit, whatever the number of players. Depth refers to how many layers of physical gates the quantum device needs to implement on the qubits to solve the problem, from start to end. In this case, the number of layers needed to solve the problem remains the same no matter how large the number of potential players grows.

In contrast, any classical circuit trying to solve these problems would need a circuit depth that grows at least logarithmically in the problem size – advantage quantum.

Their work also considered the geometry of the circuits, which describes how the qubits in a device are connected to each other. The researchers demonstrated quantum advantage in shallow circuits with one-dimensional geometry. This simplifies results of previous work with two-dimensional geometric circuits. A one-dimensional geometry means that the qubits of the circuit are arranged in a line while a two-dimensional geometry means that the qubits are arranged in a grid.

“In some device architectures, connections between qubits do not form a complete two-dimensional grid and does not allow for general two-qubit gates,” says Marco. “We can do less with one-dimensional circuits – that’s why getting a quantum advantage even with such restricted circuits is stronger.”

Coping with noise

One of the main challenges of the project was showing that the quantum advantage persists with noise.

To beat noise, the team found that shallow circuits needed a three-dimensional geometry. They also needed new techniques.

Techniques to manage noise in quantum computers are known as quantum error correction codes. However, such techniques usually need quantum circuits of at least logarithmic depth.

To get around this, the researchers came up with an error correcting code that works by measuring a so-called cluster state. This cluster state can be prepared in constant depth circuits. The main idea is that error correction does not need to be performed as a quantum circuit. Because it does not matter whether error correction is performed before or after each layer of gates – the steps commute – the correction can be deferred until after all the gates. “We can push it after the measurement step, meaning we just need to manipulate the classical measurement results,” explains Marco.

“Some of these ideas are new and should be useful for NISQ algorithms in general as they give us a means to achieve fault-tolerance even for constant depth circuits,” Marco says.

The team’s work is all theoretical so far, but they suggest their streamlined algorithm is amenable to experimental implementation on near-term quantum computers.