Essence of Quantum Computation

How do atoms, photons and electrons behave? How to build a quantum computer? What is the most powerful thing a classical computer can do? These and other questions are answered by Professor of Mechanical Engineering and Engineering Systems at MIT Seth Lloyd.

A quantum computer is a device that stores and processes information at the level of individual atoms and elementary particles. Now, quantum computation has two parts. First of all, it’s quantum-mechanical and secondly, it’s a computation. The quantum mechanic sounds a bit strange and quantum mechanics is weird, technically speaking. In some sense, the quantum part is easier to understand. Quantum mechanics is just a theory of physics that explains how things behave at their smallest and most fundamental level. So it’s the branch of physics that governs how atoms, photons (particles of light), electrons, elementary particles behave. So if we going build a computer at the scale of atoms and elementary particles by its very nature it will use the laws of quantum mechanics to function. And we’ll see that the weirdness of quantum mechanics, the fact that quantum mechanics is strange and counter-intuitive actually helps to allow us to do computations in ways that you couldn’t possibly do with a laptop or an iPhone.

So the second part about quantum computation is computation. So what’s a computer? Actually, in some sense it’s a little hard a question, I mean, I know a computer when I see one, when I type on one or I make phone calls or when I use Google maps on a computer. But in fact, the idea of computation is a deeper and a more general one than just whether you happen to have, like, an Apple or a PC, or an iPhone or a Samsung. It’s the notion of processing information. So what a computer does: a digital computer takes information and breaks it up into the smallest possible chunks of information which are called bits. So a bit is an elementary distinction between two possibilities: yes or no, true or false, zero or one, or, for that matter, inside a computer capacitor at its low energy state or capacitor at its high energy state.

And that’s in fact how bits are physically stored inside an ordinary digital computer. Low-energy is zero, high-energy is one. And then to perform a computation, the computer, having broken up information to its smallest chunks, it flips and manipulates those chunks and bashes them into them and transforms them in very general ways. In fact, there’s a notion called “universal digital computation” that says “what is the most powerful thing that a classical computer can do by taking bits and by flipping them is a systematic fashion?” So a quantum computer is a computer that takes bits and manipulates them in a systematic fashion, but also operates at a level of atoms, elementary particles, photons (particles of light), electrons – where the laws of quantum mechanics hold sway.

Quantum mechanics is weird. This is a technical term – weird. Niels Bohr, one of the inventors of quantum mechanics, said “Anybody who thinks they can understand quantum mechanics without getting dizzy, hasn’t properly understood it”. Actually, he said it in Danish, which is more impressive. But it’s true: the quantum mechanics is strange and counter-intuitive. To get a feeling of this essence of this quantum weirdness think of something called “wave-particle duality”. I know it sounds weird – wave-particle duality – what does that mean? Well, it means that the things that we think of as particles, like atoms or electrons, have waves that are associated with them. Similarly, things that we think of as waves, like light or sound, have particles that are associated with them. This all takes place at the very microscopic level. Now, what this means is that when you store a bit of information on a quantum computer, say, on the position of an electron, this electron has a wave associated with it.

So, in a classical computer the way you could store a bit is – well, in the case of zero it is a low-energy state – a whole bunch of electrons is over here, one is a high energy state – a whole bunch of electrons over here. Now let’s miniaturize this until we have a quantum bit, which is a single electron. So, zero is a single electron over here, one is a single electron over there. Well, that’s fine, you know, electron over here is zero, you move it over there, it flips to one, you move it over here, it flips back to zero. You have two electrons, you move them back and forth, you’re flipping multiple bits – so there’s nothing wrong with storing and processing information at the level of single electrons. The problem is that the electron is a quantum-mechanical thing, and even though it’s a particle, it has a wave that’s associated with the electron. The wave that’s associated with the electron has something to do with where the electron is. So if the wave of the electron is all over here, then the electron is over here and it’s zero. If the wave for the electron is all over here, then the electron is over here and it’s one.

But the funky thing about quantum mechanics is that the waves don’t have to be just here and there, you know, it doesn’t have to be either here or there, waves are extended objects, you could have a wave that’s here and there at the same time. What does it mean – to have a wave for an electron that’s here and there at the same time? It means that this one electron is simultaneously here and there at the same time. So a quantum bit, or a qubit, as it’s sometimes called, has a funny feature that it can be both zero and one simultaneously, because this electron is here and there at once. Now, this is just weird and counter-intuitive. There’s no classical intuition that corresponds to having something like, you know, a soccer ball being here and there simultaneously, even if a mess can make it look like that every now and then. So with electron you really have electron here and there at once, so a quantum bit, or qubit, can be zero and one at the same time.

So this central feature of quantum weirdness, this wave-particle duality, which is strange and counter-intuitive, and hard to grasp with ordinary intuitions, this means that quantum bits can be zero and one at the same time.

And that means that quantum computers can perform computations in ways that classical computers can’t.

