Massive Unstructured Data Sets and Underlying Patterns Focus of Microsoft Quantum Systems Team
Microsoft Quantum researchers pin down largest quantum speedup for unstructured problems
Key points to note…
+ 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.
Content may have been edited for style and clarity.
