A team of researchers at Microsoft discovered a breakthrough in two common problems that have been open for over twenty years. Specifically, the team revisited the question of the largest possible quantum speedups for some important classes of problems.
Grover’s algorithm and Shor’s algorithm are two famous quantum algorithms that yield a polynomial speedup and an exponential speedup, respectively, over their classical counterparts.
Specifically, the team investigated the implications of a 2019 breakthrough by Hao Huang, which resolved a major open problem in the analysis of Boolean functions, called sensitivity conjecture. They found that his result proves a stronger claim with several implications for quantum query complexity. First, they showed that the best possible quantum speedup for unstructured problems is quartic. This resolves a question that’s been open for over 20 years. Second, they found that the proof technique can also be used to resolve an old conjecture about quantum speedups for graph problems.
These results are described in their paper “Quantum Implications of Huang’s Sensitivity Theorem,” which can be found here. (Microsoft)