Dr. Bibek Pokharel, a Research Scientist at IBM Quantum, and Dr. Daniel Lidar, the Viterbi Professor of Engineering at USC and the Director of the USC Center for Quantum Information Science & Technology, collaborated to use quantum speedup in the setting of a “bitstring guessing game.”
By substantially reducing the kind of errors usually encountered at this scale, they were able to handle strings as long as 26 bits in length, which is a major improvement above previous limits. (In binary, each digit (or “bit”) can only be zero or one.
The advantage of quantum computers in solving particular issues is said to grow with the problem’s complexity. However, they are also quite vulnerable to mistakes and other forms of noise. According to Lidar, the obstacle is “to obtain an advantage in the real world where today’s quantum computers are still ‘noisy.'”
The current state of quantum computing, which is plagued by noise, has been given the moniker “NISQ” (Noisy Intermediate-Scale Quantum), a word borrowed from the RISC architecture used to characterize traditional computers. As a result, eliminating background noise is essential for any ongoing demonstration of the quantum speed advantage.
In general, a problem’s difficulty in being solved by a computer increases as the number of unknowns increases. Scholars can test the speed with which an algorithm can guess hidden information by playing a game with the computer. Take the popular TV show Jeopardy as an example; in one round, players take it in turns guessing a secret word of known length. After each guess, the host will disclose one accurate letter before switching the hidden word to something else.
The researchers in their study used bitstrings in place of words. To correctly identify a 26-bit string, a classical computer would need to make an average of about 33 million guesses. In contrast, a fully functional quantum computer would be able to determine the correct answer after making only a single guess, thanks to the quantum superposition of its guesses.
A quantum algorithm created by computer scientists Ethan Bernstein and Umesh Vazirani over 25 years ago is responsible for this efficiency. However, this exponential quantum advantage can be severely hampered by noise.
Lidar and Pokharel used a technique called dynamical decoupling to reduce noise and accomplish their quantum speedup. Pokharel spent a year experimenting as a doctorate student in Lidar’s lab at USC. At first, it appeared like implementing dynamical decoupling was slowing things down.
The quantum algorithm, however, worked as expected after extensive tweaking. As the complexity of the problem increased, the time required to solve it also increased more slowly than it would have with any traditional computer.
According to Lidar, “currently, classical computers can still solve the problem faster in absolute terms.” That is to say, the claimed benefit is expressed as a percentage of the scaled-up time it takes to locate the answer. That’s why the quantum solution will win out in the long run for bitstrings that are suitably long.
This study proves beyond a reasonable doubt that, with adequate error management, quantum computers can outperform classical computers in terms of scaling the time it takes to find a solution, even in the NISQ era.