Quantum Computers Just Reached the Holy Grail – No Assumptions, No Limits

Researchers from USC and Johns Hopkins used two IBM Eagle quantum processors to pull off an unconditional, exponential speedup on a classic “guess-the-pattern” puzzle, proving—without assumptions—that quantum machines can now outpace the best classical computers.

By squeezing extra performance from hardware with shorter circuits, transpilation, dynamical decoupling, and error-mitigation, the team finally crossed a milestone long called the “holy grail” of quantum computing.

Quantum Exponential Speedup Breakthrough

Quantum computers have long promised to revolutionize technology, with the ability to speed up complex calculations, design new medicines, break modern encryption, and uncover exotic new materials. But there’s been a major obstacle: noise. That’s the term for all the tiny errors that build up during quantum computations, often making these futuristic machines less effective than even today’s classical computers.

Until now.

A breakthrough led by Daniel Lidar, a professor of engineering at USC and an expert in quantum error correction, has pushed quantum computing past a key milestone. Working with researchers from USC and Johns Hopkins, Lidar’s team demonstrated a powerful exponential speedup using two of IBM’s 127-qubit Eagle quantum processors — all operated remotely through the cloud. Their results were published in the prestigious journal Physical Review X.

“There have previously been demonstrations of more modest types of speedups like a polynomial speedup, says Lidar, who is also the cofounder of Quantum Elements, Inc. “But an exponential speedup is the most dramatic type of speed up that we expect to see from quantum computers.”

What ‘Unconditional’ Exponential Advantage Means

The key milestone for quantum computing, Lidar says, has always been to demonstrate that we can execute entire algorithms with a scaling speedup relative to ordinary “classical” computers.

He clarifies that a scaling speedup doesn’t mean that you can do things, say, 100 times faster. “Rather, it’s that as you increase a problem’s size by including more variables, the gap between the quantum and the classical performance keeps growing. And an exponential speedup means that the performance gap roughly doubles for every additional variable. Moreover, the speedup we demonstrated is unconditional.”

What makes a speedup “unconditional,” Lidar explains, is that it doesn’t rely on any unproven assumptions. Prior speedup claims required the assumption that there is no better classical algorithm against which to benchmark the quantum algorithm. Here, the team led by Lidar used an algorithm they modified for the quantum computer to solve a variation of “Simon’s problem,” an early example of quantum algorithms that can, in theory, solve a task exponentially faster than any classical counterpart, unconditionally.

Simon’s Problem: Proving Quantum Supremacy

Simon’s problem involves finding a hidden repeating pattern in a mathematical function and is considered the precursor to what’s known as Shor’s factoring algorithm, which can be used to break codes and launched the entire field of quantum computing. Simon’s problem is like a guessing game, where the players try to guess a secret number known only to the game host (the “oracle”). Once a player guesses two numbers for which the answers returned by the oracle are identical, the secret number is revealed, and that player wins. Quantum players can win this game exponentially faster than classical players.

So, how did the team achieve their exponential speedup? Phattharaporn Singkanipa, USC doctoral researcher and first author, says, “The key was squeezing every ounce of performance from the hardware: shorter circuits, smarter pulse sequences, and statistical error mitigation.”

Four Tricks to Tame Quantum Noise

The researchers achieved this in four different ways:

First, they limited the data input by restricting how many secret numbers would be allowed (technically, by limiting the number of 1’s in the binary representation of the set of secret numbers). This resulted in fewer quantum logic operations than would be needed otherwise, which reduced the opportunity for error buildup.

Second, they compressed the number of required quantum logic operations as much as possible using a method known as transpilation.

Third, and most crucially, the researchers applied a method called “dynamical decoupling,” which means applying sequences of carefully designed pulses to detach the behavior of qubits within the quantum computer from their noisy environment and keep the quantum processing on track. Dynamical decoupling had the most dramatic impact on their ability to demonstrate a quantum speedup.

Finally, they applied “measurement error mitigation,” a method that finds and corrects certain errors that are left over after dynamical decoupling due to imperfections in measuring the qubits’ state at the end of the algorithm.

Evidence Quantum Edge Is Here

Says Lidar, who is also a professor of Chemistry and Physics at the USC Dornsife College of Letters, Arts and Science, “The quantum computing community is showing how quantum processors are beginning to outperform their classical counterparts in targeted tasks, and are stepping into a territory classical computing simply can’t reach., Our result shows that already today’s quantum computers firmly lie on the side of a scaling quantum advantage.”

He adds that with this new research, The performance separation cannot be reversed because the exponential speedup we’ve demonstrated is, for the first time, unconditional.” In other words, the quantum performance advantage is becoming increasingly difficult to dispute.

Looking Ahead: From Milestone to Practical Impact

Lidar cautions that “this result doesn’t have practical applications beyond winning guessing games, and much more work remains to be done before quantum computers can be claimed to have solved a practical real-world problem.”

This will require demonstrating speedups that don’t rely on “oracles” that know the answer in advance and making significant advances in methods for further reducing noise and decoherence in ever larger quantum computers. Nevertheless, quantum computers’ previously “on-paper promise” to provide exponential speedups has now been firmly demonstrated.

Reference: “Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem” by Phattharaporn Singkanipa, Victor Kasatkin, Zeyuan Zhou, Gregory Quiroz and Daniel A. Lidar, 5 June 2025, Physical Review X.
DOI: 10.1103/PhysRevX.15.021082

Disclosure: USC is an IBM Quantum Innovation Center. Quantum Elements, Inc. Is a startup in the IBM Quantum Network.

Never miss a breakthrough: Join the SciTechDaily newsletter.