The race to demonstrate “quantum supremacy” — a computational task possible for a quantum computer but not a classical computer — has dominated the media coverage of this exciting new technology. But while scientists debate the goalposts of this milestone (as well as its controversial name), some research groups explore a less flashy but still meaningful advance, “quantum advantage.” Here, the challenge is not to prove that a quantum computer can do something that no existing classical computer can pull off, but that the small-scale, noisy quantum computers of today can out-perform a similarly small-scale classical computer on a given challenge.
In Nature Physics this week, a group led by Sergey Bravyi of IBM Research published new findings that a “shallow” quantum algorithm can beat a similarly simple classical approach on a benchmark called a relation problem. This quantum speedup is limited — a more powerful classical computer can still solve it faster than the small-scale quantum device — but important for demonstrating that even today’s flawed quantum computers can have a leg up on their traditional peers, wrote Bill Fefferman in an invited perspective piece published by the journal alongside the research paper.
“I would call it an apples-to-apples comparison as compared with the apples-to-oranges comparison [of quantum supremacy],” said Fefferman, an assistant professor at UChicago CS. “They're showing that for this new type of problem, they can get a really big speed up even with the noise.”
Most theoretical demonstrations of quantum supremacy assume an idealized version of a quantum computer, which provides reliable and accurate results. But the quantum computers available today are far from that ideal, with less than 100 qubits (the quantum analogue of the traditional computer bit) and high amounts of noise and error for even simple calculations. Corralling that noise in order to produce useful applications is the grand challenge of Near-Term Intermediate-Scale Quantum (NISQ) computers, and a main research focus of the EPiQC research collaboration led by UChicago CS Professor Fred Chong.
Quantum advantage research tackles this noise problem in order to achieve its goal of beating similar-depth classical approaches. In his commentary, Fefferman credits the researchers with designing a noise-resilient solution that provides a quantum speedup even with the limitations of modern machines. But he cautions that their strategy is a restrictive error correction that works for the purpose at hand, but not much more generally, which leaves more challenges ahead for complex algorithms and quantum computers.
“The most important thing by far in near-term quantum computing is understanding noise, because we don't have the ability to error correct, and we may not have the ability to error correct for a long time,” Fefferman said. “So the big challenge that the community is facing is, what are we going to do with these devices that we know are really noisy? This paper shows one way to do it, and it's been remarkably successful, but it doesn't solve all the problems.”
The new Nature Physics study is also not a direct step on the path to quantum supremacy, given that it tackles a different sort of computational problem than the most popular benchmark test for proving a completely unique quantum achievement. Last year, Google announced “an experimental realization of quantum supremacy” based on the “random circuit sampling” test, which Fefferman helped analyze at the University of California, Berkeley. (“I think the jury is still out as to whether this is really quantum supremacy,” Fefferman told ScienceNews at the time.)
The new research uses a different sort of problem called a relation problem, where on a given input there is more than one correct answer. The analysis is inspired by the theory of non-local games in which “several players each have an input and try to produce outputs that satisfy a given relation without directly communicating with the other players.” Simple quantum circuits, thanks to their entanglement properties, can solve this puzzle, while simple classical computers cannot. But more complex classical computers are also capable of solving the problem, which actually makes life easier for researchers — they can confirm that the quantum computer found the right answer, which would be potentially impossible in the case of true quantum supremacy.
Because of these differences, Fefferman cautions quantum computing observers to be careful when reading media reports about the new finding. Due to growing discomfort with the loaded term “supremacy,” some scientists have started using “quantum advantage” instead, but the term in the IBM paper has a very specific meaning.
“For them, the advantage just means some speed up, it could mean a speed up over any sort of classical computer,” Fefferman said. “The fact that they can do that is very impressive. It's awesome. I'm just not sure it's quantum supremacy and neither are they.”