New! Sign up for our free email newsletter.
Science News
from research organizations

Quantum computers are better at guessing, new study demonstrates

Researchers leverage techniques to manage error accumulation, demonstrating the potential of quantum computing in the error-prone NISQ era

Date:
June 5, 2023
Source:
University of Southern California
Summary:
Researchers have demonstrated a quantum speedup over the most efficient classical computer algorithm possible for what is believed to be the first time.  The accomplishment was performed on an IBM Montreal Quantum Falcon r4 27-qubit device.
Share:
FULL STORY

Daniel Lidar, the Viterbi Professor of Engineering at USC and Director of the USC Center for Quantum Information Science & Technology, and first author Dr. Bibek Pokharel, a Research Scientist at IBM Quantum, achieved this quantum speedup advantage in the context of a "bitstring guessing game." They managed strings up to 26 bits long, significantly larger than previously possible, by effectively suppressing errors typically seen at this scale. (A bit is a binary number that is either zero or one).

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.


Story Source:

Materials provided by University of Southern California. Note: Content may be edited for style and length.


Journal Reference:

  1. Bibek Pokharel, Daniel A. Lidar. Demonstration of Algorithmic Quantum Speedup. Physical Review Letters, 2023; 130 (21) DOI: 10.1103/PhysRevLett.130.210602

Cite This Page:

University of Southern California. "Quantum computers are better at guessing, new study demonstrates." ScienceDaily. ScienceDaily, 5 June 2023. <www.sciencedaily.com/releases/2023/06/230605181221.htm>.
University of Southern California. (2023, June 5). Quantum computers are better at guessing, new study demonstrates. ScienceDaily. Retrieved March 2, 2024 from www.sciencedaily.com/releases/2023/06/230605181221.htm
University of Southern California. "Quantum computers are better at guessing, new study demonstrates." ScienceDaily. www.sciencedaily.com/releases/2023/06/230605181221.htm (accessed March 2, 2024).

Explore More
from ScienceDaily

RELATED STORIES