A Quantum Leap in Computing

WEIRD LEMONADE

NOVA: Quantum mechanics has taught us that nature is pretty weird. Is it possible to take advantage of that?

Seth Lloyd: Quantum mechanics is weird, that's just the way it is. It's a sad thing, but it's true. In fact, there's a funny phenomenon where people who get their Nobel Prizes in quantum mechanics don't believe in quantum mechanics because it's so weird—starting with Einstein. Einstein got his Nobel Prize for the photoelectric effect, all about quantum mechanics and photons, yet he never really believed in quantum mechanics.

Quantum mechanics is just completely strange and counterintuitive. We can't believe that things can be here [in one place] and there [in another place] at the same time. And yet that's a fundamental piece of quantum mechanics. So then the question is, life is dealing us weird lemons, can we make some weird lemonade from this?

Well, if you can have something that's here and there at the same time, then you can have a quantum bit [of information], or Q-bit as it's sometimes called, that can effectively register zero and one simultaneously. If you can do that, you can start processing information in some funky, quantum mechanical way, which nobody understands, that allows you to take advantage of this quantum weirdness.

Let's back up to some basics. How does a traditional computer store information?

Sure. A traditional digital computer like the one that I have on my desk operates by breaking down information into its smallest possible chunks. The smallest chunk of information is a bit. A bit is normally thought to be either zero or one. What a computer does is simply bust up the information into the smallest chunks and then flip them really, really, really rapidly in a systematic fashion.

Is that information—that zero or one—something physical, like a switch?

Yeah. The IBM physicist Rolf Landauer was fond of saying "information is physical." It's a slogan, but it really is true in the sense that whenever we process information, be it in a computer or in our brains, that information is represented by something. In your computer, if you have a bunch of electrons over here—we call that a zero—and a bunch of electrons over there—we call that a one. And if these electrons go from here to there, then zero is turning into one, the bit is flipping. An ordinary computer is simply doing that with many, many bits, billions of times a second.

How is a quantum computer different?

Think of miniaturizing a computer so that a bit is stored on an individual electron, so that a single electron over here is zero and a single electron over there is one. Now, an electron has this funny feature in quantum mechanics that it's really a wave, and this wave can be both here and there at the same time. And that means that the quantum bit that the electron represents registers both zero and one simultaneously. It also wiggles up and down a lot like a wave.

So how do you make those quantum bits into a computer?

Well, that's trickier! But nature supplies us with lots of electrons. And at bottom, nature is quantum mechanical, so all the things that we think of as particles like electrons have waves associated with them. If we can control them in a systematic fashion, then we can make a quantum computer.

CODEBREAKING: A "QILLER" APP

Why are quantum computers useful? Are they, in some sense, better than a standard computer?

Well, the first reason that quantum computers are useful is that they're just cool, let's face it! Like, so weird, like, whoa! Amazing, can that really happen? And the answer is "yes," because you can build quantum computers, and we've been building them for years now.

But the second reason is that if you have a different way, and a fundamentally weird way, of registering and processing information, then it means you can do computations in ways that our classical brains could not have dreamed of.

Now, actually, for many years, nobody could really figure out any problems that quantum computers could solve better than classical ones, and quantum computers were largely just a kind of a curiosity. They were known to be possible in theory. Then, about 15 years ago, I showed that they were possible in practice by proposing a way to build quantum computers. But nobody had a good application for them.

Then, in 1994, Peter Shore, who was then at AT&T and is now at MIT, came up with a killer app for quantum computers. (And maybe we should spell it Q-I-L-L-E-R because whenever you quantize something, you take a letter and turn it into a Q.) The Qiller app for quantum computers is breaking codes, codes like the ones we use whenever we use our bankcards.

How do these codes work?

Public key cryptography works in the following way: Suppose I want to buy a song from iTunes, and I give them my credit card number. Well, if I just sent my credit card number over the Web, that wouldn't be a very good idea because anybody who's listening in could use it to buy stuff that's more expensive than a tune on iTunes. So iTunes sends me what's called a public key, and I use this public key to encrypt my information about my credit card. Now, iTunes also possesses something called a private key, which allows them to decode that information. So the public key will allow anybody to encode information, but only the person who has the private key can decode that information.

The normal way of doing public key cryptography was developed by [Ron] Rivest, [Adi] Shamir, and [Len] Adleman here at MIT. The idea is that you have a very long number, hundreds of digits long, and this number is the product of two smaller numbers. The long number is the public key, and the numbers that make up the product are the private key. So in order to get the private key from the public key, you have to figure out what the two smaller numbers are. This is called factoring, right? Like the factors of 15 are three and five. Well, factoring 15 ain't too hard, but factoring a number that's 500 digits long is hard. Quantum computers can factor large numbers easily, and this is what Peter Shore told us.

Can't a regular computer factor a 500-digit number?

