Quantum computing has the potential to transform the world in which we live. Complex problems, such as major global issues. However, under current conditions, normal computers would take billions of years to reach a solution. Quantum computing promises to revolutionize calculation and complete equal tasks in days or even hours. However, so-called quantum speedup is possible when research teams use algorithms to leverage quantum mechanics… specifically entanglement and superposition. These two principles can help scale-up calculations. To achieve the scale-up, it is necessary to understand which problems are best suited to quantum calculations. More importantly, what kind of speedup can be achieved. In a blog post, Microsoft Quantum explains one example of an algorithm to yield speedups. “Shor’s algorithm, for example, is a famous quantum algorithm that we know will yield exponential speedups on a scaled quantum computer. This understanding from research has already had a significant impact on the security industry, reshaping the way we encrypt and protect our data for years to come.”
Breakthrough
However, some other common problems and how they relate to quantum computing have been unanswered. Microsoft Quantum’s research has helped to solve two of these long-standing problems. In the blog post, Robin Kothari, a Senior Researcher on the Microsoft Quantum Systems team, said they have made a breakthrough in two areas. “We found that his result proves a stronger claim with several implications for quantum query complexity. First, we showed that the best possible quantum speedup for unstructured problems is quartic (T versus T4 , described further below). “This resolves a question that’s been open for over 20 years. Second, we found that the proof technique can also be used to resolve an old conjecture about quantum speedups for graph problems.”
