DARPA's Quantum Quest May Leapfrog Modern Computers

In the future, anyone trying to figure out how to use limited resources may reap the benefits of computers that are a hybrid of quantum and classical systems.

Such hybrid computers might prove especially efficient and effective at solving certain kinds of problems, such as strategic asset deployment, global supply chains, battlefield logistics, package delivery, the best path for electronics on a computer chip and network node placement. Research also could impact machine learning and coding theory.

These are known as combinatorial optimization problems, and they often are too complex for humans and even current computing systems to solve. “‘Combinatorial optimization problems’ is a really nasty way of saying problems that come up in all aspects of business or logistics,” quips Creston Herold, research scientist, Quantum Systems Division, Georgia Tech Research Institute (GTRI).

While the phrase “combinatorial optimization” may not exactly roll off most tongues, many people are familiar with this particular class of challenges. “Anyone who relies on getting something from point A to B or figuring out how to use limited resources is grappling with combinatorial optimization problems, whether they know it or not,” Herold says. “So, the military will certainly care. The government cares. Anyone who delivers packages has to figure out these things.”

Herold is part of a GTRI team working with the U.S. Defense Department’s Advanced Research Projects Agency (DARPA) on a new program known as ONISQ, for Optimization with Noisy Intermediate-Scale Quantum devices. The program aims to exploit quantum information processing before fully operable quantum computers are available. The effort will pursue a hybrid concept that combines intermediate-sized quantum devices with classical systems to solve combinatorial optimization problems.

Tatjana Curcic, program manager within DARPA’s Defense Sciences Office, agrees that combinatorial optimization problems are widespread. “Optimization is everywhere. It’s in electronics. It’s in logistics. It’s in how manufacturing works, how you optimize the work process in a manufacturing plant. It’s everywhere,” she says. She also cautions, however, that as a basic research program, ONISQ is not attempting to solve any particular problem. Instead, the goal is to conduct foundational research that scientists can then build upon.

Planning and scheduling also are combinatorial optimization problems. “Let’s say, given a group of nurses in a hospital, how do I meet everyone’s constraints and build a valid schedule where I can cover all of my shifts and deal with everyone who has been on vacation or whatnot?” Herold offers.

He adds that combinatorial optimization problems quickly become too complex for humans. “If you look at really small examples, it feels like doing a puzzle. They’re fun for your brain when they’re small, but rapidly you get to these big problems that are intractable for people to solve on their own.”

Noisy intermediate-scale quantum—the NISQ part of the ONISQ acronym—is a term coined about three years ago by physicist John Preskill. It refers to the kind of quantum computers being developed in the relatively near term. They are considered “noisy” because the qubits involved are easily disturbed by a variety of environmental factors, such as minute temperature changes or electronic or magnetic fields. Such factors make the qubits inherently unstable and difficult to control. “As we work to develop more capable quantum computing hardware in the community, we’re going to have to have these NISQ resources. They aren’t very good. They have a lot of mistakes in them because we don’t have error correction yet,” Herold explains.

ONISQ seeks to demonstrate the quantitative advantage of quantum information processing by leapfrogging the performance of classical-only systems in solving optimization challenges, according to DARPA’s ONISQ website. Perfectly stable and accurate quantum processors may be decades away, but successful hybrid systems would be a major breakthrough.

“This is the first major program that considers quantum computing with NISQ devices, which are quite limited but also unexplored and could be done in a relatively near term,” Curcic says. We don’t even know what the capability will be in the end. We have reasons to believe we’ll be able to demonstrate quantum advantage, but it will be very much a proof-of-principle demonstration that then we can start building upon after this program.”

One possible solution, the researchers suggest, will be to divide up a problem between classical and quantum computers. The classical computers will solve some pieces of the puzzle, and the quantum processors will handle others. Herold describes a theoretical scenario in which a cloud computing resource decides how to divvy up a problem between classical and quantum computers.

“You might have these classical heuristics running and have cloud access to some quantum hardware and then when the classical heuristics struggle, maybe that quantum hardware is utilized for that problem,” Herold posits. “Or, it may be possible to break up problems into chunks and then send some chunks to the quantum processor—the really hard problems—and then put them back together in classical processing afterwards. There are a lot of ways that it could look, and we’re going to be figuring out how best to do that in the next few years.”

