The promise of quantum computing is that it could help us solve a number of the foremost complex challenges facing our world. It’s commonly told that addressing global issues like global climate change would take our classical computers of today billions of years to unravel , whereas a quantum computer could find solutions in just weeks, days, or hours.
This speedup over classical computing comes when researchers develop algorithms which will harness the unique principles of quantum physics – superposition and entanglement – to process highly complex calculations more quickly on scaled-up quantum hardware.
To prepare for this scaled-up quantum future, researchers are discovering which problems are going to be compatible with quantum computing and the way big of a speedup we will expect over classical counterparts – whether polynomial or exponential.
Shor’s algorithm, for instance, maybe a famous quantum algorithm that we all know will yield exponential speedups on a scaled quantum computer. This understanding from research has already had a big impact on the safety industry, reshaping the way we encrypt and protect our data for years to return.
But for other sorts of common problems, the utmost impact quantum can have has remained an open question for many years – so far.
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 are open for over twenty years, resolving conjecture about the speedup that’s obtainable by quantum algorithms over classical algorithms.
The problems the team explored appear in almost every sort of industry – analyzing massive sets of unstructured data and understanding the connections and patterns within an outsized graph or network. The researchers showed that the simplest possible speedup is quartic, aiming to the biquadrate, for unstructured problems in quantum query complexity. Previously, in 1998 it had been only proven that, at most, a sixth power speedup was the simplest possible. The proof technique they used also resolves an issue having to try to to with quantum speedup for graph problems.
By definitively answering the question of the most important possible quantum speedup for these problems, the team has enabled fellow researchers and organizations across the industry to raised understand both the opportunities and limits of those algorithms and to continue that specialize in problems that hold promise for future quantum impact.