Skoltech scientists use supercomputer to test
The CPQM’s Quantum Information Processing Laboratory has collaborated with the intensive computing team of CDISE “Zhores” to emulate Google’s quantum processor. By reproducing silent data following the same statistics as recent Google experiments, the team was able to point to a subtle effect lurking in Google’s data. This effect, called accessibility deficit, was discovered by the Skoltech team in its past work. The numbers confirmed that Google’s data was on the verge of a so-called density-dependent avalanche, implying that future experiments will require significantly more quantum resources to perform rough quantum optimization. The results are published in the main journal of the field Quantum.
Since the early days of digital computing, quantum systems have appeared extremely difficult to emulate, although the precise reasons for this remain a subject of active research. Yet this difficulty apparently inherent in a classical computer to emulate a quantum system has prompted several researchers to reverse the narrative.
Scientists such as Richard Feynman and Yuri Manin speculated in the early 1980s that the unknown ingredients that seem to make quantum computers difficult to mimic using a conventional computer could themselves be used as a computing resource. For example, a quantum processor should be good at simulating quantum systems because they are governed by the same underlying principles.
These early ideas eventually led Google and other tech giants to create prototype versions of the long-awaited quantum processors. These modern devices are error prone, can only run the simplest of quantum programs, and each calculation must be repeated several times to average the errors to eventually form an approximation.
Among the most studied applications of these contemporary quantum processors is the approximate quantum optimization algorithm, or QAOA (pronounced “kyoo-ay-oh-AY”). In a series of spectacular experiments, Google used its processor to probe QAOA’s performance using 23 qubits and three adjustable program steps.
In short, QAOA is an approach in which we aim to approximately solve optimization problems on a hybrid configuration composed of a classical computer and a quantum coprocessor. Prototype quantum processors like Google’s Sycamore are currently limited to performing noisy and limited operations. By using a hybrid configuration, the hope is to alleviate some of these systematic limitations while recovering the quantum behavior to exploit, which makes approaches such as QAOA particularly attractive.
Skoltech scientists have made a series of recent discoveries related to QAOA, for example see article here. The main one being an effect which fundamentally limits the applicability of the QAOA. They show that the density of an optimization problem, that is to say the ratio between its constraints and its variables, acts as a major obstacle to obtaining approximate solutions. Additional resources, in terms of operations performed on the quantum coprocessor, are required to overcome this performance limitation. These discoveries were made using pen and paper and very small emulations. They wanted to see if the effect they had 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. Dr. Igor Zacharov, a member of the Quantum Laboratory, Principal Scientist worked with several others to transform the existing emulation software into a form that allows parallel calculations on Zhores. After several months, the team managed to create an emulation that generates data with the same statistical distributions as Google and showed a range of instance densities at which QAOA performance degrades sharply. They further revealed that Google’s data was at the limit of this range beyond which the current state of the art would not be sufficient to produce an advantage.
The Skoltech team originally found that accessibility deficits – a performance limitation induced by a problem’s constraint-to-variable ratio – were present for a type of problem called maximum constraint satisfiability. Google, however, considered minimizing the energy functions of graphs. Since these issues belong to the same class of complexity, this gave the team conceptual hope that the issues, and later the effect, could be related. This intuition turned out to be correct. The data was generated and the results clearly showed that accessibility deficits create a sort of avalanche effect, placing Google’s data on the brink of that rapid transition beyond which longer and longer QAOA circuits. powerful become a necessity.
Oleg Panarine, a data and information services manager at Skoltech, commented: “We are very happy to see our computer taken to this extreme. The project was long and difficult and we worked hand in hand with the quantum lab to develop this framework. We believe that this project establishes a baseline for future demonstrations of this type using Zhores. “
Igor Zacharov, Senior Researcher at Skoltech, added, “We took the 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 time for all of us when the data finally appeared, and we had the same stats as Google. In this project, we created a software package that can now emulate various advanced quantum processors, with up to 36 qubits and a dozen layers deep.
Akshay Vishwanatahan, PhD student at Skoltech, concluded: “Getting past a few qubits and layers in QAOA was a very difficult task at the time. The internal emulation software we developed could only handle toy model cases and at first I thought that this project, although an exciting challenge, would prove to be nearly impossible. Luckily, I was in the midst of an upbeat and spirited peer group and it still motivated me to follow and replicate Google’s silent data. It was certainly a moment of great excitement when our data matched that of Google, with a similar statistical distribution, from which we were finally able to see the presence of the effect.
Computer simulation / modeling
The title of the article
Accessibility deficits in approximate quantum optimization of graph problems
Publication date of the article
Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of any press releases posted on EurekAlert! by contributing institutions or for the use of any information via the EurekAlert system.