The first author, Dr. Bibek Pokharel, a Research Scientist at IBM Quantum, and Daniel Lidar, the Viterbi Professor of Engineering at USC and Director of the USC Center for Quantum Information Science & Technology, established this quantum speedup advantage in the setting of a “bitstring guessing game.”
They successfully suppressed mistakes that are generally present at this scale, allowing them to manage strings up to 26 bits long a huge increase over what was previously achievable. (A bit is a binary number that is either zero or one).
Quantum computers offer to tackle particular issues with an advantage that grows as the complexity of the problems decreases. 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. Therefore, noise reduction is required for any current quantum speed advantage demonstration.
The difficulty of a task for a computer to solve typically increases with the number of unknown variables. By using it to play a game to discover how quickly an algorithm can guess secret information, academics can assess a computer’s performance.
Consider a Jeopardy-style game show where players alternately predict a secret word of known length, one entire word at a time. For each correctly predicted word, the host only displays one letter before changing the secret word at random.
In their study, the researchers replaced words with bitstrings. A traditional computer would typically need 33 million guesses to successfully recognize a 26-bit string. In contrast, a fully operational quantum computer may find the right response with just one guess when given guesses in quantum superposition.
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 quantum advantage then became increasingly apparent as the issues became more complicated, with the time to solve problems growing more slowly than with any classical computer.
Lidar notes that “currently, classical computers can still solve the problem faster in absolute terms.” In other words, rather than using the actual amount of time, the reported advantage is calculated using the time-scaling required to locate the solution. This implies that the quantum solution will eventually be faster for sufficiently long bitstrings.
The work unequivocally establishes that, even in the NISQ era, quantum computers, with appropriate error control, can execute entire algorithms with superior scaling of the time it takes to find the answer than conventional computers.
