Scott Aaronson: What is a Quantum Computer? | AI Podcast Clips

as you said mono computing at least in the 1990s was a profound story at the intersection of computer science physics engineering math and philosophy so the there's this broad and deep aspect to quantum computing that represents more than just the quantum computer yes but can we start at the very basics what is quantum computing yeah so it's a proposal for a new type of computation I would say a new way to harness nature to do computation that is based on the principles of quantum mechanics and now the principles of quantum mechanics have been in place since 1926 you know they haven't changed you know what's new is you know how we want to use them ok so what does quantum mechanics say about the world you know the the physicists I think over the generations you know convinced people that that is an unbelievably complicated question and you know just give up on trying to understand it I can let you in not not being a physicist I can let you in on a secret which is that it becomes a lot simpler if you do what we do in quantum information theory and sort of take the physics out of it so the way that we think about quantum mechanics is sort of as a generalization of the rules of probability themselves so you know you might say there's a you know there was a 30% chance that it was going to snow today or something you would never say that there was a negative 30% chance right that would be nonsense much less would you say that there was a you know an I percent chance you know square root of minus 1% chance now the central discovery that sort of quantum mechanics made is that fundamentally the world is described by you know the D sort of let's say the possibilities for you know what a system could be doing are described using numbers called amplitudes ok which are like probabilities in some ways but they are not probabilities they can be positive for one thing they can be positive or negative in fact they can even be complex numbers ok and if you've heard of a quantum superposition this just means the some state of affairs where you assign an amplitude one of these complex numbers to every possible configuration that you could see assist them in on measuring it so for example you might say that an electron has some amplitude for being here and some other amplitude for being there right now if you look to see where it is you will localize it right you will sort of force the amplitudes to could be converted into probabilities that happens by taking their squared absolute value okay and then and and then you know you can say either the electron will be here or it will be there and you know knowing the amplitudes you can predict the price the probabilities that it will that you'll see each possible outcome okay but while a system is isolated from the whole rest of the universe the rest of its environment the amplitudes can change in time by rules that are different from the the normal rules of probability and that are you know alien to our everyday experience so any time anyone ever tells you anything about the weirdness of the quantum world you know or assuming that they're not lying to you right they are telling you you know and yet another consequence of nature being described by these amplitudes so most famously what amplitudes can do is that they can interfere with each other okay so in the famous double slit experiment what happens is that you shoot a particle like an electron let's say at a screen with two slits in it and you find that they're you know on a second screen now there are certain places where that electron will never end up you know after it passes through the first screen and yet if I close off one of the slits then the electron can't appear in that place okay so by so by decreasing the number of paths that the electron could take to get somewhere you can increase the chance that it gets there okay now how is that possible well it's because we you know as we would say now the electron has a superposition state okay it has some amplitude for reaching this point by going through the first slit and has some other amplitude for reaching it by going through the second slit but now if one amplitude is positive and the other one is negative then note you know I have to add them all up right I have to add the amplitudes for every path that the electron could have taken to reach this point and those amplitudes if they're pointing in different directions they can cancel each other out that would mean the total amplitude is zero and the thing never happens at all I close off one of the possibilities then the amplitude is positive or its negative and the other thing can happen okay so that is sort of the one trick of quantum mechanics and now I can tell you what a quantum computer is okay a quantum computer is a computer that tries to exploit you know these exactly these phenomena superposition amplitudes and interference in order to solve certain problems much faster than we know how to solve them otherwise so as the basic building block of a quantum computer is what we call a quantum bit or a qubit that just means a bit that has some amplitude for being zero and some other amplitude for being one so it's a superposition of zero in one states right but now the key point is that if I've got let's say a thousand cubits the rules of quantum mechanics are completely unequivocal that I do not just need one amp but you know I don't just need amplitudes for each qubit separately okay in general I need an amplitude for every possible setting of all thousand of those bits okay so that what that means is two to the 1000 power amplitudes okay if I if I had to write those down lets or let's say in the memory of a conventional computer if I had to write down two to the 1,000 complex numbers that would not fit within the entire observable universe okay and yet you know quantum mechanics is unequivocal that if these qubits can all interact with each other and in some sense I need to do the 1,000 parameters you know amplitudes to describe what is going on now know now I can tell you know where all the popular articles you know about I'm computing go off the rails is that they say you know they they sort of sort of say what I just said and then they say oh so the way a quantum computer works is just by trying every possible answer in parallel okay you know you know that that sounds too good to be true and unfortunately it kind of is too good to be true that the problem is I could make a superposition over every possible answer to my problem you know even if there were two to the one thousand of them right I can I can easily do that the trouble is for a computer to be useful you've got at some point you've got to look at it and see and see an output okay and if I just measure a superposition over every possible answer then the rules of quantum mechanics tell me that all I'll see will be a random answer you know if I just wanted a random answer well I could have picked one myself with a lot less trouble right so the entire trick with quantum computing with every algorithm for a quantum computer is that you try to choreograph a pattern of interference of amplitudes and you try to do it so that for each wrong answer some of the paths leading to that wrong answer have positive amplitudes and others have negative amplitudes so on the whole they cancel each other out okay whereas all the paths leading to the right answer should reinforce each other you know should have amplitudes pointing the same direction so the design of algorithms in the space is the choreography of the interferences precisely that's precisely what it would take a brief step back and when you mentioned information yes so in which part of this beautiful picture that you've painted is information contained oh well information is that the core of everything that we've been talking about right I mean the bit is you know the basic unit of information since you know called Shannon's paper in 1948 you know and you know of course you know people had the concept even before that you know he popularized the name right but I mean but a bit at zero or one that's right basically that's right and what we would say is that the basic unit of quantum information is the qubit is you know the object any object that can be maintained in us manipulated in a superposition of zero in one states now you know sometimes people ask well but-but-but what is a qubit physically right and there are all these different you know uh proposals that are being pursued in parallel for how you implement qubits there is you know superconducting quantum computing that was in the news recently because of Google's the quantum supremacy experiment right where you would have some little coils where a current can flow through them in two different energy states one representing a zero another representing the one and if you cool these coils to just slightly above absolute zero like a hundredth of a degree then they super conduct and then the current can actually be in a superposition of the two different states so that's one kind of qubit another kind would be you know just in an individual atomic nucleus it has a spin it could be spinning clockwise it could be spinning counterclockwise or it could be in a superposition of the two spin States that is another qubit but she's just like in the classical world right you could be a virtuoso programmer without having any idea of what a transistor is right or how the bits are physically represented inside the Machine even that the machine uses electricity right you just care about the logic it's sort of the same with quantum computing right qubits could be realized by many many different quantum systems yet all of those systems will lead to the same logic you know the logic of qubits and and how you know how you measure them how you change them over time and so you know that the subject of you know how qubits behave and what you can do with qubits that is quantum information so just a linger on that short so does the physical design implementation of a qubit hmm does not does not interfere with the that next level of abstraction that you can program over it so it truly is the idea of it is is the a is it okay well to be honest with you today they do interfere with each other that's because the all the quantum computers we can build they are very noisy right and so sort of the the the you know the qubits are very far from from perfect and so the lower level sort of does affect the higher levels and we sort of have to think about all of them at once okay but eventually where we hope to get is to what are called error corrected quantum computers where the qubits really do behave like perfect abstract qubits for as long as we want them to and in that future you know the you know which you know a future that we can already suit or sort of prove theorems about or think about today but in that future the the logic of it really does become decoupled from the hardware so if noise is currently like the biggest problem for quantum computing and then the dream is error-correcting Monica yes can you just maybe describe what does it mean for there to be noise in the system absolutely so yes so the problem is even a little more specific than noise so that the fundamental problem if you're trying to actually build a quantum computer you know of any appreciable size is something called decoherence okay and this was recognized from the very beginning you know when people first started thinking about this in the 1990s now what decoherence means is sort of unwanted interaction between you know your qubits you know the state of your quantum computer and the external environment okay and why is that such a problem why I said talked before about how you know when you measure a quantum system so let's say if I measure a qubit that's in a superposition of 0 and 1 States to ask it you know are you zero or are you one well now I force it to make up its mind right and now probabilistically it chooses one or the other and now you know it's no longer a superposition there's no longer amplitudes there's just there's some probability that I get a zero and there's some that I get a one and now the the the the the trouble is that it doesn't have to be me who's looking guy here in fact it doesn't have to be any conscious entity any kind of interaction with the external world that leaks out the information about whether this cubit was a 0 or a 1 serve that causes the 0 ness or the oneness of the cubit to be recorded in you know the radiation in the room in the molecules of the air in the wires that are connected to my device any of that as soon as the information leaks out it is as if that qubit has been measured ok it is you know the the the state has now collapsed you know another way to say it is that it's become entangled with its environment ok but you know from the perspective of someone who's just looking at this qubit it is as though it has lost its quantum state and so what this means is that if I want to do a quantum computation I have to keep the qubits sort of fanatically well isolated from their environment but then at the same time they can't be perfectly isolated because I need to tell them what to do I need to make them interact with each other for one thing and not only that but in a precisely choreographed way ok and you know that is such a staggering problem right how do i isolate these qubits from the whole universe but then also tell them exactly what to do I mean you know there were distinguished physicists and computer scientists in the 90s who said this is fundamentally impossible you know the laws of physics will just never let you control qubits to the degree of accuracy that you're talking about now what changed the views of most of us was a profound discovery in the mid to late 90s which was called the theory of quantum error correction and quantum fault tolerance ok and the upshot of that theory is that if I want to build a reliable quantum computer and scale it up to you know an arbitrary number of as many qubits as I want you know in doing as much on them as I want I do not actually have to get the cube it's perfectly isolated from their environment it is enough to get them really really really well isolated ok and even if every qubit is sort of leaking you know it state into the environment at some rate as long as that rate is low enough I can sort of encode the information that I care about in very clever ways across the collective states of multiple qubits okay in such a way that even if you know a small percentage of my qubits leak well I'm constantly monitoring them to see if that week happened I can detect it and I can correct it I can recover the information I care about from the remaining qubits okay and so you know you can build a reliable quantum computer even out of unreliable parts right now the the in some sense you know that discovery is what set the engineering agenda for quantum computing research from the 1990s until the present okay the goal has been you know engineer qubits that are not perfectly reliable but reliable enough that you can then use these error correcting codes to have them simulate qubits that are even more reliable than they are regarded the error correction becomes a net win rather than a net loss right and then once you reach that sort of crossover point then you know your simulated qubits could in turn simulate qubits that are even more reliable and so on until you've just you know effectively you have arbitrarily reliable cubans so long story short we are not at that break-even point yet we're a hell of a lot closer than we were when people started doing this in the 90s like orders of magnitude closer but the key ingredient there is the more qubits the butter because well the more qubits the larger the computation you can do right I mean I mean a qubit Tsar what constitute the memory of your quantum computer right it also for the sorry for the error correcting mechanism yes so so so the way I would say it is that error correction imposes an overhead in the number of qubits and that is actually one of the biggest practical problems with building a scalable quantum computer if you look at the error correcting codes at least the ones that we know about today and you look at you know what would it take to actually use a quantum computer to you know a i'm hack your credit card number which is you know maybe you know the most famous application people talk about right let's say two-factor huge numbers and thereby break the RSA cryptosystem well what what that would take would be thousands of several thousand logical qubits but now with the known error correcting codes each of those logical qubits would need to be encoded itself using thousands of physical qubits so at that point you're talking about millions of physical qubits and in some sense that is the reason why quantum computers are not breaking cryptography already it's because of this these immense overheads involved so that overhead is additive or multiplicative I mean it's like you take the number of logical qubits that you need in your abstract quantum circuit you multiply it by a thousand or so so you know there's a lot of work on you know inventing better trying to invent better error correcting codes okay that is the situation right now in the mean time we are now in what physicist John Prescott called the noisy intermediate scale quantum or NIST era and this is the era you can think of it as sort of like the vacuum you know we're now entering the very early vacuum tube era of quantum computers the quantum computer analog of the transistor has not been invented yet right that would be like true error correction right where you know we are not or something else that would achieve the same effect right we are not there yet and but but but where we are now let's say as of a few months ago you know as of Google's announcement of quantum supremacy you know we are now finally at the point where even with a non error corrected quantum computer with you know these noisy devices we can do something that is hard for classical computers to simulate okay so we can eke out some advantage now we'll we in this noisy era be able to do something beyond what a classical computer can do that is also useful to someone that we still don't know people are going to be racing over the next decade to try to do that by people I mean Google IBM you know a bunch of startup companies or you know a player's apps yeah and in research labs and governments and yeah you just mentioned a million things well backtrack for a sec yeah sure sure so we're in these vacuum tube days yes just entering and I'm just entering Wow okay so yeah how do we escape the vacuum so how do we get to how to get to where we are now with the CPU is this a fundamental engineering challenge is there is there breakthroughs in on the physics side they're needed on the computer science side what Oh is there an an is it a financial issue we're a much larger just sheer investment and excitement is new so you know those are excellent questions oh my god well no no my my my guess would be all of the above yeah I mean my my guess you know I mean I mean you know you could say fundamentally it is an engineering issue right the theory has been in place since the 90s you know at least you know you know this is what you know error correction what you know would look like you know we we do not have the hardware that is at that level but at the same time you know so you could just you know try to power through you know maybe even like you know if someone spent a trillion dollars on some quantum computing Manhattan Project right then conceivably they could just you know build a an error corrected quantum computer as it was envisioned back in the 90s right I think the more plausible thing to happen is that there will be further theoretical breakthroughs and there will be further insights that will cut down the cost of doing this you

Channel: Lex Fridman

Views: 49,797

Rating: 4.9362245 out of 5

Keywords: scott aaronson, artificial intelligence, ai, ai podcast, artificial intelligence podcast, lex clips, lex fridman, lex podcast, lex mit, lex ai, mit ai, ai podcast clips, ai clips

Id: nK9pzRevsHQ

Length: 21min 55sec (1315 seconds)

Published: Tue Feb 18 2020