A nice way of thinking of this is if a classical computation is a sequence of bit flips for multiple bits flipping back and forth multiple times, you can think of this in wave terms, you can think of this wave for this as just being like a single wave, like a single pitch, like ‘aaaaah’. Or like a single chant, like ‘ahahahaa.’ So, classical computation is just one wave of a series of pure tones. In quantum computation, by contrast, the waves for all the bits can have multiple values at once – so it’s a symphony. I can’t actually sing a symphony on my own, but you can imagine a symphony. And what’s happening in a quantum computation is that the waves corresponding to each of the computations add up in a way that gives you interference and harmony between these different waves. So the possibilities that are available to a quantum computer are much greater than the possibilities available for a classical computer.

In particular, let’s think of what the purpose of bits is inside a computer. So if I have a zero, or one, a bit could be data. Zero and one sounds so prosaic. Suppose that I ask my fiancée, or I ask my girlfriend: “Will you marry me?” and she sends a bit of information with zero for “no” and one for “yes”. Ok, this is a very important bit for me, and maybe she emails it to me, and that’s maybe not the nicest way to accept a marriage proposition. So, for a quantum marriage she could send a quantum superposition of zero and one at the same time meaning she is feeling ambivalent in a very quantum-mechanical fashion. So what happens when I actually look at the answer to the question? Well, these quantum bits have a feature that if you have a bit with zero and one, zero=no and one=yes at the same time and I actually look to see “ok, see electron over here? – No. See electron over here? – Yes. Then half of the time I’ll find the answer “no”, half of the time I’ll find the answer “yes”. So, if my girlfriend were to tell me that, this would be her way of essentially flipping a coin about whether she’s going to marry me or not.

Now, in a computer a bit can just be a bit of data, like zero or one, but a bit can also be an instruction. So, zero could mean, you know, “do this”, and one can mean “do that”. Like, to get away from marriage metaphors that are making me uncomfortable, to get away from metaphors about marriage, let’s go to mathematics. So, zero could tell the computer to add 2+2. And one could be the instruction to the computer that says “add 3+1”. In a classical computer a bit can either be zero – add 2+2 – or one – add 3+1. But in a quantum computer, because a quantum bit can be zero and one simultaneously, then if you take such a quantum bit and give it as an instruction to a quantum computer, the quantum computer will add “2+2” and add “3+1” at the same time – in some funny quantum sense. So these two different computations occurring at the same time are like two different voice parts in a chorus or two different violin parts played simultaneously in a symphony.

And the essence of the quantum computation comes from the interference between these different parts, just as for us if we hear two sounds played at the same time, it has a sound that comes not from just one sound on its own or the other sound on its own, but from the interference of the two sounds together. Now, this may sound kind of strange and esoteric, and indeed, when you build quantum computers, you are building computers with components on the level of individual atoms, they are very-very tiny computers. You want to keep track of them, ‘cause if you lose them, like you’re never going to find them again. We can ask what we can do with this or why should try to do this when we have perfectly good classical computers.

Well, the idea of quantum computation, of storing bits on individual atoms, was proposed in the early 1980-s by Paul Benioff at Argonne National Laboratories, we should find them in Caltech, and David Deutsch at Oxford, in England. Quantum computers weren’t built, the first prototype ones weren’t built until the early 1990-s when I proposed how you could build a simple quantum computer, and indeed, Dave Wineland, the Nobel laureate in physics, received his Nobel Prize in part for building some of the first simple quantum computers. In 1994, however, a real impetus came for building quantum computers when Peter Shor, then at AT&T and now at MIT, showed that if you could build a quantum computer, even a small one, with a few tens of thousands of quantum bits, it’d be able to perform a million operations, which is nothing for a classical computer.

If you get this quantum computer doing this symphonic kind of computation, then it would be able to break all the codes that we use to transmit information secretly over the Internet.

And as you could imagine, at that point a bunch of people’s ears perked up, not just individuals, but agencies who’d like to keep secrets and who would like to find out other people’s secrets, of course. So these agencies and lots of people said “Oh, wow, it would be great if we could build a quantum computer”.

And so, in the early mid 1990-s this entire field of quantum computation took off, I and my colleagues started building quantum computers, everybody around the world, well, not everybody, but hundreds of people around the world started building quantum computers. Now we have quantum computers which, even if they can’t factor large numbers and break codes, all ashore, they can still do all kinds of interesting things. We’re using quantum computers here at MIT to investigate fundamental physical properties of matter, to even program a quantum computer to see what was happening in the Universe at the very first instant of a second. You can use quantum computers to investigate weird and funky effects that go under names like ‘entanglement’, where particles of light know much more about each other than they have any right, classically, to do so. You can use quantum computation and quantum communication to transmit information in a provably secure fashion, where the security is guaranteed by the laws of nature. And even if these are not the good enough reasons for doing quantum computation, there’s another good reason which is – it’s a tremendous fun. I’ve been myself working on these quantum computers over the last 15 or 20 years, have had a fantastic time exploring how nature works at its smallest and most fundamental scales.