>>What's the problem with quantum then? OK, I think we probably... Probably we should talk about the opportunity I mean what, what's the idea? Why would we want to build a quantum computer? We discovered... the first observation was that it's actually quite difficult to simulate a quantum system. and this could be illustrated with this famous double slit experiment where you send electrons, or photons or whatever through two slits, and then you notice that you get this interference pattern. So it gets dark and light, dark and light which we can understand if we think of electrons or photons as waves 'cause the waves interfere with each other but at the same time we know that they are actually particles because we never have half a photon, we never have half an electron so the question is, if each time we send only one electron through these slits Which way does it go? Does it go left, or right? and now you think you're clever, you put some detectors on the slits You have to 'trick' nature, find out where it goes and as soon as you do this they behave like particles, there's no interference pattern any more. and that's called a measaurement, so all quantum systems er they have this dual behaviour, they behave like waves as long as you don't look at them and as soon as you look at them, they behave like particles behaviour where this electron goes through, seems to be going through both holes at the same time it's really doing something in parallel the one explanation is, er, one understanding is Everett's er, multiple worlds interpretation that there are parallel universes and in one universe the electron goes through this and the other one through this and you don't determine which universe you are unless you look at it, and then you are either in this one or in this one OK, now, quantum computing tries to exploit this very weird nature of quantum physics and using the mathematical models we have from physics we can develop new computational paradigm, new... programming language so to say, quantum programming and in this language we can exploit this quantum parallelism to have certain computations run faster it's not completely easy because everything you do has to be reversible, every computation you do you also have to be able to do backwards so everything needs to be symmetric >>Is it a Qubit? Yes, a Qubit is a bit, and it has an amplitude, it can be somewhere between zero and one, yes? and a Qubit, which is maybe like, in the middle. is like this electron going through the one slit and the other slit and we don't know which one so while the Qubit is not observed it's at the same time zero and one, so to say. and all its interaction are based on this "it's two things at the same time," like Schrödinger's cat famously (alive and dead) so as long as you don't open the box the Qubit is in some super-position so to say it can be just one but it can be also in a super-position and that's the interesting case but the rule is, you're not allowed to look at it while you do this so it has to be unobserved because once you observe it you determine which universe you are then this multiple universe idea disappears, this paralellism disappears >>The magic is let out of the box? The magic yeah, once you look at it the magic is out you have to close your eyes for as long as you.... then at the end you can look because you want to know what the outcome is and then you measure but not inbetween There are some, very famous algorithms which work on a quantum computer faster than on any, known, classical there's no known classical solution a famous problem is the problem of factoring a number so for example 15 can be factored at 3 and 5 and this problem is actually quite important for cryptography. The RSA algorithm is based on this idea that you have the product of two prime numbers but you don't tell anybody what the prime numbers are so, it's called a one-way function so it's actually surprising, it's easy, computationally to find out whether a number is a prime number but it's hard to factor a number it's hard (this by the way is not proven) nobody knows a way to factor a number efficiently on a classical computer but since Shor (The Shor Algorithm) we know on a hypothetical quantum computer, that using this quantum paralellism there is a clever way to do this it uses a certain number theoretic function which has a period (repeats itself) and using this super-position of Qubits you can actually, with a good probability measure, this period, the repetition, and from this period you can then, find a factor that's quite clever, yeah. So it seems that quantum computing can... can be much much faster than classical computing now here's the problem we haven't yet been able to build a quantum computer of reasonable size, where there's anything interesting happening and why is this a problem? why is it difficult? the challenge is to do computations without looking at it while you have... Your Qubits are represented by some physical object some ions or whatever some particles, yeah and you want these particles to interact with each other to do the quantum computation But, they should not interact with the rest of the universe So you basically have to make them interact with each other, without touching them and, that could be possible. It may be "an engineering problem" as one says But we don't know whether whether it's actually possible in principle I think there is a mistake to extrapolate, we know in small systems we have this quantum behaviour, and quantum er, theory gives us very, very good predictions on how these systems behave but we don't know whether it actually scales up. Whether I mean, there is this problem that you have involuntary measurements, or involuntary observations it's called decoherence so when this system loses its quantum magic and becomes classical and what we don't know is whether we can actually avoid decoherence in a large quantum system because in the end, in physics it's always like this: "You should never assume an outcome of an experiment before you have done it" so far, nobody has done this experiment which shows that large scale quantum computing is actually possible so it may be that there is some hidden law we haven't yet been able to test ya? which basically says "Once you do too much quantum parallelism, nature... ...shakes its head and says no that's getting too complicated I'm not doing this, I'm going to put some decoherence in otherwise it gets too complicated it could be, I'm not saying it is like this but we basically don't know So I think research in quantum computing in this area is very interesting, very exciting, because we have actually an open question and either way the answer will be interesting The answer is either, OK we can build a quantum computer, we can do all these cool algorithms, great. Or the answer could be, Actually it's impossible we have discovered a new law of nature which actually says that nature in the end is classical and this quantum stuff is only on a small scale which would be very very exciting as well Either way it's exciting, we should find out, but we shouldn't assume now that we know the answer without having done the experiment >>There's supposed to be some kind of computer that's been built Yeah >>Is it that we don't know if it is doing what we guess? Yes there's this D-Wave and there are other projects, but as far as I know we don't know yet whether really get quantum paralellism out of it there are all sorts of claims and counter-claims and I don't think it has been decided yet >>Is it possible to simulate a quantum computer on a classical computer? Yes indeed, er, I've actually developed a library doing exactly this, called Quantum IO Monad Yes you can do this, the problem is, to simulate this quantum paralellism you have to really go through all the possibilities and you have an overhead exponential overhead so yes you can simulate it, but it's inefficient >>So could you do a very simple sum or something like that on this? Yes we did this algorithm, the Shor algorithm to factor a number and to factor 15 and it turns out, the answer is either 3 or 5... [laugh] >>Is that something we could link to, people could look at or is it err.... yes, yes >>Cool well we'll put that in the description if anybody is interested in it it's actually implemented in the programming language Haskell, the functional language I hope you can still download the code!
