Last Updated on June 13, 2025 by Sushanta Barman
In a groundbreaking demonstration, researchers have achieved an exponential quantum speedup on IBM quantum computers for a notoriously challenging computational problem known as Simon’s problem. This accomplishment, published in the prestigious journal Physical Review X, marks a significant step toward practical quantum computing, bringing the scientific community closer to efficiently solving complex problems beyond the capabilities of classical computers.
The collaborative effort involved researchers from the University of Southern California and Johns Hopkins University, along with IBM Quantum. Utilizing advanced superconducting quantum processors developed by IBM, the team tackled a variant of Simon’s problem, specifically restricting the complexity of the hidden information encoded in the problem. Simon’s problem involves finding a secret bitstring encoded in an unknown mathematical function, a task that rapidly becomes computationally infeasible for traditional computers as the bitstring lengthens.
“Simon’s problem is to find a hidden period (a bitstring) encoded into an unknown 2-to-1 function. It is one of the earliest problems for which an exponential quantum speedup was proven for ideal, noiseless quantum computers, albeit in the oracle model,” explained the researchers. “However, today’s noisy intermediate-scale quantum (NISQ) devices are functional on a relatively small scale of several hundreds of qubits and are highly susceptible to performance degradation due to decoherence and control errors.”
By employing innovative error-suppression techniques, notably dynamical decoupling and measurement error mitigation, the researchers significantly enhanced the reliability and accuracy of quantum computations. These methods effectively minimized errors that typically hinder quantum calculations, enabling the team to observe a clear exponential advantage over classical algorithms in practice.
The researchers implemented their tests on two different 127-qubit IBM Quantum superconducting processors. They reported exponential speedups in solving the modified Simon’s problem involving circuits up to 58 qubits, surpassing classical computing limits. The researchers noted: “For sufficiently small values of \(w\) (Hamming weight) and for circuits involving up to 58 qubits, we demonstrate an exponential speedup, albeit of a lower quality than the speedup predicted for the noiseless algorithm. The speedup exponent and the range of \(w\) values for which an exponential speedup exists are significantly enhanced when the computation is protected by dynamical decoupling.”
This achievement highlights the critical role of error-correction and suppression techniques in making quantum computers viable for complex, practical tasks. The researchers anticipate that their methods will help move quantum algorithms closer to solving even more consequential problems, like integer factoring—a foundational operation in cryptography and cybersecurity.
Looking ahead, the team aims to extend their techniques to more complicated quantum algorithms, potentially paving the way for solving problems currently beyond the reach of classical computers. As quantum computers get better, these advances could help us finally tap into their true potential of quantum computing, ultimately benefiting fields ranging from cryptography to materials science and pharmaceuticals.
Read the full article: P. Singkanipa et al., “Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem,” Phys. Rev. X 15, 021082 (2025).
I am a senior research scholar in the Department of Physics at IIT Kanpur. My work focuses on ion-beam optics and matter-wave phenomena. I am also interested in emerging matter-wave technologies.
