Microsoft Quantum researchers pin down largest quantum speedup for unstructured problems
The promise of quantum computing is that it could help us solve some of the most complex challenges facing our world. It’s commonly told that addressing global issues, like climate change, would take our classical computers of today billions of years to solve, whereas a quantum computer could find solutions in mere weeks, days, or hours.
This speedup over classical computing comes when researchers develop algorithms that can harness the unique principles of quantum mechanics—superposition and entanglement—to process highly complex calculations more quickly on scaled-up quantum hardware.
To prepare for this scaled-up quantum future, researchers have been discovering which problems will be well suited for quantum computing and how big of a speedup we can expect over classical counterparts—whether polynomial or exponential.
Shor’s algorithm, for example, is a famous quantum algorithm that we know will yield exponential speedups on a scaled quantum computer. This understanding from research has already had a significant impact on the security industry, reshaping the way we encrypt and protect our data for years to come.
But for other types of common problems, the maximum impact quantum can have has remained an open question for decades—until now.
Robin Kothari, a Senior Researcher on the Microsoft Quantum Systems team, and fellow collaborators Scott Aaronson, Shalev Ben-David, and Avishay Tal, have discovered a breakthrough in two common problems that have been open for over twenty years, resolving conjecture about the speedup that is obtainable by quantum algorithms over classical algorithms.
The problems the team explored appear in almost every type of industry—analyzing massive sets of unstructured data and understanding the connections and patterns within a large graph or network. The researchers showed that the best possible speedup is quartic, meaning to the fourth power, for unstructured problems in quantum query complexity. Previously, in 1998 it was only proven that, at most, a sixth power speedup was the best possible. The proof technique they used also resolves a question having to do with quantum speedup for graph problems.
By definitively answering the question of the largest possible quantum speedup for these problems, the team has enabled fellow researchers and organizations across the industry to better understand both the opportunities and limits of these algorithms and to continue focusing on problems that hold promise for future quantum impact.
You can learn more about the research in a Microsoft Research Blog post by Robin Kothari and read Quantum Implications of Huang’s Sensitivity Theorem published on arXiv.
