Quantum ‘echoes’ reveal the potential of Google’s quantum computer
The calculation is apparently out of reach for classical computers, and its result can be verified
Google's Willow chip (shown) performed a quantum calculation that has the potential to be efficiently verified, and which apparently can't be achieved with a classical computer.
For quantum computers to change the game of computation, scientists need to show that the machines’ calculations are correct. Now, there’s hope.
Google’s Willow quantum chip has achieved verifiable quantum advantage, a team of researchers claim. That’s a quantum calculation that’s apparently out of reach for a traditional, classical computer, but with a result that can be confirmed to be correct. The result of the calculation, reported October 22 in Nature, could be verified by another quantum computer — although it hasn’t been yet.
Verification is an essential step toward potential applications of quantum computers. “If I can’t prove to you that the data is correct, how can I do anything with it?” physicist Tom O’Brien of Google Quantum AI in Santa Barbara, Calif., said in an Oct. 17 news conference.
The calculation, measuring a phenomenon nicknamed “quantum echoes,” runs 13,000 times as fast on Willow as it would on the Frontier supercomputer — one of the most powerful in the world. The full set of calculations would demand about 150 years of Frontier’s time, making it infeasible to compute classically. It took just days of computing time on Willow.
“It’s pretty convincing that to simulate this [with a classical computer] you would need some combination of huge computing effort and some algorithmic advances that people haven’t come up with yet, but it’s not crazy to imagine that they would,” says quantum physicist Aram Harrow of MIT, who was not involved with the research. Previous claims of quantum advantage have frequently been followed up by improved classical computations that erase that advantage.
Some other quantum advantage claims have had a level of verification, but that verification was inefficient, says computer scientist Scott Aaronson of the University of Texas at Austin, who was not involved with the research. For example, as a calculation increases in size, the time it takes to verify it grows exponentially. Google’s new calculation would be efficient to verify, given another quantum computer of similar capabilities.
Efficiently verifiable quantum advantage has been one of the biggest challenges facing the field in recent years, Aaronson says. “This is a decent candidate.”
Even better, Harrow says, would be an algorithm that could be verified by a classical computer, rather than another quantum computer. For example, one of the most famous applications of quantum computers, Shor’s algorithm, is easy to check. It splits an extremely large integer into two prime factors. For large numbers, this task would take an impractically long amount of time on a classical computer. The difficulty in calculating those prime numbers is the foundation of the encryption that keeps internet data secure. But a powerful enough quantum computer running Shor’s algorithm could deduce those primes. Once it did, a classical computer could simply multiply them together to check that it matches original number.
Quantum echoes aren’t that simple. Known scientifically as out-of-time-order correlators, quantum echoes are a signature of chaos in a system. It’s “kind of a butterfly effect, where you poke something in one place and then very far away at a later time, there’s a disturbance,” Harrow says.
Calculating quantum echoes involves performing a variety of random operations on the computer’s quantum bits, or qubits. Those operations are then reversed, effectively running time backward to the beginning. This is what allows the researchers to get a verifiable signal out of the chaotic system, which would otherwise wash out information.
A quantum ‘butterfly effect’
The butterfly effect–like quantum echoes measured on Google’s Willow chip (illustrated) result from a series of operations on qubits. First, random operations are applied on the qubits (yellow). Then, one “butterfly” qubit is perturbed (dark purple). The operations are reversed (yellow), and the result is read out (light purple). The new work’s quantum advantage calculation used 65 qubits out of the 105-qubit array pictured.
The researchers used 65 of Willow’s qubits for the quantum echo calculation, running the operations forward and in reverse, twice. Before each time reversal, a few of the qubits were tweaked. The technique produces a complex quantum interference effect that is difficult to compute classically.
The researchers argue that their algorithm is a step toward practical uses for quantum computers. In a not yet peer-reviewed paper, to post on arXiv.org on October 22, Google researchers and collaborators use the technique to compute how certain portions of two molecules are arranged relative to one another in 3-D space. The demonstrations agreed with results from a typical lab technique — nuclear magnetic resonance. However, they don’t yet outpace classical calculations.
Still, Harrow says, “connecting their quantum computer to a real experiment is very nice to see.”
