Quantum advantage with shallow circuits

Quantum computers can solve a linear algebra problem faster than classical computers, according to a new study published in Science. The finding proves that constant-depth quantum circuits are more powerful than their classical counterparts, and provides a new sense of how quantum technology will be a key to more powerful computing.

The study, conducted by a team of researchers at IBM T.J. Watson Research Center including Sergey Bravyi, IQC faculty member David Gosset, and Robert König of the Technical University of Munich (TUM) could also guide the way toward promising use cases for the next generation of quantum computers.

Scientists prove there are certain problems that require only a fixed circuit depth when done on a quantum computer no matter how the number of inputs increase. On a classical computer, these same problems require the circuit depth to grow larger.

What’s in a circuit?

A quantum circuit performs a quantum algorithm by applying a sequence of gates that operate on a small number of qubits. Gates acting on different subsets of qubits can be applied in parallel at each time step, as specified by the algorithm. The number of time steps is called the circuit depth.

“Understanding the power of circuits with very shallow depth is relevant in understanding the power of near-term computers,” explained Gosset, also an associate professor in the Department of Combinatorics and Optimization at the University of Waterloo. Near-term quantum computers without error-correction are limited in the size of computations they can perform. “When you’re limited in size, you either look at a small number of qubits, shallow circuit depth, or both,” Gosset said.

Quantum vs. classical

The team of researchers considered constant-depth circuits, meaning that the depth or number of time steps is independent of the number of qubits. They discovered that a quantum computation with a constant number of time steps – a constant-depth quantum circuit – could solve a certain linear algebra problem which they call the 2D Hidden Linear Function problem.

Furthermore, they demonstrated that no classical computation of constant depth could solve the same problem, providing evidence of a quantum advantage over classical computers.

Next steps

The quantum algorithm only requires circuits laid out on a two-dimensional grid, consistent with what is currently used in experimental settings, one-step closer to implementation on near-term devices.

The results also open up new possibilities for quantum algorithm development and raise the question of whether such a speedup can persist in the presence of noise processes that occur in currently available technology.