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:
... continue reading