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.
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.
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.
