Scientists achieved a quantum speedup by effectively suppressing errors in a bitstring guessing game, managing strings up to 26 bits long. They showed that, with proper error control, quantum computers can execute full algorithms with better time-scaling than conventional computers, even in the current noisy era of quantum computing.
Researchers at Founded in 1880, the University of Southern California is one of the world’s leading private research universities. It is located in the heart of Los Angeles.
” data-gt-translate-attributes=”[{[{“attribute”:”data-cmtooltip”, “format”:”html”}]”>USC apply strategies to control the buildup of errors, showcasing the promise of quantum computing in the error-prone NISQ era.
Daniel Lidar, the Viterbi Professor of Engineering at USC and Director of the USC Center for Quantum Information Science & Technology, and first author Dr. Bibek Pokharel, a Research Scientist at IBM Quantum, achieved this quantum speedup advantage in the context of a “bitstring guessing game.”
By effectively mitigating the errors often encountered at this level, they have successfully managed bitstrings of up to 26 bits long, significantly larger than previously possible. (For context, a bit refers to a binary number that can either be a zero or a one).
Quantum computers promise to solve certain problems with an advantage that increases as the problems increase in complexity. However, they are also highly prone to errors, or noise. The challenge, says Lidar, is “to obtain an advantage in the real world where today’s quantum computers are still ‘noisy.’”
This noise-prone condition of current quantum computing is termed the “NISQ” (Noisy Intermediate-Scale Quantum) era, a term adapted from the RISC architecture used to describe classical computing devices. Thus, any present demonstration of quantum speed advantage necessitates noise reduction.
The more unknown variables a problem has, the harder it usually is for a computer to solve. Scholars can evaluate a computer’s performance by playing a type of game with it to see how quickly an algorithm can guess hidden information. For instance, imagine a version of the TV game Jeopardy, where contestants take turns guessing a secret word of known length, one whole word at a time. The host reveals only one correct letter for each guessed word before changing the secret word randomly.
In their study, the researchers replaced words with bitstrings. A classical computer would, on average, require approximately 33 million guesses to correctly identify a 26-bit string. In contrast, a perfectly functioning quantum computer, presenting guesses in quantum superposition, could identify the correct answer in just one guess. This efficiency comes from running a quantum algorithm developed more than 25 years ago by computer scientists Ethan Bernstein and Umesh Vazirani. However, noise can significantly hamper this exponential quantum advantage.
Lidar and Pokharel achieved their quantum speedup by adapting a noise suppression technique called dynamical decoupling. They spent a year experimenting, with Pokharel working as a doctoral candidate under Lidar at USC. Initially, applying dynamical decoupling seemed to degrade performance. However, after numerous refinements, the quantum algorithm functioned as intended. The time to solve problems then grew more slowly than with any classical computer, with the quantum advantage becoming increasingly evident as the problems became more complex.
Lidar notes that “currently, classical computers can still solve the problem faster in absolute terms.” In other words, the reported advantage is measured in terms of the time-scaling it takes to find the solution, not the absolute time. This means that for sufficiently long bitstrings, the quantum solution will eventually be quicker.
The study conclusively demonstrates that with proper error control, quantum computers can execute complete algorithms with better scaling of the time it takes to find the solution than conventional computers, even in the NISQ era.
Reference: “Demonstration of Algorithmic Quantum Speedup” by Bibek Pokharel and Daniel A. Lidar, 26 May 2023, Physical Review Letters.
DOI: 10.1103/PhysRevLett.130.210602
The study was funded by the National Science Foundation and the U.S. Department of Defense.
