Quantum computers leverage the principles of quantum entanglement and superposition to achieve a significant computational speedup compared to classical computers. Shor’s algorithm is a common example of this and it can yield exponential speedups on a scaled quantum computer, and researchers are well aware of this. Grover"s algorithm is another example that is often quoted as it boasts a polynomial speedup compared to its classical counterpart.
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.
In 1999, Buhrman et al. showed that any quantum algorithm must make Ω(√n) queries to decide a monotone graph property. The conjectured answer was a linear time complexity with the worst-case bound being Ω(n) that could be achieved using Grover’s algorithm. Kothari"s team proved this conjecture optimally, which is unique considering that the classical counterpart of this conjecture remains unproven.
This is a surprising state of affairs as we are able to completely resolve the quantum analog of the conjecture while the classical version remains unsolved.
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. More information can be found here.