Russia

Russian Scientists Reveal ‘Limitations’ of Google’s Quantum Algorithm in Challenging New Study

On its ambitious road to develop quantum-enhanced processors, hoping to ultimately increase the speed at which data can be processed, Google has devised new quantum-enhanced algorithms – QAOA - the ultimate performance limitations of which have presented a challenge to the global research community.
Sputnik

A team of scientists from the Skolkovo Institute of Science and Technology have announced they have discovered and quantified what appears to be a fundamental limitation in the widely touted approach initiated by Google – the so-called quantum approximate optimization algorithm, or QAOA - the cornerstone of efforts to develop a noise-tolerant quantum-enhanced algorithm.

The study by Skoltech’s Deep Quantum Laboratory  led by Prof. Jacob Biamonte, and published in Physical Review Letters, details the discovery of so-called “reachability deficits”.

In their paper, “Reachability Deficits in Quantum Approximate Optimization”, the authors have elaborated the mechanism of how a fundamental limitation is placed by these “deficits” on the ability of QAOA to even approximate a solution to a problem instance.

Google’s Quantum Ambitions

Google earlier devised new quantum-enhanced algorithms that “operate in the presence of realistic noise”, as part of its race to develop quantum-enhanced processors based on quantum mechanical effects.

This would be conducive towards reaching the ultimate goal - increasing the speed at which data can be processed.

The quantum approximate optimization algorithm, or QAOA, fired the interest of the global research community to explore its growing range of applications, while only a few results have been developed towards understanding the algorithm’s ultimate limitations.

The Skoltech team rose to the challenge, with its newly-reported findings revealing a clear limitation of the variational QAOA quantum algorithm.

Russian Scientists Reveal ‘Limitations’ of Google’s Quantum Algorithm in Challenging New Study

Known mathematical techniques fall short of exhaustively analyzing QAOA and other variational quantum algorithms due to the internal quantum-to-classical feedback process.

Thus, a given quantum computation can only run for a fixed amount of time inside which a fixed number of quantum operations can be carried out.

Russian Scientists Reveal ‘Limitations’ of Google’s Quantum Algorithm in Challenging New Study

QAOA seeks to “utilize these quantum operations by forming a sequence of increasingly optimal approximations to minimize an objective function”.
The recent research study now places new limits on this process.

Thus, the authors discovered that QAOA’s ability to approximate optimal solutions for any fixed depth quantum circuit is fundamentally dependent on the problems “density.”

The team reports that QAOA exhibits a “strong dependence on a problem instances constraint to variable ratio”.

This problem density places a limiting restriction on the algorithms capacity to solve optimization problem instances.

These findings, write the authors in their report, are among the first to determine strong limitations on variational quantum approximate optimization.

Discuss