Analysis Suggests Quantum Simulation as Practical Target for Early Quantum Computers

September 5, 2018

Although quantum computers are still relatively small, they are approaching an important milestone. Many researchers suspect that small versions of these devices, which operate by the rules of quantum physics, may soon surpass today’s fastest supercomputers and achieve quantum computational supremacy—a clear demonstration of a quantum computer solving a problem that is currently intractable for an ordinary computer.

Whatever that intractable task is, though, it may not have many applications beyond the demonstration of quantum supremacy, says Andrew Childs, a professor of computer science and co-director of the Joint Center for Quantum Information and Computer Science (QuICS).

“We wanted to make a distinction between quantum computational supremacy and the problems that physicists might be independently interested in solving,” he says.

In a paper published Sept. 4 in Proceedings of the National Academy of Sciences, Childs and several collaborators suggest that simulating the behavior of interacting quantum magnets might be one of the earliest practical applications of quantum computers. Moreover, the researchers presented a detailed accounting of the quantum resources—the number of basic quantum elements, or qubits, and the number of operations, or gates—required by three previously known methods for performing this kind of quantum simulation.

“We wanted to look ahead a little bit more to an era where we have really well-controlled quantum computers,” says Yuan Su, a graduate student at QuICS and a co-author of the paper. “We think quantum simulation should be one of the easiest practical tasks to achieve with such a device.”

The three methods studied offer different levels of sophistication, but in the end they all provide an algorithm that implements a digital simulation of quantum physics—in this case a simulation of the Heisenberg model, which describes how the magnetic properties of neighboring quantum particles interact. Condensed matter physicists, in particular, might be interested in simulating the Heisenberg model for different interaction strengths—something that ordinary computers struggle to simulate when the number of quantum particles surpasses a few dozen.

The digital nature of these simulation algorithms—which are broken up into discrete gates that act for fixed amounts of time—provides a degree of control that more straightforward simulations lack. For instance, you might learn a lot about the interference of water waves by splashing around in a swimming pool, but what if you wanted to study waves in something other than water? You’d have to build a new pool and fill it with something else.

A digital simulation is more flexible, allowing for complete control over all the parameters in a problem. As Childs puts it: “You can simulate the behavior of an airplane with your computer, even though there’s nothing resembling an airplane inside.” 

To compute qubit and gate counts for each algorithm, the team generated explicit quantum circuits—instructions that tell a quantum computer which sequence of operations to perform on which qubits. The circuits were generated using Quipper, a piece of software partially developed by co-author and former QuICS Hartree Postdoctoral Fellow Neil Julien Ross, now an assistant professor of mathematics at Dalhousie University in Canada.

Additionally, the team improved several mathematical bounds on the algorithms’ gate counts, showing that the worst-case counts weren’t as bad as they previously seemed. In the end, regardless of the algorithm used, the simulation of quantum magnets compared favorably to other well-known uses for quantum computers, such as factoring large numbers and performing chemistry calculations. The circuits for quantum simulation were orders of magnitude smaller than the circuits for these problems, strengthening the case for quantum simulation as a reasonable application for intermediate-scale quantum computers. 

Childs hopes that the paper encourages other researchers, especially experimentalists, to take note of the variety of quantum algorithms and techniques available for quantum simulation. And he says that others, inspired by the work, have continued digging into the details, working to improve bounds for quantum simulation even further or working to make other algorithms equally appealing targets for early quantum computers.

“This is something that we hoped would come out of the paper—that it would inspire other researchers to think hard about what you have to do to concretely implement quantum simulation algorithms,” Childs says. “And that’s actually happening. We’re working on it, and others are working on it as well.”

Story by Chris Cesare

QuICS is a partnership between the University of Maryland and the National Institute of Standards and Technology. It is one of 16 centers and labs in the University of Maryland Institute for Advanced Computer Studies.