Study Shows Quantum Computers Excel at Guessing.

Daniel Lidar, professor of engineering at the University of Southern California and director of the USC Center for Quantum Information Science and Technology, and Dr. Bebek Bukharel, research scientist at IBM Quantum, have achieved a quantum acceleration feature in the context of a “guessing the bit string” game.” They managed strings up to 26 feet in length. bits, which are much larger than previously possible, by effectively suppressing errors that typically appear on this scale (a bit is a binary number that is either a zero or a one). Their paper is published in the journal Physical review letters.

Quantum computers promise to solve certain problems with an advantage that increases as the problems get more complex. However, it is also highly susceptible to bugs or noise. Lidar says the challenge is to “get an edge in the real world where today’s quantum computers are still ‘annoying’.” This noisy state of current quantum computing is called the “NISQ” (Noisy Medium Scale Quantum Era). , a term adapted from the RISC architecture used to describe classical computing hardware. Thus, any current demonstration of a quantum velocity advantage necessitates noise reduction.

The more unknown variables there are in the problem, the harder it is for the computer to solve. Researchers can evaluate a computer’s performance by playing a kind of game with it to see how quickly an algorithm can guess hidden information. For example, 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 bit strings. 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, which makes guesses in a quantum superposition, can work out the correct answer in just one guess. This efficiency comes from running a quantum algorithm developed over 25 years ago by computer scientists Ethan Bernstein and Umesh Vazirani. However, noise can significantly hinder this exponential quantum feature.

Lidar and Bukharel achieved their quantum acceleration by adapting a noise-suppression technique called dynamic separation. They spent a year experimenting, with Bukharel working as a PhD candidate under lidar at the University of Southern California. At first, implementing dynamic separation seems to degrade performance. However, after many improvements, the quantum algorithm worked as intended. Then the problem-solving time grew more slowly than on any conventional computer, as the quantum advantage became increasingly apparent as the problems became more complex.

Lidar notes that “at the moment, classical computers can still solve the problem faster in absolute terms.” In other words, the reported feature is measured in terms of the time scale it takes to find the solution, not the absolute time. This means that for sufficiently long bit strings, the quantum solution will eventually be faster.

The study conclusively demonstrates that with appropriate error control, quantum computers can implement complete algorithms with a better measure of the time it takes to find the solution than conventional computers, even in the NISQ era.