Skoltech Scientists Break Google’s Quantum Algorithm

(Phys.org) A team of scientists from Skoltech’s Deep Quantum Laboratory took up the contemporary challenge of exploring Google’s quantum approximate optimisation algorithm (QAOA). The all-Skoltech team led by Prof. Jacob Biamonte discovered and quantified what appears to be a fundamental limitation in the widely adopted approach initiated by Google.
Reporting in Physical Review Letters, the authors detail the discovery of so-called reachability deficits—the authors show that these deficits place a fundamental limitation on the ability of QAOA to even approximate a solution to a problem.
The authors discovered that QAOA’s ability to approximate optimal solutions for any fixed depth quantum circuit is fundamentally dependent on the problems “density.” In the case of the problem called MAX-SAT, the so-called density can be defined as the ratio of the problems constraints to variable count. This is sometimes called clause density.
The authors discovered problematic instances of high density with optimal solutions that cannot be approximated with guaranteed success, regardless of the algorithm’s run time.