Microsoft Researchers Solve Two 20-Year Old Problems in Quantum Computing
(NEOWin.net) 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, i.e., 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.
Having answered the age-old problem about the maximum speedup offered by quantum computers for unstructured problems, Kothari’s team believes that moving forward, an open research question pertains to finding unstructured problems that exhibit a larger quantum speedup than that offered by Grover’s algorithm.