Quantum computers are better at guessing, new study demonstrates

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.