Quantum Computing 'Magic' - Computerphile

Key Takeaways

what's the problem with Quantum that okay I think before we talk about problem 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's actually quite difficult to simulate a Quantum system and this could be Illustrated with this famous double slit experiment yeah where you send electrons or photons over 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 you think of electrons or photons as waves because the waves interfere with each other but at the same time we know that they're 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 yeah yeah I have to trick nature yeah find out where it goes and as soon as you do this they behave like particles there's no interference pattern anymore and that's called a measurement so so the all Quantum systems uh they have this dual Behavior 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 Behavior where where this electron goes through seems to be going through both holes at the the same time it's really doing something in parallel right so so one explanation is uh or one understanding is aver uh multiple worlds interpretation that they like parallel universes and in one Universe it Con goes with this and the other one through this and you don't determine in which Universe you are unless you look at it and then you're either in this one or in this one okay now Quantum Computing tries to exploit this very weird nature of quantum physics and using the mathematical models we have from physics we we can develop new computational paradigm new programming language so to say Quantum programming and in this language we can 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 has to be symmetric is it a cubit yes the Cubit is a bit and it has a amplitude it it can be somewhere between zero and one yeah and a cubit which is maybe like in the middle is like this electron going through the one slit and the other slit and we do no wi one so while the Cubit is not observed it's at the same 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 Shing has cat famously life and dead yeah so as long as you don't open the box the cubid is in some superposition so to say it can be just 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 this multiple Universe idea disappears a paradism disappears yeah the magic is let out the magic yeah once you look at it the magic is out you you have to like you have to close your eyes as long as you qu computer then in the end you can look because you want to know what the outcome is and then you measure but not in between there are some very famous algorithms uh which work on a quantum computer faster than on any known classical or there's new known classical solution a famous problem is the problem of factoring a number so for example 15 can be factored at three or five and this problem is actually quite important for cryptography the RSA algorithm is based on this idea that you have a product of two prime numbers but you don't tell anybody what the prime numbers are yeah so it's it's called a oneway function so it's actually surprising it's easy computationally to find out whether number is a prime number but it's hard to factor a number yeah so it's hard saying this this by the way it's not proven nobody knows a way to factor a number efficiently on a classical computer but since sh the sh algorithm we know on a hypothetical quantum computer using this Quantum parallelism there is a clever way to do this it uses a a certain number theoretic function which has a period repeats itself yeah and using this qu this the super position of cubits you can actually with a good probability measure this 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 um can be much much faster than classical Computing now here's here's here's the the problem we haven't yet been able to build a quantum computer of a reasonable size where there's anything interesting happening and why is this a problem why is this difficult the challenge is to do computations without looking at it yeah so while you you have you cubage were represented by some physical object some uh 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 yeah so you visually have to make them interact with each other without touching them and that could be possible it may be an engineering problem as as as one says yeah but we don't know whether whether it's actually possible in principle uh I think there is a is a is a mistake to extrapolate we know in in small systems we have this Quantum behavior and and qu uh Theory gives us very very good predictions of how these systems behave but we don't know whether it actually scales up yeah whether I mean there's this this problem that you have a involuntary measurements so involuntary observations it's called decoherence so then 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 once you 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 to test yeah which basically says once you do too much Quantum parallelism nature shakes its head and say no that's getting too complicated I'm not doing this I'm going to do put some decoherence in otherwise it gets too complicated so so it could be I'm not saying is like this but we basically don't know so I still I think research in 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 yeah the answer is either okay yeah we can build a Quantom computer we can do all these cool algorithms great or the answer could be could be actually it's impossible if we have discovered a new law of nature yeah which actually says that nature in the end is classical and and and and this Quantum stuff is only on a small scale which would be very very exciting as well yeah either way it's exciting we should find out but we shouldn't assume now that we know already the answer without having done the experiment there's supposed to be some kind of computer that's being built is it that we don't know if it's actually doing what we guess yes there's this dve and there are other projects but as far as I know we don't know yet whether we really get Quantum Paralis out of out of it I mean 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 uh I've actually developed a library doing exactly this called Quantum I onet um yes you can do this the problem is that you to simulate this Quantum parallelism you have to really go through all uh the possibilities and you have an overhead exponential overhead so yes you can simulate it but it's inefficient so do could you do a very simple sum or something like that on this yeah no we did we did this uh algorithm the sh algorithm uh to factor numbers that you can Factor 15 and turns out the answer is either three or five but is that something we could link to people could look at or is it uh yeah yes okay cool we'll put that in the description if anybody is interested in it it's actually implemented in the programming language hll as a functional language and uh I hope you can still download the code