(SciTechDaily) CPQM’s Laboratory for Quantum Information Processing has collaborated with the CDISE supercomputing team “Zhores” to emulate Google’s quantum processor. Reproducing noiseless data following the same statistics as Google’s recent experiments, the team was able to point to a subtle effect lurking in Google’s data. This effect, called a reachability deficit, was discovered by the Skoltech team in its past work. The numerics confirmed that Google’s data was on the edge of a so-called, density-dependent avalanche, which implies that future experiments will require significantly more quantum resources to perform quantum approximate optimization.
Among the most studied applications of these contemporary quantum processors is the quantum approximate optimization algorithm, or QAOA (pronounced “kyoo-ay-oh-AY”). In a series of dramatic experiments, Google used its processor to probe QAOA’s performance using 23 qubits and three tunable program steps.
Skoltech scientists have made a series of recent discoveries related to QAOA. Prominent among them being an effect that fundamentally limits the applicability of QAOA. They show that the density of an optimization problem — that is, the ratio between its constraints and variables — acts as a major barrier to achieving approximate solutions. Additional resources, in terms of operations run on the quantum co-processor, are required to overcome this performance limitation. These discoveries were done using pen and paper and very small emulations. They wanted to see if the effect they recently discovered manifested itself in Google’s recent experimental study.
The Skoltech team originally found that reachability deficits — a performance limitation induced by a problem’s constraint-to-variable ratio — were present for a kind of problem called maximum constraint satisfiability. Google, however, considered the minimization of graph energy functions. Since these problems are in the same complexity class, it gave the team conceptual hope that the problems, and later the effect, could be related. This intuition turned out to be correct. The data was generated and the findings clearly showed that reachability deficits create a type of an avalanche effect, placing Google’s data on the edge of this rapid transition beyond which longer, more powerful QAOA circuits become a necessity.
Igor Zacharov, a senior research scientist at Skoltech, added: “We took existing code from Akshay Vishwanatahan, the first author of this study, and turned it into a program that ran in parallel. It was certainly an exciting moment for all of us when the data finally appeared, and we had the same statistics as Google. In this project, we created a software package that can now emulate various state-of-the-art quantum processors, with as many as 36 qubits and a dozen layers deep.”