A significant breakthrough has been made in the realm of quantum computing, as scientists successfully achieved a quantum speedup by effectively mitigating errors in a bitstring guessing game. This advancement allowed them to handle strings as long as 26 bits, showcasing the superior time-scaling capabilities of quantum computers compared to their classical counterparts, even in the current era of quantum computing characterized by noise.
The research conducted at USC focused on implementing strategies to control and suppress the accumulation of errors, highlighting the potential of quantum computing in the error-prone NISQ era.
Daniel Lidar, the Viterbi Professor of Engineering at USC and Director of the USC Center for Quantum Information Science & Technology, along with Dr. Bibek Pokharel, a Research Scientist at IBM Quantum and the first author of the study, successfully demonstrated the quantum speedup advantage within the framework of a “bitstring guessing game.”
By effectively managing and mitigating errors commonly encountered at this level, they achieved successful manipulation of bitstrings up to a length of 26 bits, surpassing previous limitations. (For context, a bit refers to a binary digit that can represent either a zero or a one.)
Quantum computers hold the promise of solving specific problems with increasing advantage as the complexity of the problems grows. However, they are susceptible to errors and noise. Lidar emphasizes the challenge of gaining an advantage in the real world where current quantum computers still operate in a noisy environment.
The current noise-prone condition of quantum computing is referred to as the “NISQ” (Noisy Intermediate-Scale Quantum) era, a term borrowed from the RISC architecture used to describe classical computing devices. Therefore, any demonstration of quantum speed advantage in the present context requires effective noise reduction.
Typically, the more unknown variables a problem possesses, the more difficult it becomes for a computer to solve. Researchers evaluate a computer’s performance by engaging in a form of game to gauge how quickly an algorithm can guess hidden information. For instance, envision a version of the television game show Jeopardy, where contestants take turns guessing a secret word of known length, one complete word at a time. The host only reveals one correct letter for each guessed word before randomly changing the secret word.
In their study, the researchers replaced words with bitstrings. On average, a classical computer would require approximately 33 million guesses to correctly identify a 26-bit string. In contrast, a perfectly functioning quantum computer, leveraging quantum superposition, could pinpoint the correct answer in just a single guess. This efficiency stems from running a quantum algorithm developed more than 25 years ago by computer scientists Ethan Bernstein and Umesh Vazirani. However, noise significantly hampers this exponential quantum advantage.
Lidar and Pokharel achieved their quantum speedup by adapting a noise suppression technique known as dynamical decoupling. The two researchers spent a year conducting experiments, with Pokharel serving as a doctoral candidate under Lidar’s guidance at USC. Initially, the application of dynamical decoupling appeared to degrade performance. However, after numerous refinements, the quantum algorithm functioned as intended. The time required to solve problems then increased at a slower pace compared to any classical computer, with the quantum advantage becoming increasingly apparent as the complexity of the problems grew.
Lidar acknowledges 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 required to find the solution, not the absolute time. This means that for sufficiently long bitstrings, the quantum solution will eventually outpace classical methods.
The study conclusively demonstrates that, with effective error control, quantum computers can execute complete algorithms with superior scaling of the time required to find solutions compared to conventional computers, even in the NISQ era.
Reference: “Demonstration of Algorithmic Quantum Speedup” by Bibek Pokharel and Daniel A. Lidar, 26 May 2023, Physical Review Letters. DOI: 10.1103/PhysRevLett.130.210602
The study received funding from the National Science Foundation and the U.S. Department of Defense.
Table of Contents
Frequently Asked Questions (FAQs) about quantum speedup
What is quantum speedup?
Quantum speedup refers to the enhanced computational capabilities of quantum computers compared to classical computers. It allows quantum computers to solve certain problems more efficiently and quickly, especially as the complexity of the problems increases.
How did scientists achieve quantum speedup in this study?
In this study, scientists achieved quantum speedup by effectively mitigating errors in a bitstring guessing game. They employed strategies such as error control and the use of dynamical decoupling to suppress errors and improve the performance of quantum algorithms, allowing them to handle longer bitstrings and outperform classical computers in terms of time-scaling.
What is the NISQ era in quantum computing?
The NISQ era stands for Noisy Intermediate-Scale Quantum era. It refers to the current state of quantum computing where quantum devices are still prone to noise and errors. While quantum computers show promise, they are not yet fully error-corrected or fault-tolerant. The NISQ era focuses on exploring and harnessing the computational capabilities of these noisy quantum systems.
How does quantum speedup compare to classical computing?
Quantum speedup, as demonstrated in this study, shows that for sufficiently long bitstrings, quantum computers can eventually outperform classical computers in terms of time required to find the solution. While classical computers may still be faster in absolute terms for certain problems, quantum speedup showcases the potential for quantum computers to scale better and solve complex problems more efficiently.
What are the implications of this study?
This study highlights the importance of error control techniques in achieving quantum speedup in the NISQ era. It provides valuable insights into the capabilities of quantum computers and their potential to outperform classical computers in solving certain problems. Further research and development in error mitigation strategies can pave the way for practical applications of quantum computing in various fields.
More about quantum speedup
- Physical Review Letters: “Demonstration of Algorithmic Quantum Speedup”
- USC Center for Quantum Information Science & Technology
- IBM Quantum
- National Science Foundation
- U.S. Department of Defense
