Black Holes, Firewalls, and the Limits of Quantum Computers

thank you so much for coming you know I spent four of the most formative years of my life as a student here in Berkeley and it's always a very emotional for me to come back so so I called the talk yeah black holes firewalls and the limits of quantum computers black holes and firewalls were mostly just to get you in the building you know I'm you know I'll say something about them at the end you know quantum quantum computers when I do a Google image search for quantum computer that's one of the first things that comes up now you know I'm you know it'll become clear in this talk that I'm not an engineer I'm a theorist but I don't think that's what they look like I've been in enough lab tours that you know they they look a lot messier than that okay so and by the way you can find the slides and you know a bunch of sort of our articles that you know from technical to popular about many of the things I'll be talking about on my home page okay so my starting point here is you know not about quantum mechanics it's just about the limits of technology okay there are certain things that would be awesome to have again we never seem to see them first of all warp drive you know where is it I've been waiting since I was a kid okay secondly the perpetual motion machine you know the only real solution to our energy problems okay and then thirdly is what I'll call the uber computer okay and this is a machine that you know doesn't necessarily tell you the meaning of life or anything like that you know but it immediately answers any well posed mathematical question that you put to it okay so here we see it saying you know Goldbach's conjecture true next question you know what you know it's just saying you know yes every even number four or greater is the sum of two prime numbers right you know you know I think some people have the impression that this is already what computers are okay but you know we one of the the most basic things we teach in the theory of computing is that you know even the fastest computers today you know or are powerless against certain kinds of problems they have limitations there are certain problems like the halting problem you know to tell whether a given program will ever stop running which are proven to be unsolvable you know in that case by Alan Turing in the 1930s there are other programs as there other problems that computers can solve but only we think by using astronomical amounts of time okay so now um I'd like to make the observation that you know in the first two of these cases you know we can say something about why these technologies are not around you know which is more illuminating than just well you know the engineers ran out of money before they could build it or something like that okay we can connect this to you know fundamental principles of physics okay in the case of warp drive well you know those principles are those of a special relativity which tell us that if you could send the signal faster than light then in someone's frame of reference you're sending that signal backwards in time okay and then you know you've got to worry about well what happens if you go back in time and you kill your grandfather for therefore you're never born but therefore no one kills your grandfather therefore you are born and you know you know no one wants to worry about that stuff okay so you know the in the case of the perpetual motion machine you know of course what rules it out is the increase of entropy the second will of thermodynamics okay but what about the third case so you know are there principles of physics that you know tell us what computations we can and can't perform so you know that question is is sort of the starting point for me okay you know what this physics tell us about the limits of computers and if we understand those limits can they then feed back and tell us anything new about physics okay so I guess I'll take five minutes to give you a crash course on you know some of the basic concepts of you know the theory of computing yeah that's that's that that's all I should need for the talk okay so you know we we a computer scientists like to take sort of any concept or notion of what a computer could be and associate to it some inscrutable sequence of capital letters okay so you know the most these give gives us things called complexity classes which are sort of you know one of the the most basic objects that we study okay and the may be the sort of central complexity class is called P for polynomial time okay and you can think of it informally as you know the class of all the problems that are solvable efficiently by a standard digital computer like the one in your pocket okay you know I you know you formally you would say you know a Turing machine which is the mathematical model of what a computer is laid down by Alan Turing in 1936 but today it's you know it's easier just to say the thing that's in your pocket okay you know so what do we mean by efficiently well we have a sort of rough-and-ready criterion for that that it means solvable using a number of steps that grows at most like the size of a problem instance raised to some fixed power okay like you know the size of the problem square the size of the problem cubed okay and by the way by a problem we mean sort of you know an infinite collection of let's say yes or no questions okay so here would be an example right so this is this is a you know we could consider what's called the connectivity problem okay where I give you a description you know a map described somehow as a string of bits and I ask you you know is a given point connected to a given other one okay an instance of this problem which confronted me this past week is is it mathematically possible to get between Berkeley and Palo Alto you know what if there's traffic okay so you know this is a famous example of a problem that is solvable in the class P in fact there is a linear time algorithm you know which will get invoked anytime you use Google Maps basically okay so you know so this so this is something that is you know that we consider efficiently solvable same with you know multiplying numbers same with same same with sorting and you know most of the other things that a computer would do on a day to day basis okay yeah you know and people object to the definition by the way because if you had a an algorithm that took you know like the problem size raised to the million power time well that's formally polynomial but you wouldn't want to run that for you know any problem size larger than one okay but you know in practice that tends not to happen so you know so between friends we like to say you know polynomial means efficient and you know if there are exceptions to that then we deal with them when they come okay so so then the second important class is called NP non-deterministic polynomial time misses the class of problems for which well you know maybe they're not solvable by an efficient algorithm but at least you know if there is a solution then that solution can be efficiently checked you know you can be recognized when you're showing it okay so well one of the most famous examples of an NP problem is a factoring factoring numbers okay so you know if I want to phrase this as a yes-or-no question I could give you a large number like that one there and say you know does it have a prime factor that ends in seven okay well you know has anyone solved it yet okay so I think in this case the answer is yes but you know I made this slide a long time ago and if if the answer is no I'm not sure you know well you know so so you know so so so the thing to notice is that you know uh you know if someone has solved this problem then you know it's it's pretty easy at least with a computer to check their solution okay you know as it turns out this is not quite obvious but there are very fast algorithms that can tell you whether a number is composite or prime okay if it's composite they tell you nothing about what the divisors are okay but they but they do tell you if it's prime or not so you could you know give someone the you know divisors of this number a person could use their computer multiply them that's that's an easy operation check that you know they do multiply to this thing and also check that they're prime and then just check whether one of them ends and seven okay but if someone didn't tell you you know what the divisors were well you might spend quite a bit of time looking for them right and you know in fact many of you might know that the security of you know essentially all the cryptography that we use on the Internet today is based on the belief that factoring and a few closely related problems are hard okay for you know that there is not going to be any efficient algorithm to solve these problems you know solution is is much much easier to check than it is to find okay you know so anytime you see a little padlock icon on your web browser or an HTTP right you're you know you're your information like your credit card number is being protected by a credit card or a code that depends on the belief that this kind of problem is hard okay well we'll come back to that so so then you know a further crucial concept is np-hard problems these are problems that are sort of at least as hard as any problem in NP in the sense that if you had a magic box to solve them then you could use that magic box to solve any other end people okay well that's so you know we're definition not clear that there's any problems like that but there are there's oodles of them okay and then the np-complete problems are the np-hard problems which are also themselves in NP so those are sort of like the maximally hard problems whose solutions are still easy to check you know the maximally hard NP problems okay now a central discovery that you know in the early 1970s that you know really started you know theoretical computer science as sort of its own field was the discovery which was you know in which I was a which was really sort of which a central participant was the guy who introduced me just now a carp that not just one or two but many many many hundreds of the problems that people actually care about and actually want to solve happen to fall into this np-complete class okay a famous example being the problem you know I give you a map like this and I ask not what is the shortest path or is there a path from A to B but just is there a path that hits each vertex in this case exactly once okay in this case what's the answer anyone yeah yes it's easier to see when you color it okay okay so you may have heard the the literally million-dollar question of this field is you know whether P is equal to NP that is you know for every efficiently checkable problem is it also efficiently solvable okay this question has entered popular culture you know it's been on The Simpsons Futurama other TV shows and movies that are not as good it's you know it's also one of the seven clay problems for which you know you get a million dollar prize for a solution alongside the Riemann hypothesis the punker a conjecture which was actually solved by Perlman although he declined the prize and and for other problems okay now my personal opinion is that P versus NP is actually manifestly the most important of all these problems okay that it is the biggest problem in mathematics and my argument for that is simply well if P were equal to NP and if moreover the you know algorithm were really efficient in practice so you know not n to the 1 million or something like that well then that would ants I'll answer this question but it would also mean that we could answer the other 6 questions because we would simply program our computer to find the answers for us ok you know the problem like you know given a mathematical statement written in some formal language like that of set theory you know is there a formal proof of this statement with it most you know a given number of symbols like you know a million or a billion that is an NP problem so if P were equal to NP that would be an efficiently solvable problem ok so that that I I hope you know helps to underscore the enormity of what we're asking right if P were equal so I'm you know this meta mathematical importance was recognized early on by girdle you know incompleteness guy in a letter to John von Neumann where were you know in 1956 ok uh you know I mean if P were equal to NP that would also break essentially all of the cryptography that we use today everything except stuff like the one-time pad which you know doesn't depict rebuking which don't depend on mathematical assumptions ok so you know or are they equal or not you know I like to summarize it by saying that if we were physicists as opposed to math and CS people we would have simply declared P not equal to NP to be a law of nature ok and we would we would have we would have given our you know we would have said you know of course you know you know look we tried we looked for an algorithm is not there of course can't solve it right what what are you gonna do you know you've got you know a certain gigantic search space to to the end possibilities yeah maybe you can cut it down a little here thereby being clever but you know polynomial come on right and yeah we would have given ourselves Nobel Prizes for that discovery okay and you know and by the way if someone later proved that actually P equals NP well we just would have given ourselves more nobel prizes for for the laws overthrow okay so you know but but you know you know they're they're sort of you know one thing you learn in quantum computing it's an interdisciplinary field you know in different fields have different terminology so you know what the physicists call law we call a conjecture okay so yeah so okay so so this okay so um but you know even if we you know except that you know probably presumably you know P is not equal to NP you know and we hope someday to be able to prove such things but you know we seem a long way from that now you know one can then you know ask a further question okay P versus NP itself you know is a purely mathematical question right you know it has a you know whatever's the answer it has an answer right which is totally independent of whatever the laws of physics are right because you know it just ask you know is there at this touring machine or not okay so you know it doesn't even make sense to ask well is you know this quantum mechanics change the answer at a P versus NP no of course it doesn't okay but there there is then a further question you can ask which is well supposing P is not equal to NP is there any physical means at all to solve np-complete problems efficiently possibly a means that would exceed you know the capabilities of Turing machines right because a touring machine is just one particular mathematical idealization of what a computer is okay it's not obvious that the laws of physics you know restrict us to that kind of computer right maybe they let us do something else okay so so you know when we ask sort of what are the ultimate limits of of computers that we could actually build well then of course we're asking a question about physics and physics is going to enter the discussion okay so so you know they're you know you know the idea that the limits of what we can compute in the physical universe sort of coincide with the you know limits of a Turing machine is sometimes called the church touring thesis okay although it's not clear that church or touring themselves ever said that or believed that but you know it's sort of like you know well if they didn't say it they should have okay you know but then you know you you could make an even stronger belief which is that you know whatever is efficiently computable in the physical world should be efficiently computable you know in the sense of polynomial time by a Turing machine okay but now we're really sticking our necks out and we're really making a falsifiable empirical claim about nature right you know you know Nate you know nature doesn't have to listen to us you know you know you know or you know if we even you know if we enunciate it as a principle right nature might go and ignore that principle okay so so so it behooves us to ask you know what is there in nature that could conceivably challenge that you know extended Church touring thesis right what could a physical system look like that could you know possibly exceed the limits of a Turing machine okay so you know you probably all know where this is going you know given the title of the talk but you know before we get the quantum computers let's just briefly discuss a few other examples okay so there's an old proposal I like which is that you take two glass plates you put pegs between them and whatever pattern you want and you dip the resulting contraption into a tub of soapy water then you take it out and you look at the soap bubbles that form in between the pegs okay and bubbles like the sort of relaxed to their lowest energy state which in this case you know presumably means sort of minimizing the total length of bubble you know going in between these pegs but now you know if I if I ask you what's the minimum total length of line segments connecting a set of points in the plane where those line segments could also meet at intermediate points like these well this is called the minimum Steiner tree problem and this is a famous example of one of those np-hard problems okay so now we're faced with a puzzle which is basically you know how you know if this problem is np-hard well then how does nature solve it okay how does nature do this and you know is it possible that you know a tub of soapy water does what all of our super computers cannot do and that you know we could you know just have like you know so soap tubs you know to break all the cryptographic codes that you know over you know all of our enemies are using okay so well you know there was a discussion of this on the internet some you know years ago and you know and and and some people said well you know there's they're sort of no no reason for to you know to imagine that this will always work right because systems in nature like to relax to their lowest energy state they can often be modeled as doing that but you know they can get stuck they don't always succeed as an example if I put a rock on a crevice on a mountainside well it could reach a state of lower potential energy by rolling up first and then rolling down but it's rarely observed to do that okay so you know so why shouldn't be imagine that the same is true here that you would get stuck in a so-called local optimum all right well so then someone else came and said you know but this is just an academic computer scientist party-line you will repeat that you Pat yourselves on the back I bet not one of you has they've ever tried the experiment you have no idea what would happen all right oh I told you that I'm a theorist this led me to the one foray into experimental physics in my career where I I used to take this around and do demonstrations but it was just hell to get it through airport security so you know what what I found when I tried it is that indeed you know with four or five pegs or so you usually do get the minimum steiner trait and it's cool to watch you can try it at home so if you do I recommend using Plexiglas instead of glass so you don't cut your hands I asked how I know okay so but you know but then you know if you know when you scale up more say to six pegs seven pegs then it doesn't always find the optimal solution in fact sometimes you find a little cycle of bubble which is then like a proof that it can't be minimal okay so you know I didn't try every possible brand of soap but you know I I think you know I think we have some certainly some circumstantial evidence that nature is not solving np-complete problems by magic this way right you know and that means that may sound silly and yet every year or so you'll see in the popular press another headline about you know biological system that solves np-complete problems you know protein folding right you know nature just you know every cell of your body solves an np-complete problem every second but you know just letting the proteins fold into their lowest energy state okay I think that similar comments apply you know in that case you know with proteins well there was strong a selection pressure on them right if like one could in principle may create a an amino acid chain such that you know to fold it into its lowest energy state you would need to prove the Riemann hypothesis first right this is what np-hardness means okay but that would be a pretty bad protein right it wouldn't you know you know so so like proteins that get selected will tend to be ones that do fold reliably even then there are proteins that can miss fold get stuck in local optima prions the agent of mad cow disease are apparently an example of that okay so all right my second example is you know you know we you hear about quantum computers all the time but why not a relativity computer okay so the idea here would be quite simple you start your computer working on some hard problem then you leave your computer on earth new board a spaceship which in you accelerate to relativistic speed okay and then you decelerate you return to Earth okay back in Earth's reference frame you know billions of years have now elapsed okay civilization has collapsed actually you know in our timeline civilization probably collapses by 2019 or something but you know you know at any rate it's it's it's it's it certainly collapsed you know by then okay but you know if you can you know just sort of somehow dig your computer out of the rubble and it somehow can it still connect it to a power source then you can read out the answer to your hard problem okay's to me this just raises an immediate question which is why doesn't anyone try this I mean I mean you know if you're worried about all your friends being dead just bring them on this spaceship with you you know but you know so we're asking you know what is it in fundamental physics that would rule this out that would prevent you from getting orbit Rory computational speed ups in this sort of way so I think there's actually an interesting answer to that question okay and it has to do with the amount of energy that it would take to accelerate to you know relativistic speed to get the speed up okay so what you can calculate is that if you want it and say an exponential computational speed up this way then you would need to get exponentially close to the speed of light okay but to do that would require an exponential amount of energy okay so we've sort of just traded one exponential for a different one right and now you know where to imagine that before liftoff you know you spend like exponential time just fueling up your spaceship you know or something like you know well you know or where do you find all this fuel okay so you know it's a it's an example of how you know very very often you'll you'll see proposals for these sort of hyper computers you know that would exceed the limits of Turing machines but then on analysis they're just based on taking one aspect of the laws of physics in isolation and ignoring all the other aspects okay so that's a cost retail right we better not do that okay a second example along the same lines is what I like to call the Z no computer okay now this is simply a computer that would do its first step in one second the second step in half a second the third step in a quarter second fourth step in an eighth second and so on so that after two seconds it would have done infinitely many steps you know you could solve the whole thing problem that way okay but so so again why doesn't anyone try that okay well in this case thing you know in some sense there are people who try this right there are people who overclock their microprocessor all right they run it faster than you know it's supposed to okay but many of you might know the danger in doing that which is that if you run your processor too fast it will overheat it'll melt okay you know this is why computers have fans all right because you know you know again we can ask well but what is the fundamental physical limit here okay well you can imagine trying to run a microchip faster and faster and faster and faster clock rate as I want to run it faster to do that I will need more and more cooling you know I'll start you know wanting liquid nitrogen or liquid helium and some supercomputers used to actually use okay and you know and the more cooling I need the more energy that will cost you see once again energy okay and then once my computer is running fast enough I might as well just forget about the cooling system and talk about the energy that's inherent in the computation itself okay now um as far as current physics can say the fundamental limit here seems to occur if you were to run a computation at about 10 to the 43 Hertz okay it's ten to the forty three operations per second one step per Planck time okay now you could think of you know a toy model of such a computer as just a photon that's bouncing back and forth between two mirrors to count off time steps you know and when the mirrors would be one Planck length apart that it's 10 to the minus 33 centimeters okay now what's the problem with with a computer that runs that fast while the problem is but you know Planck's relation e equals H V okay such a photon would have so much energy concentrated in so small of a region that it would exceed what's called a Schwarzschild radius okay that's just a fancy way of saying that your computer collapses through a black hole okay which you know I've always liked this Nature's Way of telling you not to try something okay uh okay but what about quantum computing I mean you know we knew it was coming at some point those are supposed to be spin 1/2 particles although you know I don't think that's actually what they look like so all right so in order to tell you you know you know I mean I mean I mean I mean quantum computing you know like when you first hear about it it sounds you know roughly as crazy as there's other things that I just talked about okay and yet we know that there are experimental groups all over the world which are currently you know working very hard and you know spending significant money to try to actually build these things okay so you know what's the difference well you know the quantum computers are machines that would be do computation in a fundamentally different way by exploiting the rules of quantum mechanics okay which is something that's you know has been sort of the basic operating system for physics since the 1920s you know the thing that everything else sort of runs on is application programs okay except for you know general relativity there's some technical problems porting it to the OS okay but but well what is this operating system right you know and like what what is there that's in it of sort of comparable enormity to the church you know to the extended church-turing thesis that that the one could actually challenge the other okay so I have to spend a couple slides telling you about what this quantum mechanics say you know you you might think that would take more than a couple slides you know I mean physicists you know think over generations we succeeded in convincing people that quantum mechanics is somehow complicated or hard you know and it's true that if you want to know you know the ground states of you know interesting molecules and so forth yeah you know that's complicated okay but not being a physicist and not being bound by their rules I can let you in on a secret which is that quantum mechanics is actually incredibly simple once you take the physics out of it okay now the way that I think of quantum mechanics is that it's a certain generalization of the rules of probability themselves okay so you know you know probability you know you could talk about well you know a you know a 30% chance that you know wildfires will consume the Bay Area or whatever but you know you would never talk about a negative 30% chance right let alone you know a you know an AI percent you know square root of minus 1% chance okay that would just be nonsense okay but quantum mechanics fundamentally is a generalization of the rules of probability where to each possible way that things could be or that we could find things on looking at them we assign a number called an amplitude okay and amplitudes are a little like probabilities in fact we use them to calculate the probability that we'll see a system in one state or another when we do look at it okay but these amplitudes are not themselves probabilities they can be positive or negative and in fact they can even be complex numbers okay so you know a Richard Fineman used to say that everything in quantum mechanics just boils down to one experiment the double-slit experiment so we might as well talk about it you know the double slit experiment is the thing where I take photons I shoot them one by one and a screen with two slits in it and I look at where they end up on a second screen and what you know and and and and where they end up is random right with the same initial conditions photon can sometimes land one spot and sometimes another you know people go on and on about well you know this is God playing dice Einstein couldn't accept it but well that is not the strange part about quantum mechanics right if it was just probability who cares okay we could you know invent you know thirty theories for that before breakfast okay the the strange part is the way that the probabilities have to be calculated okay because what you find is that there are certain dark spots on the second screen where the photon never seems to appear or almost never okay and yet if I close off one of the slits then the photon can appear in those places okay so by decreasing the number of ways for something to happen I can increase the chance that it happens okay also if I just look at the photon to try to see which slit it's going through then I don't see this interference pattern anymore right everybody you know I I hasten to add it doesn't have to be a conscious person looking at it or anything like that if if the if the photon is interacting in any way with its external environment so that the information about which slit it goes through leaks out you know into a recording device into the air molecules in the room into anything then you don't see the interference okay interference is something that photons you know and other particles like to enjoy in private okay so so okay the way that quantum mechanics explains this is by saying that well the probability of an event in quantum mechanics is calculated as the squared absolute value of its amplitude okay and the amplitude could be a sum of of contributions you know complex numbers representing the contributions from all the different ways that that thing could have happened okay and so the result is that you know there could be certain spots on the second screen where the photon could arrive there through the first slit with a positive amplitude I or through the second slit with a negative amplitude okay if that happens the nose two contributions can as we say interfere destructively and cancel each other out with the result being that the total amplitude is zero and the photon is never found there okay I close off one of the slits and then the amplitude is positive or negative so that I can see it there okay so physicists describe this by saying you know that the state of the world is a vector right it's a vector of complex numbers okay and they have this strange notation that they like to use for vectors okay that's all this is right so the simplest type of quantum system is a bit which could be in a zero state or a one state but because it's quantum mechanics it can also have an amplitude to be in zero and an amplitude to be in one okay it can be in what we call a superposition of the two states okay a bit that can be in a superposition of zero and one we call a quantum bit or a qubit okay so the state of a qubit is written as a 0 plus B 1 where a and B are just complex numbers called amplitudes and they satisfy this relation here ok and this relation is sort of there to ensure that if you look at the qubit you know you ask it whether it's 0 or 1 well then you know you know it tells you that at 0 with this probability and it tells you that it's 1 with that probability well then those probabilities better add up to 1 ok that's why that's there so so the possible states of one qubit you know if we looked at real amplitudes only for simplicity would simply define a circle like you know a squared plus B squared equals 1 ok 0 could be you know we could take to be the horizontal Direction 1 we could take as the vertical direction and then we can have any possible intermediate like this equal superposition state of 0 plus 1 over square root of 2 okay now you know if I take a superposition like that and I look at it I force it to make up its mind about what it wants to be sort of snaps to one possibility or the other okay and you know by the way whichever choice it makes it sticks with it okay so you know if it tells you that it's one and you look again it says you know what do you want for me I'm one okay all right so so now I can start to tell you what is quantum computing okay so so now the the key observation here is imagine I have not just one qubit but a thousand cubits or a million cubits okay physically maybe that's like a thousand particles that could all be each each of which could be spinning one way or spinning the opposite way right oh you know I don't I don't you know it does it doesn't actually matter for our purposes you know what physically gives rise to this qubit okay you know any quantum system that has two distinguishable States okay but now the point is if I have a thousand you know say of these qubits the rules of quantum mechanics tell me that to dispute if those qubits are interacting with each other in some arbitrary way then to describe their state I actually need to assign one amplitude for every possible configuration of all thousands of those bits that means two to the thousand power amplitudes okay so you know if you were wanted to write them down you know that's you know way more amplitudes than there are atoms in the observable universe okay and yet you know quantum mechanics has been telling us for ninety years that you know to just to maintain the state of a thousand measly particles nature off to the side somewhere has to have some scratch paper with two to the thousand complex numbers and every time something happens to those particles it has to cross off those numbers and replace them with a new two to the thousand numbers okay that is an immense amount of work for nature to be going to you know and you know I say you know and and and it's astounding that I sort of it it took so long for this to sink in that quantum mechanics you know was always saying this okay now to be fair chemists and physicists did you know know this for a while they knew it mostly as a practical problem okay what they what they knew was that you know if you're trying to simulate quantum mechanics on a classical computer then the time needed for the simulation seems to increase exponentially with the number of particles that you're trying to simulate okay and so you know they invented all kinds of approximate methods and heuristics over the decades for getting around that problem you know Nobel prizes were awarded for some of the most important ones you know and you know in fact it's a pretty decent fraction of supercomputer time today is used for this problem the problem of trying to simulate quantum mechanics you know with large numbers of interacting particles you know in order to learn things about chemistry and material science and so forth okay so it was not until the early 80s that a few physicists like Richard Fineman and David Deutsch started asking well why can't we turn that computational lemon into lemonade okay so you know if you know quantum systems are so hard to simulate with today's computers then why don't we build computers that themselves take advantage of superposition and interference of amplitudes you know and you know entanglement between different qubits okay you know of course they then face the question supposing we built such a computer well what would it be good for okay you know at the time they only really had one answer to that question which is such a computer would be good for simulating quantum mechanics right now you know it sounds funny but actually you know if you know when we do start to get practical quantum computers I predict that quantum simulation is still the most important application that we know ok it has you know potential uses from you know understanding reaction rates and you know industrially important processes you know fertilizer production you know all kinds of things designing draw that bind to a receptor in the right way you know maybe you know understanding high-temperature superconductivity designing higher efficiency solar cells okay and furthermore you know we are you know pretty confident that a quantum computer really would help for these sorts of problems right it's you know you know it you know it what you know because a general quantum simulator is exactly what you know this is sort of its its home territory right but now if you know the surprise the big you know non-trivial discovery that was made in the 1990s is that a quantum computer can also sometimes be used to solve even classical problems faster than we know how to solve them with a classical computer okay and the most famous example of that is Shor's algorithm okay sure sure famous algorithm actually solves the problem of factoring an integer which I talked about earlier in polynomial time with a quantum computer okay so what sure showed is you know and related problems like discrete logarithms elliptic curve problems and so forth okay with the upshot being that you know if you build a universal quantum computers then the assumptions that underlie modern public key cryptography are no longer true you can break essentially all the systems that we use in practice now okay this made many more people interested in quantum computing than had previously been you know I should mention that there are theoretical public key cryptosystems that seem to be resistant even against quantum attack such as lattice space crypto systems okay it's just that those are not widely deployed yet okay so you know of course people always ask well so so where are we with building these things you know I'm proud to report that you know after some you know probably a couple billion dollars of investment in this field and more than 20 years of effort the experimentalist have succeeded in factoring 21 into 3 times 7 using Shor's algorithm with high statistical confidence I am I'm optimistic the 35 is on the horizon you know I mean you know you know scaling this up is hard actually you know you know there are more impressive things that are you know that are likely to happen in a few years you know this is this this joke slide is even a little bit outdated now okay but you know there's a huge practical problems in actually building this which were understood from the beginning and you know the the central thing is the unwanted interaction between the qubits and their external environment okay the phenomenon called decoherence okay basically you know when a quantum computation is being run yeah you know it is as if the entire universe is you know or the entire rest of what you know what say your lab is constantly trying to peek in and see what's happening just because of the natural you know noise and interactions between the computer and the external world okay but you know you look in on a quantum computer prematurely well I'm told that it's like you know baking a souffle where you open the oven before it's ready this thing collapses okay same with quantum states right you you know to get a quantum computation to work you would need to you know have the qubits incredibly well isolated from their external environment but then at the same time interacting with each other and not only doing that but doing it in a very precisely prescribed way okay so you know that's so hard that there were you know fit a good number of physicists in the 90s who said this can never happen okay this is really impossible the you know a huge discovery that you know changed many people's money changed most people's minds was called quantum fault-tolerance which told us that we don't actually have to have to get the decoherence down to zero we merely have to make it very small and then there are very clever error correcting codes that can take care of the rest okay you know so qubits are sort of just now you know get you're just like a few years ago have gotten good enough to apply these error correcting codes when you look at just a few of them in isolation okay the problem is as I try to scale up and have lots and lots of qubits then the noise rate goes back up because of interactions between the qubits okay but you know people are working on it and you know Google right now has a 22 qubit system which seems to be working pretty well they say that within a year they plan to upgrade that to 49 qubits okay you know when when I heard John Martinez of Google say that I asked him to clarify if he meant the calendar year or the academic year he said he said the calendar year but it will take a lot longer to test it and calibrate it and so on you know he said oh you know by December 31st we'll have something I don't tell you it will work ok so ok but now you know a crucial point to understand ok is that fact the factoring problem is neither known or believed to be one of these np-complete ones ok there are excellent theoretical reasons why it should not be np-complete ok and you know to you know if you read almost any popular article that's ever been written on this subject right it will say something about it that sounds really good and it's totally wrong ok we'll say look you know the way a quantum computer works is just that it tries every possible answer in a different parallel universe you know it's like yeah well you know journalists love that because you know it's like yeah anyone can understand why that would make it faster ok but then you know the puzzle is well if it's that simple then you know why did it take people all these decades to figure to figure it out ok so so you know the the resolution is that with a quantum computer you know it is easy to create a superposition over all the possible solutions to your problem right that you know you can you can do very easily but for it to be useful well at some point you've got to measure the thing you've got to get an answer out ok and if I just take an equal superposition over all answers and I measure it not having done anything else then the rules of quantum mechanics say all I'm gonna get out will be a random answer yeah you know if I just wanted a random answer well I could have picked one myself with a lot less trouble okay so for that reason the entire hope of getting a speed advantage from a quantum computer is to rely on the way that these amplitudes behave differently from ordinary probabilities and in particular the fact that being complex numbers they can interfere with each other okay so the idea with every quantum algorithm is to choreograph things in such a way that for each wrong answer some of the paths leading there have positive amplitudes and others have negative amplitudes so on the whole they cancel each other out whereas the pairs that lead to the right answer should all be in phase with each other say all positive or all negative if I could arrange that then when I measure I'll see the right answer with a good probability you know which you know if I even if I have a 70% chance of getting the right answer that's great just run it several times you know take the majority vote okay so um um so so so you know a huge question that people asked at the beginning of this field was well could there be a an efficient quantum algorithm to solve not merely factoring but all the NP problems right here to solve the np-complete problems okay well uh you know I I hope no one will be shocked if I reveal that the answer is we don't know okay you know you know can we prove that quantum computers can't solve these problems well of course we can't prove that because we can't even prove that classical computers can't do it okay that's the P versus NP problem okay but you know we can say is that at the least if there were fast quantum algorithm to solve the np-complete problems then it would have to look totally different from Shor's algorithm or from any of the other quantum algorithms that we know ok so quantum speed-up seemed to you know be more specialized this this whole thing of choreographing the interfere rent pattern it works for problems that have a special kind of structure to them you know in the case of factoring sure really took heavy advantage of this sort of number theory and group Theory structure and the problem to sort of choreograph a set of operations which we call the quantum Fourier transform that gives you the right kind of interference pattern we don't know how to do that for np-complete problems ok and in fact we have an important result about it so my my advisor at Berkeley Oh mesh Raza Ronnie along with the Bennet Bernstein and Brassard proved in the 90s that if I just imagine say an abstract space of 2 to the N possible solutions and if the only thing I knew how to do was you know for each solution just check whether it's valid or not valid right and I'm searching for a valid solution ok call this black box search right well then you know with a classical computer it's pretty obvious that well you know I'm gonna have to open about 2 to the N boxes to find this little right you know what else am I gonna do alright you know but now imagine that I can open many different boxes in superposition ok so with some amplitude I can open the first box with some other amplitude I can open the second box and so on and then I get a superposition of answers then I can you know transform that state some more I can make another superpose query to the boxes ok in that case um there is an amazing algorithm called Grover's algorithm which lets me find a solution with only about the square root of the number of steps that I would have needed classically ok so in this case that means 2 to the N over 2 steps okay but what Bandit at all proved actually they proved it before Grover's algorithm was even known to exist ok is that that's the best you can do ok so even with a quantum computer you know ok yeah well instead of 2 to the thousand steps you can do it with 2 to the 500 steps you know and that's awesome but 2 to the 500 still a big number right you're not turning an exponential into a polynomial you're you know you're somewhat expanding the the size of the problems that you could handle okay so as far as you know we can see that you know this may be like the best kind of quantum speed-up that you can plausibly hope for for solving np-complete problems with a quantum computer okay but we still don't know right what we do know is that if there is a fast quantum algorithm to solve np-complete problems which you know again would be like the holy grail of computer science you know and you know you know 500 times more important than you know then merely factoring and those things okay well then somehow it would have to exploit the structure of the problems just as a classical algorithm would have to okay so then the question becomes well is there are there any quantum algorithms out there that would try to exploit the structure of np-complete problems so there is one very important one which is called the adiabatic algorithm okay proposed by Ed for hey my other former colleagues at MIT like 17 years ago and I don't want to go into the details of how this algorithm works but if you've seen like local search methods you know things that just sort of store it at some random place and makes a bunch of local improvements do some hill climbing it's basically you know it's basically like a quantum version of local search a quantum analog of simulated annealing in particular okay so now these are not algorithms you know that you know typically we can prove will work but you know you can try them out and see what happens okay and so some of you might know that there is a company which was founded you know just around trying to build special-purpose devices to run a sort of noisy version of this quantum adiabatic algorithm okay the company's called d-wave you know they were on the cover of Time magazine and they were you know they've gotten a huge amount of attention for it they actually have sold a few of these devices one to Google one to Lockheed Martin I think I think a couple of others you know their latest model has about 2,000 cubits you know superconducting qubits right and you may wonder well why have I been talking about you know 20 cubits or 50 cubits if d-wave already has 2,000 cubits right and they're already selling it you know to customers and you know well the issue is there's actually two issues okay first there's sort of the engineering issue that you know that these qubits just don't seem to maintain their quantum coherence very well okay they you know they're sort of like they're a technology that is optimized for you know getting as many qubits as you can as fast as you can rather than for making the qubits as good as you can okay and you know many of us were sort of doubtful that you know that with qubits that are that noisy that you that you would see a speed-up you know that you that you could you know even if there were one to be had and the second issue is a more theoretical one you know the issue is well you're trying you know D waves entire approach is based on trying to solve np-complete problems as I mentioned these problems seem pretty hard okay and you know it's not clear that even if you could run this adiabatic algorithm perfectly that you really would see much speed up for these problems okay may you know probably you can see a Grover type of speed-up you know a square-root speed-up maybe even that you know is not certain because you got to compare against classical algorithms that themselves are very clever and that could be much better than brute force right but you know are you gonna see an exponential speed-up you know we don't know right you know so there was a hope about it that you know the this adiabatic algorithm could take advantage of a phenomenon called quantum tunneling which basically says like if I have like if I'm trying to you know find the minimum in some potential but I have a spike sort of along the way that's blocking me well then we're a classical particle might get stuck over here for exponential time you know a quantum particle can actually get over the spike you know in a much more efficiently in polynomial time right this is a very important you know like this effect is central to why you know the hydrogen atoms in the Sun are able to fuse into helium for example okay they have to get over a barrier like that okay but uh so you know so you know we could exploit that algorithmically but then you know when we're trying to solve real-world optimization problems well is the fitness landscape actually going to look like that well you know who knows and if it does look like that maybe you could design a better classical algorithm you know that would take advantage of it right so so so people studied this for a while and what what they found is that the amount of time that you have to run this adiabatic algorithm for if I want to end with the solution to my np-complete problem is determined by something called the minimum eigen value gap of my Hamiltonian don't worry what those words mean okay basically I see you know I have a graph with two things and the you know and I look at the closest that they ever get to each other and however close they get I need to run my algorithm for the inverse of that amount of time okay and so then people you know you know you know for he and my other physicist friends looked at this and they said well you know well you know why are they gonna magically get super duper close to each other right you know and that's the only thing that would cause the algorithm to fail okay but then people studied it on you know they looked at it on hard instances of np-complete problems you know satisfiability you know things like that and lo and behold they found that this gap does become does seem to become exponentially small right you know it was hard to to tell from the numerix you know and there was a big debate about it for a few years okay but far he has told me the wonderful story that he wants you know went to an expert in condensed matter physics because you know for their own reasons they have decades of experience calculating these spectral gaps okay and he asked well based on your experience with sim systems do you think that you know in our adiabatic algorithm that this spectral gap will will decrease polynomial e or exponentially as a function of the number of particles okay and this expert thought about it a bit and he said I think it will decrease exponentially okay now that was not the answer that far he wanted to hear so he said why what's the physical reason for it okay and the expert thought about it some more and he said well it's because otherwise your algorithm would work okay so so so you know I mean you know after you've seen enough examples of nature sort of just failing to solve np-complete problems in polynomial time you know you might be tempted to you know just want to take that as a fundamental principle or you know postulate alongside no superluminal signaling and the second war and so forth and you might wonder you know supposing I accepted that postulate what else could I then use it to explain okay so that's you know that that's a direction that that interests me a lot okay so you know I'd say it remains unclear whether you really get a practical speed up this way over the best classical algorithms we might not know for sure until we can really build quantum computers and test them out all right so a lot of my work you know in the last you know six years or so has been about this very unfortunately named goal of quantum supremacy which reasonably just means getting a clear quantum speed-up not necessarily for something useful but just for something hard okay and so my student alex arkhipov and I had an early proposal for how to do that which was called boson sampling okay what we suggested was like a very very rudimentary type of quantum computer where you just generate a bunch of photons you send them through a network of beam splitters and then you measure where they end up okay now what is that useful for oh I have no idea okay but we were able to give evidence that you sample from some probability distribution we're sampling from that distribution class classically would be exponentially hard okay and so people have actually started implementing this so far they've done it with about six photons you know if you want to outperform a classical computer you probably need at least like forty photons or something okay so that's that that's a challenge but in the meantime I'm also mentioned this group at Google which is planning very soon to have a forty nine qubit chip you know now as far as we can tell a forty nine qubit chip is probably still not useful for anything okay but you know if we just put a bunch of up quantum operations on that and we use it the sample from some distribution over forty nine bit strings then we have pretty good reason to think that well that is a distribution that if you want to sample it with a classical computer you know you'll need something like two to the forty nine steps you know maybe maybe a little bit better but you know that's about the best that we know okay and so you know so it's it's not so hard that a classical computer can't do it you know that's important because you want the classical computer to be able to check the results and you know we only know how to do that but you know using this exponential time operation okay but you know it's hard enough that you could clearly see that this chip would be solving something faster than the fastest classical computer that we have on earth okay so I think that that will be if and when that's achieved you know possibly within the next couple of years that will be a real milestone for this field okay now I had stuff about the firewalls and the black holes because I am out of time what I suggest to do is to just go to my conclusion you can see you know what well look at these graphics that I made okay you know I have a Schrodinger's cat I've got a wormhole alright so what I suggest that I do is that I just go to my conclusion and then you know if anyone wants to ask me a question about firewalls or something then I can tell you about it okay so my summary is that quantum computers are the most powerful kind of computer allow by the currently known laws of physics there is a realistic prospect of building them you know you know what I like to say is that if you can build a quantum computer and it works you know that's the conservative possibility right I mean you know when people come to my blog let's say and they're you know they're you they say you know this can never be done I say well you know you know in some sense I hope you're right right because that would be a revolution in physics right but you know my you know I think for me the number one application of building a quantum computer is actually just to prove those people wrong okay all the all the other applications are just icing to me okay so you know but what we've seen is that you know even a quantum computer contrary to what the popular articles say you know is not this magic Oracle that solves everything okay even they have limits and the limits are sort of so strange and sort of cut across you know things you know in such a non-trivial way I like to think no science fiction writer would have had the imagination to invent this right it's you know people usually go wrong by trying to round it down to something that a science fiction writer could have thought of okay okay but you know the limits of quantum computers have explanatory power you know they can explain why spectral gaps behave the way they do and the part of the talk that I haven't gotten to I could tell you why they might even help to protect the geometry of space-time all right so let me stop there for now so thank you Scott why do you say that these limits might help protect the geometries oh you really want to know all right all right anyone wants to leave I won't be offended all right all right so now all right there's yeah there's you've seen this guy you know so so you know you know I know sort of never when I was here at Berkeley doing my thesis about quantum computing I have never imagined that it was you know it was gonna have anything to do with with black holes like you know I just you know read about them and you know popular science the same as anyone else okay there was a remarkable connection that's really been made within the last five years or so between quantum information and quantum gravity okay including a famously this black hole information puzzle so this was a central problem in modern physics which was raised by Hawking in the 70s and is basically you know well the the rules of quantum mechanics are you know except for measurement which let's just forget about measurement for now okay but if I just have a bunch of qubits and they're revolving on their own then everything they do is time reversible okay so you know I can run things backwards as well as forwards and information is never destroyed okay but a black hole seems to violate that right I if I you know take some bits or I take an encyclopedia or something I throw it into a black hole well and you know general relativity tells me it's gone right it's sitting the singularity is never getting out okay so you know this seems the you know the universe seems to have an information dumpster okay you know which then the question is how do we reconcile that with quantum mechanics okay well Hawking also famously oh yeah this is might does my animation right so Hawking also famously discovered in the 70s that black holes radiate okay so you know is there not completely black you know actually photons slowly come out you know for a black hole the mass of the Sun it may take about 10 to the 67 years for this to happen but you know eventually the black hole will go away okay but the trouble is you know his calculation also said that the radiation that comes out we know it suggested it would be completely thermal completely uncorrelated with whatever came in so the puzzle remains okay and there's a bunch of possibilities you know none of them very appealing right if it stays there forever we violate quantum mechanics you know it comes out okay well you know you know we could imagine that somehow by some yet unknown physics the information that's dropped in what it would would would would come out in some scrambled form in the Hawking radiation okay but then that leads to a problem as well because from the perspective of someone who was inside the black hole well the information doesn't come out right it just you know hits the singularity and go splat okay so so now you seem to have two copies of the information and well why is that a problem well it's because of I have a quantum state then there's a basic principle of quantum mechanics called the no-cloning theorem right which says that there is no way to actually make a copy of an unknown quantum state okay this is you know this is the central principle by the way that enables quantum cryptography and other possible applications such as quantum money which would be physically impossible to counterfeit okay that you know but but I digress that's a different talk okay so so then people in the 90s started developing a view called black hole complementarity which says that actually you know you should not even think of the interior of the black hole as being a different quantum state than what was you know available to you outside of the black hole you know including on its event horizon okay you should just think of them as different regan coatings of the same quantum state and then jumping into a black hole you know is just a really weird way of measuring the same quantum information that you could have measured had you stayed outside the black hole all right well you know that seemed the you know sort of resolve the problems for a while I was always confused about it and then what happened in 2012 is that a bunch of physicists decided that they were confused about it - okay and so then you know this led to a you know a big you know a huge sort of discussion in theoretical physics which you know you know even spilled into the New York Times and so on you may have seen something about it it was called the firewall paradox okay so what is this was my um Harry Merrill polchinski and solely in 2012 and this was sort of a challenge to this black hole complementarity and so it was a thought experiment where you know the idea is we would form a black hole we would have complete knowledge of the you know the entire quantum state of all the in the in fowling matter you know it's a thought experiment okay and you know we let it form a black hole then we let the black hole mostly but not completely evaporate okay you know which takes you know ten to the sixty seven years or so we'll assume we have a really good grant okay and and then you know as the Hawking radiation comes out we route all of it into our quantum computer okay we just treat it as a collection of qubits we process it in a certain way and then we make some measurement which will tell us that a you know that a hawking photon is just now coming out of the black hole is entangled with all the photons that previously came out okay and and then we jump into the black hole okay for the sake of science and and we look at what's happened and now there's a principle of quantum mechanics called monogamy of entanglement it says that if I find a qubit and it was already entangled with a second qubit then it can't also be entangled with a third qubit okay but now there's a more principles in quantum field theory that say as I fall into the black hole you know yeah you know here's Alice it's always Alice some reason okay you know she she jumps into the black hole and now you know it's and now because these two qubits were entangled you know the the the qubit that's just now coming out of the black hole cannot also be entangled with a qubit that's just inside the black hole okay but Hawking says if you want to see a smooth space-time at the event horizon then you need that entanglement that straddles the event horizon right and you know it sounds crazy but in quantum fee theory space-time is built up out of sort of a huge amount of local entanglement if you don't have that entanglement you've got no smooth space-time which basically just means space and time and at the event horizon okay and Alice encounters well you know an end of space-time which was called the firewall okay now why is that a problem well Alice was supposed to encounter an end of space-time but only at the singularity right and this is saying she would hit it hit one much earlier that she can't even cross the event horizon okay so then the question is what gives right you know and and but you know what made this a big deal is that it's not just a philosophical problem right it's like if you claim to have an answer then you have to say well if Alice did this then what would happen okay so so there have been a whole bunch of you know suggested you know resolution there have been hundreds of papers about this paradox okay but you know one of the you know maybe the the most interesting things that's been said about it was said by Daniel Harlow and Patrick Hayden and what they did is they said well yeah it's true that you know black hole complementarity says that you know the you know it implies that that that Alice could do some quantum computation on the Hawking radiation that would show her that there is this entanglement you know and therefore you know create a breakdown of quantum field theory at the event horizon okay but let's now ask well how hard of a computation which you have to do okay and what they did is they argued that the computation seems like one that would be exponentially hard even for a quantum computer okay so you know take time exponential in the number of Hawking photons that she's dealing with okay so what do we mean there we'd mean you know she can't do it in a mere ten to the sixty seven years she can't even make a dent in it in that time she instead needs two to the ten to the sixty seven years okay so by the time that she had done this the black hole would have already evaporated anyway so maybe there's nothing to jump into so maybe there's no problem okay so that was you know that was kind of what they said and you know now you can you know have your own view on you know how house weather weather that satisfies you or not but you know when they the thing that blew me away was that when they came to the crucial point why is this an exponentially hard problem they drew on sort of all the work that we had done over the last 20 years in understanding what are the limits of quantum computers and in particular you know their argument sort of relied usually on this thing that I did at my PhD thesis here at Berkeley okay which is the thing you know the sort of best-known thing that I showed in my in my PhD was had to do with the ability of quantum computers to find collisions and something called cryptographic hash functions okay so you know a hash function is like a function that map's you know some string to a much shorter string and they're super useful in cryptography but the key property that they're supposed to have is that it has to be intractable to find two different inputs that map to the same output okay and and so what I showed is basically that you know if I have just a black ash function that's a complete black box just like that setting that we talked about earlier with Grover's algorithm that in that case even a quantum computer will need exponentially many queries to find a collision in that hash function right it turns out that like if let's say my hash function has n possible outputs then classically finding a collision takes about square root of n steps right Y square root of n well because of the birthday paradox you've heard of that right that's why by like if there's 23 people in a room there's even odds that two of them share a birthday what matters is the number of pairs of people okay now it turns out that a quantum computer could find a collision in such a hash function using only cube root event steps you know I'm not making this up okay you know and you get cube root of n by sort of combining the birthday paradox with Grover's algorithm in a clever way okay so what our work showed in 2002 is that actually even with a quantum computer cube root of n is the best that you can do okay now what Harlow and Haydn argued was that you know actually you can sort of take this collision problem is finding collisions in a hash function and you can embed it into the problem of decoding the Hawking radiation that is coming out of a black hole in such a way as to create a firewall okay you know you can sort of reduce one to the other okay so that you know if you had a generic efficient algorithm for decoding as Hawking radiation then it would you know it would let you find collisions and hash functions which you know we think is hard for even for a quantum computer okay so now recently I strengthened their result show that you know performing this computation is actually you know actually doesn't you know is it's hard eve even even without using my PhD thesis ok so you know in fact if you could do it then you can invert lets go you know basically any one-way function using a quantum computer ok which you know which would let you break not just public key cryptosystems like RSA and so forth but even any private key cryptosystem you know that's based on any mathematical assumption ok so you know so whether it solves the problem or not the problem indeed seems to be hard you know so you know and and and in what's happened in the last 5 years is that cut you know computational complexity has been feeding back into fundamental physics in all sorts of ways so I have a recent result you know about well you know you've heard of the schrödinger's cat experiment right and and you know people wonder if I had you know if I maintain a cat in a superposition of alive and dead states well you know like like well you know what does it mean do I have to talk about two universes that you know are both somehow existing you know which is the many-worlds philosophy ok and what what my result says is that if I had the technological ability to you know make a Schrodinger cat I then measure it and confirm that it was in this superposed cat state then I would necessarily also have the ability to bring a dead cat back to life okay in the sense that the quantum circuit complexity of one task is basically the same as you know the as the size of the circuit that I would need for the other task okay so you know so in the dead state is not clear you know we should even call the cat dead any al I mean it's thinking I was alive it's dead it's live it's right so I mean you know in fact the schrödinger's cat experiment involves way less animal cruelty than isn't you know normally suppose okay okay and then you know the craziest one to me is that since you know about four years ago you know there's um you know been a whole bunch of well people who call themselves string theorists you know led by Lenny Susskind at Stanford who now like they don't talk about strings anymore okay they are speaking in a language of qubits and quantum circuits and entanglement you know and and this is now what they talk about okay and a lot of the reason for that has to do with what's called the ATSC ft correspondence which is like one of the most important things to have come out of string theory and it's sort of a holographic duality which relates physical theories in different numbers of dimensions and this is sort of one of the best handles that anyone has on what a quantum theory of gravity can look like okay but the crazy thing that people found was that when you like I can take some situation like involving a general relativity like for example a wormhole between two different regions of space and you know general relativity says that a wormhole will just continue expanding forever okay it'll just get longer and longer and in fact the standard wormhole and relativity is not reversible right I go in and I can't get out the other end cuz it's you know so now you know like like what else do we know that sort of somehow a connection between two things and yet doesn't let you send a signal from one to the other well quantum entanglement okay and so what's been what's become increasingly clear these two things are extremely related to each other in particular when you take these holographic dualities if I take a wormhole and I look at what it corresponds to unlike this boundary theory this quantum field theory that lives on the boundary then I find an entangled quantum state okay and as the wormhole gets longer and longer the only thing that is changing about that quantum state that would sort of track the length of the wormhole seems to be that this quantum state gets more and more and more complicated okay but you know what do you mean complicated how can you quantify it well Susskind proposal is that what we mean is literally the quantum circuit complexity of that state meaning like the number of you know operations that I would need to prepare that state using a quantum computer okay so because of this connection circuit complexity is now as now started sort of playing the role of like a fundamental quantity in physics you know at least you know in the context of ATS CFD so I don't know where all of this is going but you know I sort of have no choice but to you know you know when they come to me as you know you know well you know what do I know about wormholes or black holes okay but you know if they want me to use me as a computer science consultants you know and they can boil down their question to something about quantum computing well you know we're here to serve alright so that so thank you for asking that was the answer there [Applause]

Channel: Simons Institute

Views: 8,828

Keywords: Simons Institute, theoretical computer science, UC Berkeley, theoretically speaking, quantum computing

Id: cstKRACrMQY

Length: 84min 2sec (5042 seconds)

Published: Fri Oct 27 2017