Artist’s rendition of the Google processor. Credit: Forest Stearns, Google AI Quantum Artist in Residence

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. The results are published in the field’s leading journal Quantum.

From the early days of numerical computing, quantum systems have appeared exceedingly difficult to emulate, though the precise reasons for this remain a subject of active research. Still, this apparently inherent difficulty of a classical computer to emulate a quantum system prompted several researchers to flip the narrative.

Scientists such as Richard Feynman and Yuri Manin speculated in the early 1980s that the unknown ingredients which seem to make quantum computers hard to emulate using a classical computer could themselves be used as a computational resource. For example, a quantum processor should be good at simulating quantum systems, since they are governed by the same underlying principles.

Such early ideas eventually led to Google and other tech giants creating prototype versions of the long-anticipated quantum processors. These modern devices are error-prone, they can only execute the simplest of quantum programs and each calculation must be repeated multiple times to average out the errors in order to eventually form an approximation.

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.

In a nutshell, QAOA is an approach wherein one aims to approximately solve optimization problems on a hybrid setup consisting of a classical computer and a quantum co-processor. Prototypical quantum processors such as Google’s Sycamore are currently restricticted to performing noisy and limited operations. Using a hybrid setup, the hope is to alleviate some of these systematic limitations and still recover quantum behavior to take advantage of, making approaches such as QAOA particularly attractive.

Skoltech scientists have made a series of recent discoveries related to QAOA, for example see the write-up here. 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.

Skoltech’s quantum algorithms lab then approached the CDISE supercomputing team led by Oleg Panarin for the significant computing resources required to emulate Google’s quantum chip. Quantum laboratory member, Senior Research Scientist Dr. Igor Zacharov worked with several others to transform the existing emulation software into a form that permits parallel computation on Zhores. After several months, the team managed to create an emulation that outputs data with the same statistical distributions as Google and showed a range of instance densities at which QAOA performance sharply degrades. They further revealed Google’s data to lie at the edge of this range beyond which the current state of the art would not suffice to produce any advantage.

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.

Oleg Panarin, a manager of data and information services at Skoltech, commented: “We are very pleased to see our computer pushed to this extreme. The project was long and challenging and we’ve worked hand in glove with the quantum lab to develop this framework. We believe this project sets a baseline for future demonstrations of this type using Zhores.”

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

Akshay Vishwanatahan, a PhD student at Skoltech, concluded: “Going past a few qubits and layers in QAOA was a significantly challenging task at the time. The in-house emulation software we developed could only address toy-model cases and I initially felt that this project, while an exciting challenge, would prove nearly impossible. Fortunately, I was amidst a group of optimistic and high-spirited peers and this further motivated me to follow through and reproduce Google’s noiseless data. It was certainly a moment of great excitement when our data matched Google’s, with a similar statistical distribution, from which we were finally able to see the effect’s presence.”

Reference: “Reachability Deficits in Quantum Approximate Optimization of Graph Problems” by V. Akshay, H. Philathong, I. Zacharov and J. Biamonte, 30 August 2021, Quantum.DOI: 10.22331/q-2021-08-30-532