A new problem that only quantum computing can solve

As quantum computing develops, scientists are working to identify tasks for which quantum computers have a clear advantage over classical computers. So far, researchers have only pinpointed a handful of these problems, but in a new paper published in Physical Review Letters, scientists at Los Alamos National Laboratory have added one more problem to this very short list.

“One of the central questions that faces quantum computing is what classes of problems they can most efficiently solve but classical computers cannot,” says Marco Cerezo, the Los Alamos team’s lead scientist. “At the moment, this is the Holy Grail of quantum computing because you can count on two hands such problems. In this paper, we’ve just added another.”

Quantum computing harnesses the unique laws of quantum physics, such as superposition, entanglement and interference, which allow for information processing capabilities beyond those of classical devices. When fully realized, quantum computing promises to make advancements in cryptography, simulations of quantum systems and data analysis, among many other fields. But before this can happen, researchers still need to develop the foundational science of quantum computing.

The particular problem considered by the Los Alamos team involved simulating an extremely complex optical circuit with semi-transparent mirrors (or beam splitters) and phase shifters, acting on an exponentially large number of light sources. The Los Alamos team chose this problem because these Gaussian bosonic circuits constitute a physically motivated system that emulates experimental laboratory setups.

“Just writing down a complete description of this system on a classical computer would require an enormous amount of memory and processing capability,” says Diego García-Martín, a co-author with the Lab’s Information Sciences group who originally proposed the project idea. “Our work also rigorously shows that this simulation problem is not expected to be solvable by a classical computer without running for an intractable amount of time. But with a quantum computer, we were able to simulate this problem efficiently.”

A host of solutions

More than just simulating a complex arrangement of light sources and optical components, Los Alamos scientists wanted to prove that quantum computers have a provable advantage for this class of problems.

“In keeping with computational complexity theory, our goal is to show that the task of simulating large Gaussian bosonic circuits can be mapped to other problems that are known to be hard for classical computers, but easy for quantum ones,” García-Martín says.

As such, the team’s paper shows that the considered simulations belong to a class of classically hard — but quantumly easy — problems known as bounded-error quantum polynomial time complete, or BQP-complete. This means that any other BQP-complete problem can be mapped to a large Gaussian bosonic circuit and vice versa. This result shows that quantum computers can hold a computational advantage for these Gaussian bosonic circuit problems.

A team effort

The work evolved quite naturally for such a meaningful discovery. The idea came about after a previous paper theorized that quantum computers could efficiently simulate an exponentially large network of masses coupled with springs. The Los Alamos team wondered if something similar could be done for a quantum rather than a classical system.

The team was interested in such a project, but they needed someone who specialized in optical circuits. The key to solving this complex problem, it turned out, came with the help of the Quantum Computing Summer School student Alice Barthe, who is working with the European Organization for Nuclear Research (CERN) in Geneva, Switzerland.

The Lab’s school is a highly competitive program that pairs graduate and undergraduate students with Los Alamos mentors to work for 10 weeks on a research project. Along with Barthe’s specialization in quantum algorithms and complexity theory, she also brought invaluable knowledge of optical circuits. 

“The skills Alice brought to our team were fundamental to this paper’s success,” Cerezo says, “and it really goes to show the quality of the students that are accepted into our internship program.”

Paper: “Gate-Based Quantum Simulation of Gaussian Bosonic Circuits on Exponentially Many Modes.” Physical Review Letters.

DOI: 134.070604

Funding: This work was funded by the U.S. Department of Energy through a quantum computing program sponsored by the Los Alamos National Laboratory Information Science and Technology Institute. Additional funding was provided by the Quantum Science Center (QSC), a National Quantum Information Science Research Center of the U.S. Department of Energy, and by Los Alamos National Laboratory through the Center for Non-Linear Studies and the Laboratory Directed Research and Development program.

LA-UR-25-22749