June 2016

Quantum contest

“Extraordinary claims require extraordinary proof,” astronomer Carl Sagan once said (although other famed scientists have made similar statements). And in science, extraordinary claims are certain to face testing.

So several years ago, when D-Wave Systems Inc. said it had developed the first quantum computer, many researchers began investigating the company’s claims.

A University of Southern California team, however, has a big advantage in the pursuit: time on the world’s second-most powerful computer. Itay Hen and Tameem Albash of USC’s Information Sciences Institute and Daniel Lidar, professor of electrical engineering, chemistry and physics, used millions of processor hours on the Department of Energy’s (DOE) Oak Ridge Leadership Computing Facility’s (OLCF) Titan, a Cray XK7, to model the D-Wave’s processor and the problems it could run. The fourth investigator is Travis Humble, co-director of Oak Ridge National Laboratory’s Quantum Computing Institute and a 2016 recipient of DOE’s Early Career Research Program award.

The researchers also have access to a D-Wave computer at the affiliated USC-Lockheed Martin Quantum Computation Center. “We’re trying to find out by simulations whether this machine is quantum,” Hen says.

Most classical computers work with bits or groups of bits and use transistor logic gates to perform operations. Circuit-model quantum processors, still in their infancy, use an analogous system but seek to employ quantum behavior like superposition and entanglement to greatly cut the time to solution.

D-Wave says its computers use a contrasting approach: adiabatic quantum annealing. It solves optimization problems, finding a solution that best maximizes or minimizes a quantity or property – the objective function – from among a myriad of possibilities. In essence, the solution is the quickest or lowest-cost way to do something. Such problems can be recast as finding a molecule’s lowest-energy, or ground, state.

‘We have come up with a very reasonable and quantum model to capture the physics of the device. This was a big deal for us.’

Finding the objective function can take lots of time because the combination of properties governing it often is enormous. Molecules also could be stuck in locally low-energy states with high-energy barriers blocking them from finding their true ground states. Quantum annealing finds this optimal state by gradually reducing the size of quantum fluctuations and overcoming energy barriers with quantum tunneling – essentially going through energy barriers rather than over them.

But with various algorithmic approaches, classical computers can achieve something similar to quantum annealing, so it’s not clear whether D-Wave’s device actually exhibits quantum behavior or, even it does, whether it’s significantly faster than a standard approach.

The USC researchers wanted to develop models that accounted for the D-Wave machine’s behavior. In their arsenal: a 2015 ASCR Leadership Computing Challenge (ALCC) grant of 22 million Titan processor hours.

The team wanted to find “which models predict best the output from the D-Wave device. Are they quantum models? Or classical models? Or maybe hybrids?” Hen says. “The other major question we tried to answer is, given that it is quantum, is it useful? What kind of problems can we solve on this device?”

The team’s models not only had to recreate quantum mechanical behavior but also how the D-Wave device interacts with its environment. And the researchers had to engineer problems that definitively separated quantum and classical properties. “After generating these problems, these good benchmarks, we wanted to test or to benchmark the D-Wave against state-of-the-art algorithms and those, too, we ran on Titan.” But “on even a supercomputer, it was a challenge.”

Hen was principle investigator on a similar quantum computing project that used a 2014 ALCC grant of 45 million Titan processor hours. The momentum from that was so great, Hen says, that the researchers consumed their entire 2015 allocation in the first month. With some advice from Jack Wells, OLCF science director, the team found ways to extend its hours to around 60 million under the latest grant.

The payoff: The team developed a model that consistently captured the D-Wave device’s output. Based on those comparisons, the team believes it does exhibit quantum features – specifically, entanglement, in which the behavior of two particles is connected even though they’re separated by great distances.

“We were able to rule out a lot of classical models – which doesn’t mean there are no other classical models out there that can mimic the device’s physics,” Hen says. Nonetheless, “we have come up with a very reasonable and quantum model to capture the physics of the device. This was a big deal for us.”

The team also has developed ways to find benchmark problems to test quantum-annealing devices. If such machines really use quantum tunneling, Hen says, they should be superior in solving specific energy-barrier problems.

“But we haven’t seen that yet. We don’t have anything that tells us the quantum annealers are really superior,” Hen says. For the D-wave, “we don’t have this smoking gun that says this device is not only quantum, but it also beats every other classical supercomputer out there.”

After running its Titan simulations, however, the team knows what to look for and how to find it – something that will require more supercomputer time. “We’re at the stage where we have to basically run the competition between the device and (Titan) and see who wins.”

Meanwhile, researchers continue tuning classical computing algorithms to challenge quantum computing’s speed and perhaps even capture the benefits of quantum tunneling.

“That’s part of the competition,” Hen says. “We want good competitors and so we also are developing state-of-the art classical algorithms. Some of them are quantum-inspired, in a way.”