The story so far: In two papers published in Nature on October 22, researchers from Google, MIT, Stanford, and Caltech reported what they called a verifiable display of quantum advantage using the company's Willow quantum processor. That is, the teams said they have shown that Willow clearly outperforms existing supercomputers on solving a specific problem.

How does a quantum computer work?

Imagine waves moving in a pond. When two wave crests meet, they combine to make a bigger wave. When a crest meets a trough, they cancel each other out. This is called interference. At the quantum level, particles can behave like waves and their "wave functions", which describe their probabilities, can be made to interfere with one another. By controlling this interference, scientists can amplify the probability of finding the right answer to a problem while cancelling out the wrong ones. This is what a quantum computer does.

In one of the two new studies, researchers introduced a quantum algorithm designed to solve optimisation problems, which are puzzles where the goal is to find the best possible solution among many. The research team called it Decoded Quantum Interferometry (DQI).

DQI uses a quantum version of the Fourier transform to manipulate the wave-like nature of particles that the quantum computer uses as its bits. This process is engineered such that the waves corresponding to good solutions interfere constructively, reinforcing each other to create a strong signal. Meanwhile, the waves for bad solutions interfere destructively and fade out. By measuring the final state, the algorithm will have a higher chance of landing on a 'high-quality' answer. The researchers showed that for the optimal polynomial intersection problem, the DQI algorithm could find a good approximation much faster than any known classical computer.

Entanglement breakthrough brings quantum computers closerWhat is scrambling?

In the second study, the authors measured how information becomes scrambled in a complex quantum system. Say you drop a small amount of dark blue dye into a still swimming pool. At the first moment, the 'information' is simple and local. "The blue dye is right here," you can say. But the dye doesn't stay there: it spreads out. The information is no longer in one place but distributed across a larger volume of water. After a few hours, the entire pool has a faint, uniform blue tint. You can no longer see the original drop. The information seems to be gone -- but it isn't. It's been scrambled. Every single water molecule in the pool now carries an almost imperceptible piece of that "blue" information.

This is what happens in a quantum system. A piece of information, initially stored in one quantum bit, gets spread out across all the other bits as they interact. The information becomes 'hidden' in the complex relationships between all the particles. So the challenge is: how do you measure a pattern that's so intricately hidden?

To do this, the researchers used a clever experiment. Imagine you're standing in a large, empty warehouse. You shout. The sound waves spread out instantly, bouncing off every wall, the floor, and the ceiling. This is the scrambling: the sound's information is now everywhere. Now, while your shout is still echoing around, your friend on the far side of the warehouse strikes a large metal bell with a hammer. This 'kick' doesn't stop the echoes but it changes them. Any sound wave from your shout that happens to hit that specific bell at that exact moment now gets a little 'imprint' in the form of a faint metallic ring. Then, the researchers did the equivalent of hitting a magical rewind button that caused all the sound waves to travel perfectly backward. All the normal echoes, the ones that didn't hit the bell, trace their paths back perfectly and cancel each other out upon returning, resulting in complete silence.

However, the imprinted echoes are now slightly off-course. When they travel backward, they don't cancel out properly, and the researchers are left hearing a very faint, jumbled echo -- one carrying the imprint of the kick. That leftover sound is the OTOC measurement, and this process of different paths mixing and cancelling (or not) is called interference.

Willow is a small chip for Google but a quantum leap for computing

By measuring the faintness and character of that leftover echo, the scientists could tell exactly how much the information had spread out and interacted with that specific part of the system (the bell). This is how they successfully measured the subtle, hidden patterns of scrambled information.

How do you show quantum advantage?

The second experiment involved circuits so intricate that researchers estimated simulating them on the world's second fastest supercomputer would have taken more than three years. The Willow processor completed the same task in about two hours. This said, while the first paper described a quantum algorithm that solved a puzzle much faster than any known classical computer, researchers haven't mathematically proven that a clever trick for a regular computer to solve the same puzzle quickly doesn't exist. New research will be needed to prove the problem is permanently hard for all non-quantum computers.

Likewise, while the second paper showed a quantum computer solving a complex problem, the next step will be for an independent team to use the same method to solve an actual unsolved problem in, say, physics or chemistry.

Finally, while the two studies mark a decisive step, their applications remain largely prospective. These are still lab-designed tasks whose outputs don't yet translate to scientific discoveries. The next stage will depend on improving other parts of quantum computing, including error correction and scaling to thousands of reliable quantum bits. These are widely expected to take several years more.

What did Google claim in 2019?

In a 2019 experiment, Google researchers used a quantum system to attempt to solve a problem called random circuit sampling. Here, its Sycamore processor ran a random programme generating a list of answers, with the challenge of predicting which of those answers would appear most frequently. However, researchers can't check a single answer in random circuit sampling, if the statistical distribution of all the answers looks correct. On the other hand, the problem the new test solved concerned a scientifically meaningful physical quantity.

How quantum computing can make large language models even better

The result was also said to be "verifiable" because the same problem can be run on a classical computer or another quantum computer, and verifying the answer doesn't depend on statistical patterns. One likely early application of the findings is in Hamiltonian learning, the process of inferring unknown parameters of a physical system by comparing experimental data with simulated outcomes. The same principles that this year's physics Nobel Prize laureates developed are what make processors like Willow possible. One of the laureates, Michel Devoret, is the chief scientist of quantum hardware at Google Quantum AI. The new studies built on the laureates' work to solve an optimisation problem and then to track how information spreads in quantum systems.

What is Google's 'quantum advantage' leap? | Explained