AUSTRALIAN FRONTIERS OF SCIENCE, 2003
Canberra, 31 July to 1 August 2003
Quantum computing
theoretical challenges
by Dr Howard Wiseman
 |
Howard Wiseman has been a world-leader in developing theories for controlling quantum devices by feedback over the past 10 years. He has applied his theories in areas from metrology to quantum computing, in fields from optics to nano-electronics. Just last year, his theories were validated in two ground-breaking experiments conducted by his collaborators in the USA. In recent years, Howard has also made important contributions in the field of quantum information. This includes work on small-scale space-efficient quantum algorithms (theory and experiment) and the theory of quantum entanglement constrained by restrictions on the possible physical operations on a system. He was awarded the Australian Academy of Science's Pawsey Medal in 2002. Currently he is a QE-II Research Fellow and Manager for the Griffith University Program within the Australia-wide Centre for Quantum Computer Technology. |
Click on image for a larger version of figure 1
Before saying exactly what quantum computing is, I thought I would jump straight to the motivation of our interest in it. To begin with I will talk about Moore's Law which is basically just an empirical law based on observations from the last 40 years or so, that computing power doubles every 18 months. So if you plot something like number of transistors on a chip versus time on a log scale, you get a pretty good, straight line. As a consequence of this, the only way you can pack more transistors onto a chip is by making them smaller. So this is the flip side, showing transistor size as a function of time, with again a nice straight line (figure 1).
If you extrapolate this to about 2030 the computer industry assumes that this is going to keep happening for some period of time, at least all you see is that the transistor size is going to be about 2 nanometres, which sounds small but when you really think about the size of silicon, et cetera, that means that these transistors would have to be about four atoms across. There is a problem there, because conventional or, as physicists say, 'classical' semiconductor physics breaks down at that point. The reason it breaks down is quantum mechanics: at that atomic scale you get very strange effects due to quantum physics.
However since about 1995 there has been a change, at least by physicists, to view quantum effects like this not as a bug but as a feature, and this is what quantum computing is all about. So the reason that it can work as a feature is that what has been shown is that quantum computers can be much more powerful than a classical computer of the same size. I will talk about that as we go on.
I should point out that quantum computing is not something which just exists in isolation; it is actually part of a broader area, which again has arisen in the last decade or so, which has come to be known as quantum information science. That includes a lot of other things for example, quantum cryptography, which I should point out is actually a quantum technology already in use by Ultrasecure Communication, in Washington.
Now I will outline the rest of my talk. I am going to begin by introducing quantum computing very gently, by talking about the most basic element of any sort of computing, that is, a bit or, for quantum mechanics, a q-bit. Even with the single q-bit, I can show you something interesting which you can do but which you could not do with a single classical bit. Then I will talk about how you go from a quantum bit to make a full-scale quantum computer, and then what you would be able to do if you had a quantum computer. I will finish with the theoretical challenges I am supposed to talk about.
For classical computers, the basic element is the bit, which is just short for 'binary digit'. This is a thing which can, basically, take just two values, or have two states, 0 or 1 those are the conventional things which we call it. In practice, this could be a voltage which could be set as either 0 volts or 5 volts, for example. That is the logic. But basically any system which can be in two states could act as a bit in that case.
A quantum bit, or q-bit as we call it, is exactly the same as a bit, in the sense that when you look at it you find it in one or other of two states, which again we will conventionally call 0 or 1. But the difference about a q-bit is that when you are not looking at it, just as an electron can be in two places at once, a q-bit can be simultaneously in state 0 and state 1. We call this a 'superposition', of being in both of those states at once. Mathematically, we write down an expression like this: ψ = α 0 + β 1. The Greek letter ψ is the conventional symbol used to represent a quantum state, and α and β are two complex numbers, and here 0 and 1 are the possible states. Don't worry too much if you don't remember what complex numbers are all about; they have to do with things involving the square root of -1, but that is not incredibly important.
A more important thing to know is that these complex numbers are called probability amplitudes. The reason they are given this name is that they are not actually probabilities; to get probabilities out of them you have to take the modulus squared of them. And then they are the probabilities that when you look at the q-bit you find it to be either in state 0 or in state 1. So this number |α|2 the modulus squared gives you the probability that you will find it 0, and this number |β|2 will give you the probability that you will find it can be in state 1. But when you are not looking, it is in this superposition in both.
Click on image for a larger version of figure 2
There are any number of physical systems that could act as q-bits, but the simplest one to explain is the spin of an elementary particle (figure 2). It turns out that an elementary particle like an electron acts like a tiny top, spinning all the time. If you put it in a magnetic field, which conventionally we take to be in the z direction like this, then that basically defines our two preferred states, 0 and 1. So the 0 state we take conventionally to be when the electron is spinning up, and the 1 state we take to be when the electron is spinning down. And when you look at an electron in a strong magnetic field, you will find it to be in one or other of those two states. But when you don't look at it, or before you look at it, the electron can actually be in a superposition of those two states.
Physically, what that corresponds to is that the electron could be spinning in some other direction. So, for example, if I have a superposition which is 0.7 times the state 0 plus 0.7 times the state 1 [ψ = 0.7 0 + 0.7 1], that actually corresponds to an electron spinning around the x-axis of space, whereas if I introduce my imaginary number [ψ + 0.7 0 + (0.7 i) 1], I can get an electron which is spinning around the y-axis. So, basically, for a single q-bit there is a very nice, simple physical way to picture what a superposition means.
Click on image for a larger version of figure 3
The nice thing is that I can actually show you that, with a single q-bit, you can do something interesting computationally that you could not do with a single bit (figure 3). Specifically, it is as follows. What I want you to imagine is this scenario: we have two read-only bits that means these are going to be bits that never change from their initial values, because they are read-only and I will call them u and v. So the initial values are u and v. These are just conventional, classical bits, so their values are 0 or 1.
Then I am going to say that I just have one processor bit. For the moment I will talk about classical computers, so I will call that b. I am going to start with it in the state b = 0. And I am going to imagine that I have a 'hard-wired' program now, so that these two read-only bits can interact with the processor bit in other words, they can change the processor bit but they can only change them one at a time. So I can have u changes b or v changes b, but not both at the same time.
The question is: can I calculate the product of those two numbers, uv? Can I come up with some program so that at the end of it my classical bit is in the state which is the product of those two read-only bits?
Classically the answer is simply no. You can convince yourself of this if you think about it, because basically the only thing which you can do with a classical bit, the only operation you can do on a classical bit, is something called the NOT operation. That is something where, if you are in state 0 to start with, you change into state 1; and if you are in state 1, you change back into state 0. So, if you think about it, if your u acts on it, it can change b from 0 to 1, but then if your v acts on it, it is just going to change it back into 0 again. So in the end you haven't computed the product.
The way that quantum mechanics gets around this is that there are actually infinitely many operations that you can do on a single quantum bit. Again I can picture these quite easily. Basically, they can all be built up of elementary operations which I can think of as just being rotations around the different axes in space for this particular physical realisation of a q-bit. x(θ) just means rotations around the x-axis by the angle θ.
Click on image for a larger version of figure 4
Figure 4 is an example. Here is an arbitrary superposition, some superposition of 0 and 1 pointing here. If I act on it by this operation, which is 180° rotation around the z-axis up here, then I rotate into this state over on this side here. So that is just an example of a quantum operation.
How can I use this to solve the problem which I set out before? Here is the answer. Here you have a quantum computer program. The way we do it is to begin the same way, we set up the quantum state to be initially in the state 0 and these have their preset values u and v and then I go through the following. Probably, rather than read through the lines, I will just explain what goes on over here.
The first line says that if u = 1, then do a -90° rotation around the x-axis [x(-90°)]. That is this rotation down to here. So I am now in a superposition state over here. The next line says that if v = 1, do a -180° rotation around the z-axis [z(-180°)]. That takes me around to there. Then if u = 1 again, do a +90° rotation around the x-axis. That will take me down to here, because the x-axis is pointing out of the page as you look at it.
The end result of all that is that if the u and v are 1, then I do all three of these things. So I have rotated from 0 eventually down to 1, which is indeed the product of 1 x 1. At the end of the computation I do a read-out, and if u and v were 1, I find that the q-bit is now in state 1, which does tell me the product.
What if u was 0? Then I would not do this first one or this fourth one; the only one which would get done would be this one, which is a rotation around the z-axis. But if I start here and do a rotation around the z-axis, nothing happens. I stay in state 0. Then 1 x 1 = 0, and that is the right answer. The other one I have to check is that if v is 0 but u is still 1, what happens is that I do the -90° rotation around x, but then I will do a +90° rotation around x at this point, and again end up back at 0 so that I get the right answer, that the product is 0 in that case.
The crucial thing to understand here is that, although during the computation I am in a superposition state, I have to arrange the computation so that at the end of it all I am guaranteed to be in one of these classical read-out states, either 0 or 1, so that when I make a measurement I get a definite answer. And that is what I want from my computation.
This was published last year by myself and some co-workers in the Journal of Quantum Information and Computation. It gives some idea about how rapidly this field is developing that there are now three journals devoted to the field of quantum information and computation.
Click on image for a larger version of figure 5
Not only did we do the theory for it, but some of those people and some other people did an experimental demonstration of this algorithm (figure 5). It was actually done using nuclear magnetic resonance. I do not want to go into the details of NMR ensemble quantum computation, but there are reasons why this is not exactly the same as the ideal quantum computation one would like. Basically, it is because you actually have a huge number of identically operating quantum computers in parallel, if you like each one you can only read out with very inefficiently, so you need the huge number in order to get enough signal so that you can see what is going on. But it demonstrates the principle, even if it is not a completely rigorous quantum computer.
This is very similar to the idea I talked about, of having an electron spin, but in this case it is actually a proton spin, because it is the nucleus of a hydrogen atom that is being our quantum computer here. The operations I talked about, the rotations in space, are done using transverse radiofrequency magnetic pulses. And the one last thing is that the read-out in this case is done using an antenna to detect the radio waves that the protons emit.
What this shows is the experimental results. You will just have to take my word for it basically this is a spectrum as we saw this morning, but a much, much simpler one, and just believe me that if the spectrum points up, then that indicates an upward pointing spin, and if it points down, that indicates a downward pointing spin. So these (figure 5) were the parameters which we put into the program. As you see, it works that you get an output of 0 for all the cases except when u and v are both 1, in which case you get the output of 1.
So basically that works as expected. It is published in Physical Review, if you are interested.
That is what you can do with a q-bit, but to do really interesting things what you need is a full-scale quantum computer. That is a much harder thing, because that means ideally you want a lot maybe of the order of 104 q-bits, all together and, more than that, each one individually has to be preparable in the state you want it to be prepared in, you have to be able to control each one individually, and you have to be able to measure each one individually. And also you have to be able to get them to interact with each other. So it is a tall order, but basically that is what you need.
Now a little bit about the maths of it. We talked about how I can write down the general q-bit state as a state like that. You might think that if I have got many q-bits that means I've got one of these [a single q-bit state] for each q-bit. But that is not the way it works. Basically, when you have a quantum computer and you have many q-bits together, you cannot write down the state for an individual q-bit. All you can do is say that you can write down a state for the entire computer, and the state for an individual q-bit does not exist at all, because you actually have what we call an 'entangled' state. All the q-bits are entangled, in the sense that it is only possible to write down a state for the entire computer, not for each individual q-bit.
What the entire state looks like is something like this: I have a probability amplitude for all these q-bits to be in state 0 times that state where they are all state 0, plus a probability amplitude when they are all 0 except for this one being in state 1, and there's the state, et cetera all the way up to the point where I have a probability amplitude for all the q-bits to be in state 1. And so I have this massive state here, which is a superposition of all possible classical states of the computer, and that is the sort of states which are going to be produced during the quantum computation. And again these things are called probability amplitudes, and I take the modulus squared of those in order to find out the probability, to read out the computer in a particular state, when the read-out happens at the end.
If I can do that, why would I want to do that? The reason is that they can be fast. Basically, this is the big motivation for wanting to do quantum computers.
There are two sorts of fast. There is exponentially fast, which is really good. There are a couple of things which have been pointed out that one can do exponentially faster on a quantum computer.
One is to simulate quantum systems. This was really where the whole field started off, when Feynman made the observation in 1958 that this should be possible, and this has lots of possible applications obviously in physics and in chemistry, and possibly even in biology, with a problem like protein folding. Essentially, molecules are quantum systems and it may be that for some subtle features we need to be able to model the quantum mechanics. A quantum computer would be ideal to do that.
The second thing, if this [simulating quantum systems] started the field, is what really set it off, set it going skywards: an algorithm by Peter Shor in 1994 for factoring. What he showed is that a quantum computer can factor very large numbers that is, find their two factors very fast, exponentially fast. You might think that sounds a bit boring, but you should know that the difficulty of finding the factors of a very large number is behind all of the secure data transmission on the Web. Every time you send an encrypted credit card number or whatever on the Web, that is relying on the fact that it is difficult to factor large numbers. So you could understand why security agencies would be very interested in having a quantum computer.
The second sort of fast you can get is quadratically fast, which is not as good as exponentially fast but is still pretty good. This was another algorithm which Lov Grover came up with in 1996 to show that quantum computers would be this much faster at searching for solutions to unstructured problems. That also possibly has lots of applications.
Click on image for a larger version of figure 6
You might ask why it is that a quantum computer can be powerful like this. It is basically related to the fact that, as I said before, you have a superposition of all possible classical states. Some physicists have even taken it so far as to say that what is really going on is that you are doing computations in parallel universes and you have got all these parallel states in common in the one computer.
If you think of things this way, it sounds as if it is going to be easy to make a quantum computer do anything. You have got parallel worlds; you should be able to do anything with it. But it is not that easy, because theoretically the trick is that, as I pointed out when I talked about my very simple algorithm, you have to make sure that at the end of your algorithm you end up in one, and only one, classical state. There is no point in ending up in this huge superposition, because then when you do your measurement to find out something, you just randomly get one of those possible worlds, and that does not take advantage of the whole superposition. So that is the theoretical difficulty.
I am going to give you my personal speculations, then, on where we might be heading with quantum computers. This is very difficult to guess, so what I used as a guide was to look at the past history of electronic computing. The beginning of that field was really, I would say, in 1906 when the first triode valve, which was the forerunner of the transistor, was invented. The first circuit using that came about 15 years later. It was not used for anything useful until about 1930 theoretical things there and general-purpose computers did not come till the '40s and '50s. In quantum computing we have already done entangling operations, which are the basic step in quantum computing, back in the 1970s. We have done what I would is roughly the equivalent of 'toy' quantum computations since about 1998.
So, just a guess, we may have a useful quantum computing device, something which would actually be technologically useful, by maybe 2015, but general-purpose quantum computers probably not till some time in the middle of this century. That is just my personal speculation.
That is the broad view of where we are heading, and I am happy to say that in Australia we are leading the way, in many ways. You will hear a lot more about the Centre for Quantum Computer Technology in the next talk, from Alex Hamilton. He is at UNSW, where they are doing the solid state experiment. There is also an optics experiment at the University of Queensland, which I could probably answer questions about if anyone is interested. Melbourne is a great support for the UNSW solid state effort. As I said, I am at Griffith University, which is one of the theory programs in the Centre.
I was supposed to talk about theoretical challenges, so very, very briefly I will say something about that. I would say that in this field really the biggest challenges are in experiment rather than theory, but there are still some big questions in the theory, such as: exactly what is it that makes quantum computers powerful? And a related question is: what other algorithms would be fast on a quantum computer? Then a more architecture one is: what would be the best architecture for a large-scale quantum computer, given that you have to include things like error correction and fault tolerance, and things like that? I think these are really areas where people in other fields can contribute, especially computer scientists and mathematicians for the first two, and possibly engineers and materials scientists in the ones related to architecture.
