Dr. Bibek Pokharel, a Research Scientist at IBM Quantum, and Daniel Lidar, the Viterbi Professor of Engineering at USC and Director of the USC Centre for Quantum Information Science & Technology, have realized a quantum speedup advantage in the setting of a “bitstring guessing game.” Errors commonly observed at this scale were efficiently suppressed, allowing them to handle strings as long as 26 bits in length. A bit is a unit of information in binary notation (a binary integer can only be a zero or a one). Physical Review Letters has published its paper.
The advantage of quantum computers in solving particular issues is said to grow with the problem’s complexity. They are, nevertheless, extremely vulnerable to inaccuracy or noise. Lidar explains the difficulty as “to obtain an advantage in the real world where today’s quantum computers are still ‘noisy.'” Taking a cue from the RISC architecture used to describe traditional computers, the current state of quantum computing has been dubbed the “NISQ” (Noisy Intermediate-Scale Quantum) era. Noise reduction is thus required for any current demonstration of the quantum speed advantage.
In general, the greater the number of variables in a problem, the more challenging it is for a computer to find an answer. Researchers can gauge a computer’s efficacy by challenging it to a game designed to reveal concealed information as rapidly as possible using an algorithm. Think of a game show like Jeopardy in which players take turns guessing a secret phrase of known length by pronouncing it aloud one letter at a time. After each guess, the host will reveal just one accurate letter before switching up the secret word at random.
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 only need to make one guess to get the correct solution when presenting guesses in quantum superposition. 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 while a doctorate student in Lidar’s lab at the University of Southern California. 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 ratio of how much longer it takes to locate the solution relative to how much longer it takes in absolute terms. This means that in the long run, the quantum solution will be faster for bitstrings that are suitably long.
The research 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.
