Posted in | News | Quantum Computing

New Method to Simulate Quantum Optimization Algorithm Using Classical Computer

Two Physicists from École polytechnique fédérale de Lausanne (EPFL) and Columbia University have presented a new method for simulating the quantum approximate optimization algorithm with the assistance of a conventional computer.

Visual of stimulating quantum approximate optimization

Image Credit: École polytechnique fédérale de Lausanne.

Rather than running the algorithm in an advanced quantum processor, the new method employs a classical machine-learning algorithm that nearly reflects the behavior of near-term quantum computers. The study was published in the journal npj Quantum Information.

EPFL Professor Giuseppe Carleo and MatijaMedvidović, a graduate student at Columbia University and the Flatiron Institute in New York, discovered a method to process a complicated quantum computing algorithm on conventional computers rather than using the quantum ones.

The particular “quantum software” that the researchers consider is Quantum Approximate Optimization Algorithm (QAOA) and is employed to resolve the traditional optimization problems in mathematics. It is necessarily a way of choosing the best solution to an issue from an array of possible solutions.

There is a lot of interest in understanding what problems can be solved efficiently by a quantum computer, and QAOA is one of the more prominent candidates.

Giuseppe Carleo, Professor, Institute of Physics, École polytechnique fédérale de Lausanne.

Eventually, the objective of QAOA is to assist the popular “quantum speedup,” the anticipated boost in processing speed that can be reached with the help of quantum computers rather than traditional ones.

The QAOA has several supporters, including Google, which has its site build on quantum technologies and computing in the years to come. In 2019, a 53-qubit quantum processor known as Sycamore was developed by the researchers and employed to execute a task that would probably take 10,000 years to complete on an advanced classical supercomputer. The Sycamore ran the task in just 200 seconds.

But the barrier of quantum speedup is all but rigid and it is being continuously reshaped by new research, also thanks to the progress in the development of more efficient classical algorithms.

Giuseppe Carleo, Professor, Institute of Physics, École polytechnique fédérale de Lausanne.

Carleo and Medvidović have answered an important open question in their study: whether it is possible to run algorithms on current and near-term quantum computers that provide a notable benefit over the traditional algorithms for tasks of practical interest.

Carlo answered, “If we are to answer that question, we first need to understand the limits of classical computing in simulating quantum systems.

This is particularly important as the present generation of quantum processors function in a period where they make errors when running quantum “software” and hence can only execute algorithms of limited complication.

The researchers employed traditional computers to design a technique that can almost simulate the behavior of a special class of algorithms called variational quantum algorithms. This method involves identifying the lowest energy state, or “ground state,” of the quantum algorithms. These are predicted to be a potential candidate for “quantum advantage” in near-term quantum computers.

The technique is built on the idea that sophisticated machine-learning tools can also be utilized to understand and reproduce the inner operation of the quantum computer.

An important tool for these simulations is Neural Network Quantum States, which are artificial networks developed by Carleo and Matthias Troyer in 2016. This system is currently utilized for the first time for the simulation of QAOA. The outcomes are considered significant for quantum computing and place a new benchmark for the further development of quantum hardware.

Our work shows that the QAOA you can run on current and near-term quantum computers can be simulated, with good accuracy, on a classical computer too.

Giuseppe Carleo, Professor, Institute of Physics, École polytechnique fédérale de Lausanne.

However, this does not mean that all useful quantum algorithms that can be run on near-term quantum processors can be emulated classically. In fact, we hope that our approach will serve as a guide to devise new quantum algorithms that are both useful and hard to simulate for classical computers,” concluded Carleo.

Journal Reference:

Medvidović, M & Carleo, G (2021) Classical variational simulation of the Quantum Approximate Optimization Algorithm. npj Quantum Information.


Tell Us What You Think

Do you have a review, update or anything you would like to add to this news story?

Leave your feedback
Your comment type