A quantum advantage with noisy circuits

Friday, July 17, 2020

En français

New research shows that limited near-term quantum computers may be more powerful than they seem when solving a problem that is impossible for comparable classical computers.

Collaborators from the Institute for Quantum Computing (IQC) at the University of Waterloo, IBM, Technical University of Munich, and the University of Technology Sydney created an algorithm to solve a problem on a noisy quantum circuit that has a constant depth, meaning it has to solve the problem within a set upper limit of steps.

“We’re interested in constant-depth circuits because the kind of near-term quantum computers being built accumulate more errors the longer they operate,” said David Gosset, faculty member at IQC and in the Department of Combinatorics and Optimization at Waterloo’s Faculty of Math. “So, we want to look at restricted models of quantum computing that make the most of the ‘quantumness’ with the least computation.”

Correcting for errors caused by noise in a quantum circuit normally takes extra steps, losing the quantum advantage of solving the problem in a limited amount of time. The algorithm the researchers created corrects for errors at the same time as it solves the problem, allowing the circuit to remain constant depth. There is no classical algorithm that can solve the same problem using a constant-depth circuit, even one that is noise free. As the inputs into the problem grow, the classical circuit needs to grow logarithmically.

Think of it like driving a racetrack that is a set length, but the slope of the track keeps rising as you race. A quantum car—the researchers’ new algorithm—can keep on going, even dodging potholes along the way. A classical car will need to be tuned with more and more power as the slope increases, even with a perfect road.

The algorithm may be implementable in the future with quantum computers that are able to perform some of the basic elements of quantum error correction.

The quantum computers scientists will be able to build in the short-term will be very limited and noisy. If theoreticians develop better algorithms that can solve problems on a quantum circuit in a very small number of steps, then better results will be possible with these near-term quantum computers.

“The problem we’re solving with the circuit is not necessarily useful itself, but the fact that there is a quantum advantage is another piece of evidence that quantum computers may one day be able to surpass classical computers at certain tasks,” said Gosset.

Quantum advantage with noisy shallow circuits was published in Nature Physics July 6, 2020.