(SciTechDaily) A team of Russian scientists from Skoltech’s Deep Quantum Laboratory led by Prof. Jacob Biamonte discovered and quantified what appears to be a fundamental limitation in the wildly adopted approach initiated by Google.
The authors detail the discovery of so-called reachability deficits that 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.