Researchers run complex quantum computing algorithms on traditional computers

EPFL Professor Giuseppe Carleo and a graduate student from Columbia University named Matija Medvidović have found a way to execute a complex quantum computing algorithm on a traditional computer. Typically executing quantum software requires the use of a quantum computer. The quantum software the researchers are considering is known as Quantum Approximate Optimization Algorithm (QAOA), and it's used to solve classical optimization problems in mathematics.

According to the researchers, the software is basically a way of picking the best solution to a problem out of a set of possible solutions. Carleo says there is significant interest in understanding what problems can be solved efficiently by quantum computers, and QAOA is one of the most promising candidates. QAOA is meant to help on the path to the so-called "quantum speedup," which is a predicted boost in processing speed achievable using quantum computers.

QAOA is a subject of research and has significant support in the technology community. For example, in 2019, Google created Sycamore, a 53-qubit quantum processor, and used it to run a task. That task is estimated to take a state-of-the-art classic supercomputer around 10,000 years to complete, but Sycamore completed the task in 200 seconds.

Researchers on the new study wanted to address an open question in the field: Can algorithms running on current and near-term quantum computers offer a significant gain in performance over classical algorithms for tasks of practical interest. Using a conventional computer, the researchers developed a method that can approximately simulate the behavior of a special class of algorithms known as variational quantum algorithms.

Those algorithms are ways of working out the lowest energy state, or "ground state" of the quantum system. The team says that QAOA is an important example of this type of quantum algorithm. Researchers believe algorithms of the sort are among the most promising candidates to gain quantum advantage in near-term quantum computers. The work showed that QAOA could run on current computers, and near-term quantum computers can be simulated with good accuracy on a classical computer.