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.

MORE of the story and another associated image / click image TOP of PAGE