Quantum computers just beat classical ones — Exponentially and unconditionally
Quantum computers have the potential to speed up computation, help design new medicines, break codes, and discover exotic new materials — but that’s only when they are truly functional.
One key thing that gets in the way: noise or the errors that are produced during computations on a quantum machine — which in fact makes them less powerful than classical computers – until recently.
Daniel Lidar, holder of the Viterbi Professorship in Engineering and Professor of Electrical & Computing Engineering at the USC Viterbi School of Engineering, has been iterating on quantum error correction, and in a new study along with collaborators at USC and Johns Hopkins, has been able to demonstrate a quantum exponential scaling advantage, using two 127-qubit IBM Quantum Eagle processor-powered quantum computers, over the cloud. The paper, “Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem,” was published in APS flagship 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.”
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 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.”
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.
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.
Next steps:
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.
Disclosure: USC is an IBM Quantum Innovation Center. Quantum Elements, Inc. Is a startup in the IBM Quantum Network. More
