Newswise — Daniel Lidar, the Viterbi Chair of Engineering at USC and Head of the USC Center for Quantum Information Science & Technology, along with Dr. Bibek Pokharel as the primary author, an IBM Quantum Research Scientist, accomplished this quantum acceleration benefit within a "bitstring guessing game." They proficiently mitigated errors commonly observed at this magnitude, enabling successful handling of bitstrings as extensive as 26 bits, a considerable improvement from prior limitations. (A bit denotes a binary digit, either zero or one).
Quantum machines offer the potential to tackle increasingly complex problems with a growing advantage. Nevertheless, they are susceptible to errors and noise. Lidar emphasizes that the real challenge lies in "attaining an advantage within the current 'noisy' state of quantum computers." This state, characterized by noise vulnerability, is referred to as the "NISQ" (Noisy Intermediate-Scale Quantum) era, drawing inspiration from the RISC architecture employed in classical computing systems. Consequently, any existing showcase of quantum speed advantage requires the reduction of noise.
The level of difficulty in solving a problem typically increases with the number of unknown variables involved. To assess the performance of a computer, researchers often engage in a form of game where they measure how efficiently an algorithm can guess concealed information. For example, consider a variation of the popular TV game Jeopardy, where participants take turns attempting to guess a secret word of known length, providing an entire word at a time. The host, in this scenario, discloses only one correct letter for each guessed word before randomly altering the secret word.
During their investigation, the researchers substituted words with bitstrings. According to their findings, a classical computer would need around 33 million attempts, on average, to accurately determine a 26-bit string. In contrast, an ideally functioning quantum computer, employing quantum superposition to generate guesses, could ascertain the correct answer in a single attempt. This exceptional efficiency is achieved through the utilization of a quantum algorithm developed over 25 years ago by computer scientists Ethan Bernstein and Umesh Vazirani. However, the presence of noise can greatly impede this exponential quantum advantage.
Lidar and Pokharel accomplished their quantum acceleration by implementing a noise suppression method known as dynamical decoupling. Their research involved a year-long endeavor, during which Pokharel collaborated with Lidar as a doctoral candidate at USC. Initially, the application of dynamical decoupling appeared to diminish performance. However, through iterative improvements, the quantum algorithm started functioning as intended. Subsequently, the time required to solve problems began to increase at a slower pace compared to any classical computer, highlighting the growing quantum advantage as the complexity of the problems escalated.
Lidar acknowledges that "presently, classical computers can still outperform in terms of absolute speed in solving the problem." In other words, the advantage reported is measured in terms of the time scaling required to discover the solution, rather than the absolute time taken. This implies that for bitstrings of sufficient length, the quantum solution will eventually surpass the classical solution in terms of speed.
The study provides conclusive evidence that, given effective error control, quantum computers can execute entire algorithms with superior time scaling in finding solutions compared to conventional computers, even within the NISQ era.
RSS