A conventional, classical digital computer could, indeed, factor a 500-digit number, but the only known methods are basically, well, let's try these two numbers and multiply them together and see if it's this big number. Let's try these other two numbers. The problem is that there are gagillions—that's a technical term—there are gagillions of numbers that could be multiplied together, and to explore all those numbers would essentially take the age of the universe on a conventional digital computer, even the biggest supercomputers.

So how can a quantum computer solve the problem?

On a quantum computer, you can actually factor these numbers very, very rapidly. The way it works is, well, it's very sneaky and tricky, but it boils down to the following:

In this factoring problem, there's a kind of a hidden periodicity. So you can rephrase the factoring problem as, oh, I've got this wave, and it wiggles up and down over some very long time. Intuitively, quantum mechanics is about waves. And zero and one have a wave that's associated with them, and this gigantic number that's hundreds and hundreds of digits long also has waves associated with it. Now, waves are famously, you know, wavy, and quantum computers are darn good at figuring out how fast waves wiggle up and down.

Peter Shore showed that you can set up this factoring problem so that if you're given the wave for this 500-digit number, then you can find the hidden waves for the two 250-digit numbers which, when multiplied together, give you the 500-digit number. It's very sneaky, and it involves more stuff than that, but at its quantum heart, the guts of the quantum problem, that's what it is, finding out the periodicity of waves.

PREDICTING THE WEATHER AND OTHER MIRACLES

What other problems might quantum computing solve?

It's hard to find problems that quantum computers are better at solving than classical computers, but shortly after Shore's algorithm was proposed, [computer scientist] Lov Grover pointed out that quantum computers could search a database much faster than a classical computer. So, for example, suppose I have nine pockets, and my wallet is in one of them. I've got to look in up to nine pockets before I find my wallet. Well, a quantum computer could do that in just three operations. And if you had 100 pockets, the quantum computer could do it in 10 operations, or a million pockets, a thousand operations. So a quantum computer could seriously speed up the ability to search a database.

More recently, my colleagues Aram Harrow and Avinatum Hassidim and I here at MIT showed that quantum computers could actually solve big sets of equations like the kind that describe the weather or the stock market much more rapidly than a classical computer. Again, the reason is that there's a kind of hidden wave nature to such equations. Waves add up—they're so-called linear. We showed that a quantum computer could solve any set of linear equations where waves are adding up, and these kinds of equations are very common.

How would it improve weather forecasting?

If we had a set of equations with many, many variables, like the weather—where there are thousands of weather stations getting lots and lots and lots of data—then we might be able to analyze or parse that data much faster than a classical computer. Currently, a classical computer might take more time than it actually takes the weather to evolve to predict the weather. But predicting the weather would be miraculous. So I'll believe it when I see it.

Are there other important applications for quantum computing?

There are. Classical computers have a very hard time analyzing quantum stuff. And a long time ago the Nobel laureate Richard Feynman speculated that quantum computers might be good at teasing out the characteristics of physical systems. Feynman said, well, if we just had a quantum computer, then we could map the quantum weirdness of the system we're trying to analyze onto the quantum weirdness of the computer and then we could actually figure out what the heck is going on. About 10 years ago, I showed that, in fact, you could do this. This [studying quantum systems] is perhaps the most common application of quantum computers right now.

It's recently been discovered that actual living systems such as photosynthetic bacteria in plants are using funky quantum weirdness techniques to make energy transport in plants and bacteria be much, much more efficient. It was kind of a drag because, you know, we discovered all these cool quantum techniques, and then we found out, whoa, these bacteria have been doing it for a billion years! Well, they didn't publish, so it's okay.

Another example is in protein folding. When proteins fold up into the right kind of configuration to be biologically active, lots of quantum stuff is going on there. It's very hard to simulate protein folding, even on giant supercomputers. Quantum computers could be very useful for looking at these things.

GETTING REAL

So how real are quantum computers? It sounds as if we actually do have some quantum computers doing stuff at the moment.

How real are quantum computers? Wow, depends on your notion of reality. I'm a professor of mechanical engineering. I don't mess with questions about the nature of reality. On the other hand, we actually have lots of quantum computers sitting around the MIT campus.

Right now, we have small, general-purpose quantum computers that can basically do anything you ask them to, if you ask nicely. Then we have large, special-purpose quantum computers that can solve specific problems better than classical computers can. What we don't have is a large, general-purpose quantum computer of the sort that would be needed to break codes, strike fear in the heart of the National Security Agency and other three-letter agencies. Which is probably a good thing.

Are we going to get them?

It's hard to build large-scale quantum computers. Nature hasn't been obliging enough to allow us to build quantum computers that have enough quantum bits to factor large numbers and break codes. I think it's probably going to be a reasonably long road before we have this kind of quantum computer.

What about the quantum computers that you do have now. What are you doing with them?

With the special-purpose quantum computers that have thousands or tens of thousands or, actually, billions of quantum bits, we can simulate a variety of quantum phenomena to understand how these complicated quantum phenomena work.

