Daniel Lidar, the Viterbi Professor of Engineering at USC and Director of the USC Center for Quantum Information Science & Technology, and the first author, Dr. Bibek Pokharel, a Research Scientist at IBM Quantum, have achieved a quantum speedup advantage in a game where participants guess bitstrings. They were able to handle strings up to 26 bits long, a significant improvement compared to previous attempts, by effectively reducing errors commonly seen at this scale. (A bit is a binary number that is either zero or one).
Quantum Computers and Noise Reduction
Quantum computers offer the potential to solve increasingly complex problems with greater efficiency. However, they are highly susceptible to errors and noise. The main challenge, according to Lidar, is “to achieve an advantage in the real world with the current noisy quantum computers.” This noise-prone condition in current quantum computing is referred to as the “NISQ” (Noisy Intermediate-Scale Quantum) era. Therefore, any demonstration of a quantum speed advantage requires noise reduction.
The Bitstring Guessing Game
In order to evaluate a computer’s performance, researchers often use games to test their algorithm’s ability to guess hidden information quickly. In this study, the researchers conducted a variant of the TV game Jeopardy. Participants took turns guessing a secret bitstring of known length, one bit at a time. The game host would reveal only one correct bit for each guessed bitstring before randomly changing the secret bitstring.
Instead of words, the researchers used bitstrings in their study. A classical computer would require approximately 33 million guesses, on average, to correctly identify a 26-bit string. In contrast, a perfectly functioning quantum computer, using quantum superposition, could guess the correct answer in just one attempt. This exponential efficiency is based on a quantum algorithm developed more than 25 years ago by computer scientists Ethan Bernstein and Umesh Vazirani. However, noise significantly hampers this quantum advantage.
Noise Suppression Technique and Quantum Speedup
Lidar and Pokharel achieved quantum speedup by utilizing a technique called dynamical decoupling to suppress noise. They spent a year experimenting with this technique, with Pokharel working as a doctoral candidate under Lidar at USC. Initially, applying dynamical decoupling seemed to reduce performance. However, after several refinements, the quantum algorithm functioned as intended. The time required to solve problems then increased at a slower rate compared to any classical computer, making the quantum advantage more evident as the problems became more complex.
It is important to note that “currently, classical computers can still find the solution faster in absolute terms,” says Lidar. The reported advantage is measured in terms of the time-scaling it takes to find the solution, rather than the absolute time. This means that for sufficiently long bitstrings, the quantum solution will eventually be quicker.
This study conclusively demonstrates that with proper error control, quantum computers can execute complete algorithms more efficiently than conventional computers, even in the NISQ era.