Quantum computers have long promised to revolutionize fields such as medicine, cryptography, and material science. However, their potential has been largely theoretical due to persistent challenges like computational noise. This barrier has historically made quantum machines less effective than classical computers. But a groundbreaking study led by Daniel Lidar at the USC Viterbi School of Engineering has demonstrated a significant breakthrough: an exponential scaling advantage using quantum computers.
In collaboration with researchers from USC and Johns Hopkins, Lidar’s team utilized two 127-qubit IBM Quantum Eagle processors to achieve this milestone. Their findings, published in the prestigious journal Physical Review X, mark the first unconditional exponential speedup over classical counterparts. Lidar, a prominent figure in the field, noted, “There have previously been demonstrations of more modest types of speedups like a polynomial speedup. But an exponential speedup is the most dramatic type of speedup that we expect to see from quantum computers.”
Understanding Quantum Speedup
The quest for quantum computing has always been about executing algorithms with a scaling speedup relative to classical computers. Lidar explains that a scaling speedup doesn’t simply mean performing tasks faster, but rather that as problem size increases, the performance gap between quantum and classical computers widens exponentially. “Moreover, the speedup we demonstrated is unconditional,” Lidar emphasized, meaning it doesn’t depend on unproven assumptions.
The team modified an algorithm to solve a variation of “Simon’s problem,” a foundational quantum algorithm that can theoretically solve tasks exponentially faster than classical methods. Simon’s problem involves identifying a hidden repeating pattern in a mathematical function, akin to a guessing game where players aim to uncover a secret number known only to the game host.
Achieving the Breakthrough
Phattharaporn Singkanipa, a USC doctoral researcher and first author of the study, detailed the strategies that led to their success. “The key was squeezing every ounce of performance from the hardware: shorter circuits, smarter pulse sequences, and statistical error mitigation,” she said. The researchers employed four main techniques:
- Data Input Limitation: By restricting the number of secret numbers, they reduced the need for quantum logic operations, minimizing error potential.
- Transpilation: This method compressed the number of required quantum logic operations.
- Dynamical Decoupling: This involved applying sequences of carefully designed pulses to isolate qubits from their noisy environment, significantly enhancing performance.
- Measurement Error Mitigation: This technique corrected residual errors after dynamical decoupling.
Lidar, who also holds positions at the USC Dornsife College of Letters, Arts and Science, remarked, “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.”
Implications and Future Directions
The implications of this research are profound. For the first time, the performance separation between quantum and classical computing is not only evident but also irreversible. “The exponential speedup we’ve demonstrated is, for the first time, unconditional,” Lidar stated, underscoring the growing difficulty in disputing quantum computing’s advantages.
However, Lidar cautions that practical applications remain on the horizon. “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,” he noted. Future efforts will focus on demonstrating speedups without relying on pre-known answers and further reducing noise and decoherence in larger quantum systems.
Despite these challenges, the study represents a significant step forward. The previously theoretical promise of quantum computers to deliver exponential speedups is now a demonstrable reality. As the field progresses, the potential for quantum computing to transform industries grows ever closer.
Disclosure: USC is an IBM Quantum Innovation Center. Quantum Elements, Inc. is a startup in the IBM Quantum Network.
