Recently, a team of researchers at Microsoft led by Robin Kothari 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. Kothari and his collaborators investigated the implications of a 2019 breakthrough by Hao Huang, which resolved the infamous sensitivity conjecture, and proved that the best possible quantum speedup for unstructured problems is quartic (T versus T^4). This answers a question that's been open for over 20 years.

Further, the team found that the same proof technique can also be used to resolve an age-old conjecture about quantum speedups for graph problems that involve analyzing massive sets of unstructured data and finding underlying connections and patterns in it.