A team of scientists from Skoltech‘s Deep Quantum Laboratory discovered and quantified what appears to be a fundamental limitation in the QAOA quantum algorithm initiated by Google.
Google has devised new quantum-enhanced algorithms that operate in the presence of realistic noise. The so-called quantum approximate optimisation algorithm, or QAOA for short, is the cornerstone of a modern drive toward noise-tolerant quantum-enhanced algorithm development. Yet, little is known about the ultimate performance limitations of Google’s QAOA algorithm.
The researchers have discovered so-called reachability deficits which place a fundamental limitation on the ability of QAOA to even approximate a solution to a problem. QAOA and other variational quantum algorithms have proven extremely difficult to analyse 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 utilize these quantum operations iteratively by forming a sequence of increasingly optimal approximations to minimize an objective function. (Phys.org)
The paper has been published in Physical Review Letters.