NASA begins exploring quantum computing

Deep within the recesses of NASA's Ames Research Center in Mountain View, Calif., a small team of researchers is beginning to run applications on a revolutionary machine that could pave the way for a new era of computing.

After delays caused by the partial government shutdown, scientists in NASA's Advanced Supercomputing Division are running applications on the D-Wave Two to probe the possibilities of quantum computing.

NASA's early experiments with the computer, developed by D-Wave Systems, are geared toward optimizing aeronautics and other processes vital to the agency's mission, said Rupak Biswas, deputy director of the Exploration Technology Directorate at Ames. But in these primordial days of quantum computing, every experiment will serve as benchmark for where the technology is and where it might go, he added.

"From our perspective, we are trying to get better answers," Biswas said. "Am I getting the same solution as a classical computer, but faster? Second, if I didn't get a faster solution, did I get a more accurate one? And third, did I find solutions that a classical computer never found?"

In the next five years, NASA will share access to D-Wave Two as part of a three-way partnership with Google and the Universities Space Research Association. USRA's team has not yet carried out tests with D-Wave Two, but Google engineers have been busy refining classical computing algorithms to pit the processing capabilities of today's computers against the D-Wave Two.

NASA's efforts have been more mission-oriented, but neither NASA nor Google expects to publish research results until early next year.

In traditional computing, data is encoded as either a 1 or a 0, but a quantum computer's use of quantum mechanical phenomena allows a quantum bit, or qubit, to represent a one, zero or both values simultaneously.

The simultaneous calculation is the key.

Even today's fastest supercomputers, which crunch trillions or more operations per second, carry out only one operation at a single moment in time. There is no classical computing approach in today's desktop PCs or supercomputers equivalent to the way the qubit allows information to be processed.

Biswas said NASA's efforts on the 512-qubit D-Wave Two have concentrated on planning missions, scheduling processes and re-analyzing portions of data collected by the planet-seeking Kepler telescope. In mission planning, NASA might use its quantum computer to come up with the optimal navigation plan for the Mars Curiosity rover, with variables that include various stop points and resource limitations.

NASA also wants to use the quantum computer to schedule supercomputing jobs. At Ames, NASA's Pleiades, one of the most powerful supercomputers in the world, constantly runs jobs but almost always has open nodes available for more work. Assuming 1,000 nodes are available to carry out a 500-node job, Biswas said the quantum computer should be able to sift through a gargantuan number of node combinations to tell NASA engineers exactly which 500 nodes to use for optimal results. NASA currently uses a classical computing approach to guess which nodes to use.

Finally, NASA is beginning to use D-Wave Two to look at the light-curve data of stars collected by the Kepler telescope. The quantum computer has nowhere near the capacity to sift through all the Kepler data, but if it looks at a small portion and finds additional planets hiding within, it would be a groundbreaking moment in quantum computing.

NASA will develop further experiments with D-Wave Two based on the results of the initial applications.

Challenges and questions

About the only thing D-Wave Two and a classical computer have in common is the word "computer."

D-Wave Two takes about one month to boot up because of the complex calibration necessary, and its 512-qubit Vesuvius processor operates at 20 millikelvin, which is 100 times colder than outer space. Without shielding to protect it from Earth's magnetic field, the machine would be nothing more than a large paper weight.

The biggest challenges, however, come in its actual use. Classical algorithms and quantum algorithms are not interchangeable, and a lot of work goes into feeding the right information to the D-Wave Two.

First, engineers have to map a problem in quadratic unconstrained binary optimization, a mathematical model for any optimization problem and the input form required by any variant of quantum computer. Biswas said there is not a set way to do this, so engineers use a variety of math tricks to convert optimization problems to QUBO.

The larger challenge, though, is taking the QUBO form of the problem and embedding it into the D-Wave Two hardware.

All 512 qubits on the machine are not totally connected, yet problems require multiple qubits to work "in such a way that they actually represent a single vertex on your graph," Biswas said. D-Wave Two's 512 qubits are composed of 64 unit cells. Each unit cell is made up of 8 qubits, four on one side and four on the other, with each qubit composed of a bipartite graph.

"How to embed QUBO onto quantum architecture is the real problem," Biswas said, adding that the process can be "convoluted and can take a lot of work."

Once a problem is embedded in quantum architecture, D-Wave Two produces answers in the form of probability. In classical systems, calculations carried out repeatedly that measure unchanging variables such as height or weight produce the same results. That is not the case in quantum systems where measurements change the system, Biswas said, so engineers typically run a problem thousands of times or more and then examine the probability distribution and measure value accordingly.

It is far from simple science. Questions even remain about whether D-Wave Two is a true quantum computer.

"We don't know yet," Biswas said, but he added that thus far, the machine clearly demonstrates quantum tunneling and superposition -- two important features of any quantum computer. Less clear is whether D-Wave Two exhibits quantum entanglement across unit cells beyond those interconnected 8 qubits.

Regardless, the most important thing will be determining "whether this device, whatever it might be, might solve problems better than classical machines," Biswas said.

NASA plans to upgrade the machine to 2,048 qubits in the next year or two and potentially to 4,096 by 2018, depending on budget and results. Biswas envisions an ecosystem developing around quantum computing in the next five years, with the potential for finding better ways to convert problems to QUBO form, advancements in embedding QUBO into quantum architecture and improvements in linking qubits together.

"We believe, just like 50 years ago with classical computing, we are in the early days of quantum computing," Biswas said. "Clearly, it has moved one step forward and is no longer conceptual."