Russian Scientists Break Google’s Quantum Algorithm
Scientists from Skolkovo Institute of Science and Technology (Skoltech), a private graduate research institute in Moscow, Russia, discovered and quantified what appears to be a fundamental limitation in the wildly adopted quantum approach initiated by Google.
Google is racing to develop quantum-enhanced processors that utilize quantum mechanical effects to one day dramatically increase the speed at which data can be processed.
In the near term, Google has devised new quantum-enhanced algorithms that operate in the presence of realistic noise. The so-called quantum approximate optimization algorithm, or QAOA for short, is the cornerstone of a modern drive towards noise-tolerant quantum-enhanced algorithm development.
The celebrated approach taken by Google in QAOA has sparked vast commercial interest and ignited a global research community to explore novel applications. Yet, little actually remains known about the ultimate performance limitations of Google’s QAOA algorithm.
A team of scientists, hailing from Skoltech’s Deep Quantum Laboratory, took up this contemporary challenge. The all-Skoltech team led by Prof. Jacob Biamonte discovered and quantified what appears to be a fundamental limitation in the wildly adopted approach initiated by Google.
Reporting in Physical Review Letters, the authors detail the discovery of so-called reachability deficits — the authors show how these deficits place a fundamental limitation on the ability of QAOA to even approximate a solution to a problem instance.