Quantum devices with 50 to 100 qubits already exist, and those numbers are increasing all the time, Curcic notes. ONISQ researchers will be tasked with developing quantum systems that are scalable to hundreds of qubits that last longer and have improved noise control.

The four-year program officially kicked off in March and is divided into two phases. It includes two kinds of research—hardware and theoretical. Early this year, DARPA awarded three contracts to teams led by the University of Tennessee, Clemson University and Lehigh University to explore the theoretical possibilities of hybrid computers working combinatorial optimization problems. The agency also awarded contracts to teams led by GTRI, Universities Space Research Association (USRA), Presidents & Fellows of Harvard College and ColdQuanta Incorporated to develop quantum-classical computing hardware. Each team is pursuing different potential solutions.

The GTRI team, which includes the National Institutes for Standards and Technology’s Ion Storage Group, is the only team specializing in trapped ion research. “Our project is called Optimization with Trapped Ion Qubits, which has a snappy acronym, OPTIQ,” Herold states.

A couple of years ago, GTRI demonstrated universal control of as many as four qubits and followed that with a demonstration of a small quantum algorithm that Herold describes as a “toy algorithm.” The DARPA program is a natural extension of that previous research. “The goal there is to build out the hardware to the point we have enough ions and control over them that we can actually solve problems which are interesting in the real world and aren’t just toys,” Herold says.

Meanwhile, USRA is working with the NASA Quantum Artificial Intelligence Laboratory on the DARPA program. In a USRA press release, officials report that the team has been working on quantum algorithms for planning and scheduling for the NASA lab since 2012, resulting in innovations in quantum gates.

For the first phase of the ONISQ program, which will last about 18 months, the hardware-focused teams will be required to demonstrate an initial capability of their technology. Those that perform well will move into the second phase, lasting about 2.5 years. At that point, they will have to demonstrate that their technologies hold a provable advantage over any other existing computation method.

“We will push the community toward building bigger and better quantum processors—bigger, meaning with more qubits and better, meaning qubits that hopefully are going to be less noisy,” Curcic says. The teams also will have to implement some optimizing algorithms, characterize them and compare the solution to the best-known classical solutions. “The hope there is that we will demonstrate an advantage of quantum processing,” she adds.

Showing that quantum systems can perform better than classical computers for combinatorial optimization problems is a serious challenge, Herold says. “That’s a really tall order. We’re starting in this place where we’ve shown control over two and three or four ions, and to meet their metrics and to have enough resources to solve interesting, real-world problems, we need to extend our hardware to have 10 or 20 ions in a year and offer 50 ions the year after that,” Herold adds. “That’s a real engineering challenge for us. It’s not hard to trap those ions, but to actually have control over them and to make use of all of them is really difficult.”

And the competition is stiff. Governments, including the United States, China, Russia, North Korea and most European nations, are racing to gain a quantum computing advantage. Industry also is interested. In the United States alone, Google, IBM, Intel, Microsoft and a host of smaller companies are investing in quantum computing research. “There are tens of hardware computing companies from major corporations to startups that are developing quantum computing hardware and are also racing to really show a useful quantum advantage,” Herold states. “It’s a real sprint.”

He defines a quantum advantage as “actually doing something with the machine that you could not have gotten done any other way, whether that’s in the same amount of time, at the same level of accuracy, or with any other technology.

The GTRI researchers specialize in ion trapping with the use of lasers. Some lasers focus on all of the ions, others on individual ions. “Just expanding our optical setup so that we have focused beams for as many ions as possible is one of the engineering challenges. After that, we also have to make sure we eliminate as many environmental interactions with our ions as we can,” Herold says. “Any other environmental noise in those modalities can mess up the computation that we’re trying to do, so we’re trying to isolate them and just have control over them with our chosen set of laser beams and push that as far as we can.”

Research into hybrid computing solutions is in such early stages that scientists do not yet know what the results or impact will be. “We are, in this program, really going where no one has been in terms of science. We are exploring the unexplored,” Curcic says. “No one has done this before with this many qubits.”