At this year’s SC13, the subject of Rupak Biswas’ daily talk at the NASA booth delved into the strange landscape of quantum computing and quantum physics – an odd realm with mind bending features like entanglement, superposition, particles that behave like waves and visa versa, and non-locality.
Biswas is the deputy director of the Exploration Technology Directorate at NASA’s Ames Research Center, Moffett Field, Calif. Last summer the agency installed a D-Wave Two quantum computer in the NASA Advanced Supercomputing (NAS) facility at Ames. NAS is also home to the agency’s most powerful supercomputer, Pleiades, a petaflop machine from SGI.
NASA is conducting on-going studies to determine the potential for quantum computing to solve difficult problems of importance to the agency.
In this special feature, John Kirkley talks with Dr. Biswas to learn more about NASA’s fledgling involvement in the weird world of quantum computing.
John Kirkley: Rupak, why is NASA so interested in quantum computing?
Rupak Biswas: Well John, NASA has always been interested in modeling and simulation. All the various missions that we do in Earth and space sciences, aeronautics, and space exploration, require a lot of experimental testing such as wind tunnel and flight tests, as well as a large amount of numerical modeling and simulation. The latter are digital experiments – not only are they cheaper, but they also have a predictive capability that you cannot realize in real world experiments. With simulation you can predict things happening in the future, a capability obviously not possible in real life.
But even though we’ve been using modeling and simulation for many years, there are clearly problems within NASA – like optimization and scheduling problems – that are intractable for a reasonable number of unknowns on a classical machine. We have solved these on classical machines so far by resorting to heuristics.
John Kirkley: In other words, guessing.
Rupak Biswas: Right. So you are reducing your search space and now it becomes a tractable problem. You may get a suboptimal solution, but at least you got it in a reasonable amount of time, so you can live with it. And there are many examples of these kinds of problems within NASA: such as mission planning and scheduling on Mars (for example, navigating the terrain and scheduling science experiments) – these are clear examples of difficult optimization problems where a quantum computer promises to give you better solutions.
John Kirkley: Now, quantum computing is notoriously difficult to work with. How are you finding working with the D-Wave machine?
Rupak Biswas: Well, one of the challenges of working with quantum computing is you need well behaved qubits that stay in a superposition state long enough to do something of value. You also need a reasonably large number of qubits. People have run experiments in the lab using two or four qubits, but they are so tiny that it’s hard to produce something useful.
The 512-qubit D-Wave system became operational in early September and we’re getting some preliminary results. One of the things we seem to have confirmed is that the machine does do quantum tunneling. This allows us to focus on the optimization of navigation, scheduling and planning problems. You embed the problems in the D-Wave machine and run them. One thing about quantum machines – at least in the D-Wave version – because it’s a quantum annealing machine, you need to execute the same problem multiple times in order to get a probability distribution.
John Kirkley: You mentioned quantum annealing. Could you please tell me more about that?
Rupak Biswas: Quantum annealing, similar to simulated annealing in numerical methods, is a relatively new term which describes moving from a chaotic state to where you want to be. For example, people doing manufacturing will start with a piece of metal at a very high temperature and then cool it, but not too rapidly so that the metal becomes rigid. During this slow process you continually mold the metal to the form that you want. So you start with a highly chaotic state, then you slowly shape the metal to its finished form. This is the same process we follow when moving from a chaotic quantum state to a stable solution.
John Kirkley: Let’s talk about some of the applications for this technology – for example, navigation and scheduling.
Rupak Biswas: Right now our main focus is on three areas. One is navigation and scheduling – part of mission planning. For example, to solve a navigation problem you have to create a plan that follows a certain sequence. Quantum computing can tell you the best way to do this sequence, something that would not be possible on a classical machine given the amount of variables involved. Planning is also has a scheduling component where you are trying to take multiple actions simultaneously to reduce the total time. For example, you might want to schedule a number of tasks on the International Space Station that are only possible if certain preconditions are met. You want to make sure that two actions that will conflict with each other are not going on at the same time.
Another kind of scheduling problem is attempting to schedule jobs on a supercomputer – that’s a very well-known hard optimization problem. And a third application that we’re looking at is the Kepler search for habitable planets. That’s a classic search problem – we’re trying to find a needle in a haystack. In fact, it’s not even a needle; there’s something unknown in the haystack and we’re trying to find it. And that involves a search problem in which a quantum computer could be better at classifying these characteristics. This will allow us to find planets that a classical algorithm would overlook.
So these are the problems we’re currently working on, but there are a whole bunch of other problems. For example, how to optimize air traffic control as we develop increasing numbers of unmanned vehicles with more distributed control on the vehicle itself.
John Kirkley: Now the D-Wave machine is not the only computer you’re working with – you have the Pleiades supercomputer as well. Are there any interactions between the two machines?
Rupak Biswas: We haven’t done that yet – we are still in the early stages. We expect that quantum machines are going to be like special purpose attached processors to a classical supercomputer. Even now we don’t deal directly with the D-Wave machine; there is a front end that transforms your input into a form that the D-Wave can understand. We expect that the D-Wave or any other quantum machine will be attached to a classical supercomputer, which will act as the gateway – the front end to the users. The users will load their problem on to the classical machine and the classical machine will then take the parts of the problem that need to be optimized for, say navigation or search, and hand them off to the quantum machine. The answers will then be integrated into the bigger problem and the classical computer will return the results to the user.
John Kirkley: So the classical computer essentially becomes a front end to the quantum computer.
Rupak Biswas: Exactly.
John Kirkley: Let’s take a look at the near future. What do you expect to see happening in your work with quantum computing in the next five or ten years?
Rupak Biswas: One of the things we expect is for quantum computing to move away from the very conceptual state it has occupied for the last 15 or 20 years to actual implementations. Some of these machines may do entanglement, but not tunneling, or visa versa. We will also see more ways to do quantum computing involving a greater number of qubits – or maybe using trapped atoms or ions, or quantum computers based on photons.
We also expect that a community will slowly build up that is looking at quantum algorithms independent of the hardware. There will be a lot of activity around devising new algorithms that can be efficiently implemented on quantum machines.
Over the next five or 10 years we will see a whole industry develop around quantum computing.