IBM 16 Qubit Processor” by IBM Research, licensed under CC BY-ND 2.0

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.”

Related News

More UChicago CS stories from this research area.
Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
UChicago CS News

Assistant Professor Robert Rand Receives Air Force Young Investigator Grant

Dec 19, 2022
Professor Fred Chong advising students
UChicago CS News

Prof. Fred Chong Reappointed to National Quantum Initiative Advisory Committee

Dec 13, 2022
UChicago CS News

Professor Fred Chong Named IEEE Fellow

Dec 09, 2022
UChicago CS News

Associate Professor Diana Franklin Named ACM Distinguished Member

Dec 07, 2022
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
In the News

Alumnus Pranav Gokhale Named to Crain’s 40 Under 40

Nov 07, 2022
UChicago CS News

Prof. Diana Franklin Discusses Quantum Computing Education on Entangled Things Podcast

Nov 03, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

High School Students in College Prep Program Visit UChicago CS

Aug 23, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube