Russian Scientists Break Google’s Quantum Algorithm

Quantum Algorithm Concept Design

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.

Fixed Depth QAOA Circuits Performance

The graph represents the performance (difference between QAOA optima and exact optima) of fixed depth QAOA circuits on randomly generated MAX-SAT instances with increasing problem densities. Although higher depth versions achieve better performances, they still exhibit reachability deficits. Credit: Physical Review Letters

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.

The Skoltech team’s findings report a clear limitation of the variational QAOA quantum algorithm. QAOA and other variational quantum algorithms have proven extremely difficult to analyze using known mathematical techniques due to an internal quantum-to-classical feedback process. Namely, a given quantum computation can only run for a fixed amount of time. Inside this fixed time, a fixed number of quantum operations can be executed. QAOA seeks to iteratively utilize these quantum operations by forming a sequence of increasingly optimal approximations to minimize an objective function. The study places new limits on this process.

The authors discovered that QAOA’s ability to approximate optimal solutions for any fixed-depth quantum circuit is fundamentally dependent on the problem’s “density.” In the case of the problem called MAX-SAT, the so-called density can be defined as the ratio of the problem’s constraints to variable count. This is sometimes called clause density.

The authors discovered problem instances of high density whose optimal solutions cannot be approximated with guaranteed success, regardless of the algorithms’ run-time.

Reference: “Reachability Deficits in Quantum Approximate Optimization” by V. Akshay, H. Philathong, M. E. S. Morales and J. D. Biamonte, 5 March 2020, Physics Review Letters.
DOI: 10.1103/PhysRevLett.124.090504

Be the first to comment on "Russian Scientists Break Google’s Quantum Algorithm"

Leave a comment

Email address is optional. If provided, your email will not be published or shared.