Then we have small-scale quantum computers with 10 or 15 quantum bits, which can do almost anything we ask them to. These are actually wonderful devices for understanding the natural weirdness of quantum mechanics. The small quantum computers we've been building for the last 15 years are, effectively, this quantum sandbox that allows us to figure out how quantum sand works.

For instance, one of the best uses for quantum computers, including the small-scale ones we have right now, is to explore the types and uses of entanglement.

EMBRACING QUANTUM WEIRDNESS

What is entanglement?

Okay, now let's go to some serious quantum weirdness. So far, we've only encountered ordinary quantum weirdness, like electrons being here and there at the same time. But you also can have two electrons that are in some really funky quantum state—not just zero and one at the same time, but zero-one and one-zero at the same time. This is called entanglement.

At first, it doesn't sound so strange. But, in fact, it's really strange. Suppose I have electrons that are zero-one and one-zero at the same time. Now, I make a measurement of one of the electrons. Well, if I find this one to be zero, the other one must be one. Or if I find this one to be one, the other one must be zero. It seems as if, by making a measurement on this electron, I've somehow changed the state of the other electron.

That is pretty funky. This, by the way, is what Einstein really objected to about quantum mechanics. Unfortunately for Einstein, it is the case. People have done many experiments [to prove it].

Why was entanglement so offensive to Einstein?

Well, it looks as if by doing something here, you're instantaneously changing something over there. One [electron] could be in the lab and the other one could be off in Alpha Centauri [a star system more than four light-years from Earth]. If you do something here in the lab and that suddenly changes something off in Alpha Centauri, that violates all notions of relativity, like signals only propagating at the speed of light. It's not good.

So how is it possible?

I don't know! Look, quantum weirdness already violates our intuitions. Entanglement completely violates our intuitions. I don't know how it's possible, but I know that it is possible.

Are there any uses for entanglement?

One well-known use of entanglement is teleportation, which at first sounds crazy. But, in fact, it turns out that with entanglement you can actually teleport things. Indeed, if you could do this on a large scale, then you wouldn't have to drive to work. You could just get into the teleporter at home and show up at your job. ("It's not quantum computing; it's quantum commuting." Sorry, bad joke.)

Even more extreme, my colleagues and I recently showed that you can think of time travel, the process of going from the future into the past, as a kind of teleportation of information from now to back then. Moreover, we were actually able to use a simple quantum computer to demonstrate this effect. We could investigate what happens when you send a photon billionths of a second backwards in time.

But perhaps the best-known use of entanglement is in quantum cryptography. Quantum cryptography is a peculiarly quantum mechanical way of getting information securely from here to there. Entanglement can be used to create a purely secret key that no eavesdropper can figure out.

How do you grapple with the fact that quantum mechanics seems to defy our notion of reality?

My opinion is, reality is overrated, at least our notion of reality. We have this very macroscopic, classical idea of reality. We're biological systems that process information in a very specific way. Yet we like to think that this very specific way that we process information constitutes reality. Fuhgeddaboudit.

To the extent that things like electrons and photons and quanta are processing information, they're doing it in a very different way. If you want to think of reality in terms of how we process information or how they process information, their reality is very different from ours. It's so different; it's really hard for us to get a sense of what kind of reality this is.

Do you agree with Niels Bohr [a founding father of quantum physics], who basically said, there are just some things we're not going to understand? You just have to accept that this is the way the universe is. Or do you think that there's a possibility that we're going to be able to see deeper to actually understand this weirdness?

Niels Bohr made a philosophical distinction to separate the world into its quantum part and its classical part. This wasn't a practical distinction; it was a philosophical distinction: We are classical, this is quantum mechanical, and ne'er the twain shall meet.

One of the good things about our new science and technology of quantum information processing is that we can make these worlds meet. We can forge bridges between the quantum and classical world. I would say we now have a new and potentially profound understanding of the quantum world, which would have been unimaginable to Bohr and to Einstein.

Quantum mechanics is irreducibly weird. But as we build more devices that allow us to talk with atoms and have them talk back to us, and as we learn the language of quanta, of elementary particles—electrons and atoms—we're entering into their own world and acquiring, if you like, intuitive understanding of this weirdness that we did not possess before.

Do you find the weirdness of the quantum world a beautiful thing, or a disturbing thing, or both?

Many people find quantum weirdness disturbing. Famously, many Nobel laureates in quantum mechanics find quantum weirdness disturbing, maybe because they've spent so much time trying, unsuccessfully or with partial success, to bend their intuitions around that quantum weirdness.

I find it wonderful. The fact that, at bottom, things behave in a way that's totally different from how our macroscopic intuitions want it to be, I think that's great. That's fantastic. I've always thought that my macroscopic intuition is kinda worthless [laughs] because it's so frequently wrong. It's a strange and fascinating and wonderful place, and the fact that it's weird is just gravy.