New Protocol Demonstrates and Verifies Quantum Speedups in a Jiffy
- Details
- Category: Research News
- Published: Monday, June 09 2025 09:00
While breakthrough results over the past few years have garnered headlines proclaiming the dawn of quantum supremacy, they have also masked a nagging problem that researchers have been staring at for decades: Demonstrating the advantages of a quantum computer is only half the battle; verifying that it has produced the right answer is just as important.
Now, researchers at JQI and the University of Maryland (UMD) have discovered a new way to quickly check the work of a quantum computer. They proposed a novel method to both demonstrate a quantum device’s problem-solving power and verify that it didn’t make a mistake. They described their protocol in an article published March 5, 2025, in the journal PRX Quantum.
“Perhaps the main reason most of us are so excited about studying large interacting quantum systems in general and quantum computers in particular is that these systems cannot be simulated classically,” says JQI Fellow Alexey Gorshkov, who is also a Fellow of the Joint Center for Quantum Information and Computer Science (QuICS), a senior investigator at the National Science Foundation Quantum Leap Challenge Institute for Robust Quantum Simulation (RQS) and a physicist at the National Institute of Standards and Technology. “Coming up with ways to check that these systems are behaving correctly without being able to simulate them is a fun and challenging problem.”
Researchers have proposed a new way to both demonstrate and verify that quantum devices offer real speedups over ordinary computers. Their protocol might be suitable for near-term devices made from trapped ions or superconducting circuits, like the one shown above. (Credit: Kollár Lab/JQI)
In December 2024, Google announced its newest quantum chip, called Willow, accompanied by a claim that it had performed a calculation in five minutes that would have taken the fastest supercomputers 10 septillion years. That disparity suggested a strong demonstration of a quantum advantage and hinted at blazing fast proof that quantum computers offer exponential speedups over devices lacking that quantum je ne sais quoi.
But the problem that the Willow chip solved—a benchmark called random circuit sampling that involves running a random quantum computation and generating many samples of the output—is known to be hard to verify without a quantum computer. (Hardness in this context means that it would take a long time to compute the verification.) The Google team verified the solutions produced by their chip for small problems (problems with just a handful of qubits) using an ordinary computer, but they couldn’t come close to verifying the results of the 106-qubit problem that generated the headlines.
Fortunately, researchers have also discovered easy-to-verify problems that can nevertheless demonstrate quantum speedups. Such problems are hard for a classical (i.e., non-quantum) computer but easy for a quantum computer, which makes them prime candidates for showing off quantum prowess. Crucially, these problems also allow a classical computer to quickly check the work of the quantum device.
Even so, not every problem with these features is practical for the quantum computers that exist right now or that will exist in the near future. In their new paper, the authors combined two key earlier results to construct a novel protocol that is more suitable for demonstrating and verifying the power of soon-to-be-built quantum devices.
One of the earlier results identified a suitable problem with the right balance of being difficult to solve but easy to verify. Solving that problem amounts to preparing the lowest energy state of a simple quantum system, measuring it, and reporting the outcomes. The second earlier result described a generic method for verifying a quantum computation after it has been performed—a departure from standard methods that require a live back-and-forth while the computation is running. Together, the two results combined to significantly cut down the number of repetitions needed for verification, from an amount that grows as the square of the number of qubits down to a constant amount that doesn’t grow at all.
“We combined them together and, somewhat unexpectedly, this also reduced the sample complexity to a really low level,” says Zhenning Liu, the lead author of the new paper and a graduate student at QuICS.
The resulting protocol can run on any sufficiently powerful quantum computer, but its most natural implementation is on a particular kind of device called an analog quantum simulator.
Generally, quantum computers, which process information held by qubits, fall into two categories. There are digital quantum computers, like Google’s Willow chip, that run sequences of quantum instructions and manipulate qubits with discrete operations, similar to what ordinary digital computers do to bits. And then there are analog quantum computers that initialize qubits and let them evolve continuously. An analog quantum simulator is a special-purpose analog quantum computer.
Liu and his colleagues—inspired by the kinds of quantum devices that are already available and driven by one of the primary research goals of RQS—focused on demonstrating and verifying quantum advantage on a subset of analog quantum simulators.
In particular, their protocol is tailored to analog quantum simulators capable of hosting simple nearest-neighbor interactions between qubits and making quantum measurements of individual qubits. These capabilities are standard fare for many kinds of experimental qubits built out of trapped ions or superconductors, but the researchers required one more ingredient that might be harder to engineer: an interaction between one special qubit—called the clock qubit—and all of the other qubits in the device.
“Quantum simulators will only be useful if we can be confident about their results,” says QuICS Fellow Andrew Childs, who is also the director of RQS and a professor of computer science at UMD. “We wanted to understand how to do this with the kind of simulators that can be built today. It's a hard problem that has been a lot of fun to work on.”
Assuming an analog quantum simulator with all these capabilities could be built, the researchers described a protocol to efficiently verify its operation by following a classic two-party tale in computer science. One party, the prover, wants to convince the world that their quantum device is the real deal. A second party, the verifier, is a diehard skeptic without a quantum computer who wants to challenge the prover and ascertain whether they are telling the truth.
In the future, a practical example of this kind of interaction might be a customer accessing a quantum computer in a data center that can only be reached via the cloud. In that setting, customers might want a way to check that they are really using a quantum device and aren’t being scammed. Alternatively, the authors say the protocol could be useful to scientists who want to verify that they’ve really built a quantum simulator in their lab. In that case, the device would be under the control of a researcher doing double duty as both verifier and prover, and they could ultimately prove to themselves and their colleagues that they’ve got a working quantum computer.
In either case, the protocol goes something like this. First, the verifier describes a specific instance of the problem and an initial state. Then, they ask the prover to use that description to prepare a fixed number of final states. The correct final state is unknown to the verifier, but it is closely related to the original problem of finding the lowest energy state of a simple quantum system. The verifier also chooses how certain they want to be about whether the prover has a truly quantum device, and they can guarantee a desired level of certainty by adjusting the number of final states that they ask the prover to prepare.
For each requested state, the verifier flips a coin. If it comes up heads, the verifier’s goal is to collect a valid solution to the problem, and they ask the prover to measure all the qubits and report the results. Based on the measurement of the special clock qubit, the verifier either throws the results away or stores them for later. Measuring the clock qubit essentially lets the verifier weed out invalid results. The results that get stored are potentially valid solutions, which the verifier will publish at the end of the protocol if the prover passes the rest of the verification.
If the coin comes up tails, the verifier’s goal is to test that the prover is running the simulation correctly. To do this, the verifier flips a second coin. If that coin comes up heads, the verifier asks the prover to make measurements that check whether the input state is correct. If the coin comes up tails, the verifier asks the prover to make measurements that reveal whether the prover performed the correct continuous evolution.
The verifier then uses all the results stemming from that second coin flip to compute two numbers. In the paper, the team calculated thresholds for each number that separate fraudulent provers from those with real quantum-powered devices. If the two numbers clear those thresholds, the verifier can publish the stored answers, confident in the fact that the prover is telling the truth about their quantum machine.
There is a caveat to the protocol that limits its future use by a suspicious customer of a quantum computing cloud provider. The protocol assumes that the prover is honest about which measurements they make—it assumes that they aren’t trying to pull one over on the verifier and that they make the measurements that the verifier requests. The authors describe a second version of the protocol that parallels the first and relaxes this element of trust. In that version, the prover doesn't measure the final states but instead transmits them directly to the verifier as quantum states—a potentially challenging technical feat. With the states under their control, the verifier can flip the coins and make the measurements all on their own. This is why the protocol can still be useful for researchers trying to put their own device through its paces and demonstrate near-term quantum speedups in their labs.
Ultimately the team would love to relax the requirement that the prover is trusted to make the right measurements. But progress toward this more desirable feature has been tough to find, especially in the realm of quantum simulation.
“That's a really hard problem,” Liu says. “This is very, very nontrivial work, and, as far as I know, all work that has this feature relies on some serious cryptography. This is clearly not easy to do in quantum simulations.”
Original story by Chris Cesare: https://jqi.umd.edu/news/new-protocol-demonstrates-and-verifies-quantum-speedups-jiffy
In addition to Gorshkov, Zhenning Liu, and Childs the paper had several other authors: Dhruv Devulapalli, a graduate student in physics at UMD; Dominik Hangleiter, a former QuICS Hartree Postdoctoral Fellow who is now a Quantum Postdoctoral Fellow at the Simons Institute for the Theory of Computing at the University of California, Berkeley; Yi-Kai Liu, who is a QuICS Fellow and a senior investigator at RQS; and JQI Fellow Alicia Kollár, who is also a senior investigator at RQS.
