Quantum Computing: A Primer



hello this is Frank Chen from the a 16 CD land research team one of the ways that I think about my job is that my team and I are off scouting the future we're trying to understand what the big breakthrough is right around the corner our that will turn into great startups great products for you and me and one of the things that we've found is around quantum computing so today I'd like to give the scouts report on what's happening in this fascinating field of computer science material science mathematics physics and it's mind-blowing so let's get started so you know what I love I love it when politicians teach computer science it's a real Revenge of the Nerds moment for me to see world leaders talking about the big impact that computer science is going to have on our society and so let's watch the Prime Minister of Canada Justin Trudeau work some magic this was from a speech that he gave in April 2016 at the Perimeter Institute for Theoretical Physics in Waterloo and it's safe to say he won the Internet that day perfectly normal computers work don't interrupt it when you walk out of here you will know more some of you will know far less about quantum computing but most of you normal computers work taking of this power going through a wire or not 1 or 0 they're binary system what quantum states allow for is much more complex information to be encoded into a single disk regular computer bit is either 1 or 0 on or off a quantum state can be much more complex than that because as we know things can be both particle and wave at the same time and the uncertainty or important state allows us to devote more information into a much smaller computer so that's what's exciting about quantum computing [Applause] so wasn't that great that speech reminded me a little of when President Obama visited Google in January of 2008 and Eric Schmidt asked him what the most efficient way to sort a million 32-bit integers was so if you missed that go look it up on YouTube another fun moment when political leaders are teaching computer science now if you listen to the prime minister he implied that what we were trying to do with quantum computers was make smaller computers and while he didn't say anything technically inaccurate I think that misses the point a little so we're not really trying to make smaller computers so what are we trying to do with quantum computers so understand that let's go back to beginnings so I'm going to pick up the story with this fine-looking fellow his name happens to be richard fineman most physicists would consider him one of the top 10 most influential physicists of all time he helped design the atomic bomb at the Manhattan Project he laid down standard notation for how quantum interactions work and turned out to be a great Bongo drummer you want to look that up on YouTube and oh by the way he was on the Commission that figured out why the space shuttle Challenger exploded so Richard had a bigger brain than most people and he was fascinated by the physics of very very small objects so think of these objects as atoms or electrons or photons and what happens at this very small small tiny scale is that nature gets weird and so because nature gets weird what does every quantum physicist want to try to understand the nature of nature at this scale well what every quantum physicist wants is a particle accelerator what a particle accelerator does is lets the quantum physicists run experiments about subatomic and atomic scale objects it turns out we have one right in our backyard so our offices at a 16 Z are in Menlo Park right on the tip of the Stanford campus and in our backyard literally you will see the rooftop of the Stanford Linear Accelerator which is one of these ginormous devices designed to accelerate atomic and subatomic particles and collide them into each other and this is the way that we run physics experiments at this scale here you see a picture of an even bigger accelerator this one's actually round and not linear this is the Large Hadron Collider operated by CERN just outside of Geneva Switzerland the Large Hadron Collider is 27 kilometers around and that makes it the world's biggest machine there is no machine bigger than this so what is mankind doing with the biggest machine that it's ever made it's doing quantum physics experiments so obviously we can't build many of these machines they're incredibly expensive to build and to operate they are the ultimate not in my backyard project in fact it took a while to find the site for the LHC as the community calls it and so if you can't build a lot of these machines what's your consolation prize as a physicist so if you don't get a particle accelerator for your birthday what do you get well what you get is simulation time on a supercomputer and so much of the experimentation that happens today on quantum physics happens inside supercomputers so if you don't get to actually run an experiment on the Large Hadron Collider or at the Stanford Linear Accelerator and you can imagine the queue is very long for the experiments that want to be run what you do instead is you simulate the interactions of these particles in a supercomputer in fact if you go out east from our office eventually you will run into the Lawrence Livermore Berkeley labs and this is the bulk of what they do they are simulating the effects of what would happen if we detonated nuclear weapons to see if our nuclear weapons will continue to work and to improve their efficacy so the United States doesn't actually explode nuclear devices anymore we signed the comprehensive test-ban treaty and so all of the work that we do now is in simulation but there's a problem with simulating quantum mechanics and let me try to give you the intuition behind the problem the key insight that richard fineman had was that quantum mechanics is just way too complicated to simulate using traditional computers so I'll give you a concrete example let's say we wanted to simulate the state of a thousand hydrogen atoms and in particular we wanted to simulate the state of a thousand of the electrons in a hydrogen atom now the hydrogen atom is one of the simplest we've got we've got one proton we've got an electron and if we wanted to simulate the up or down state of the electron and we wanted to do that for a thousand of these electrons we would need a computer that could represent two to the Italian States so you could have the possibility that all of the electrons are spinning down you had the possibility that all thousand were spinning up and you have all the possible combinations which works out to two to one thousands so even with this very relatively simple example we would need a computer that could represent more states to the 1,000 then there are atoms in the known universe so think about that for a while which is no computer can actually store that skate but the weird thing is somehow nature seems to be doing these calculations by itself somehow it's keeping the state represented in a way that leads to consistent quantum mechanical behavior and so richard feynman's insight was a nature seems to be doing these calculations can we somehow hitch a ride on the quantum mechanical properties of these atoms and get nature to do calculations that we want to do as opposed to calculations nature seems to be doing to keep nature working so that's the fundamental insight behind the quantum computer so to boil it down quantum computers rely on properties or quirks in quantum physics and the goal of building a quantum computer is to be able to do calculations of a unique sort and I'll describe that in a little more detail as we go along so we're trying to hitch a ride on nature to perform computations that using a traditional computer we just couldn't do or would take an incredibly long time so to go back to justin trudeau where he kind of implied we're trying to build smaller computers that's not what we're really trying to do what we're really trying to do is build quantum computers that can solve a class of mathematical problems that we couldn't solve with traditional computers or that we could only solve with way big amounts of memory and would take a long long long long time so how do quantum computers work so to understand how quantum computers work first we need to understand how traditional computers work so traditional computers work basically as Justin Trudeau explained correctly using transistors and these transistors can either be an on or off state just like your light switch originally we made these transistors out of vacuum tubes but eventually the geniuses at Bell Labs figured out how to create transistors out of semiconductors so we have this physical property of a semiconductor which it can be conducting electricity or not and we're going to declare that the on or off state and then we marry that up with logical gates that can perform operations and in the case of modern computers we're performing boolean algebra operations so not and/or the knot of one is zero the end of one and zero is zero and basically if you extrapolate from these two building blocks the transistor which includes on or off state these logical operations that are performing boolean algebra applications that DES leads directly to the smart phone that's sitting in your pocket so all of traditional computing basically is on a linear path straight down these two fundamental building blocks so the fundamental physical property again that we're taking advantage of is a transistor that is either conducting electricity or not and the logical operations were performing our boolean algebra operations contrast with quantum computers we're using a different part of nature and in particular we're either using atoms or photons or electrons let's lay aside the implementation detail of what we're using for now and let's sort of try to understand the what of what we're doing so in contrast to traditional computing bits where a transistor represents an on or off state what we have with quantum computers is a quantum bit so when observed the quantum bit behaves exactly like a traditional bit which is to say it can be 0 or 1 so it can be an electron in up or down state it can be an electron that's negatively charged or not but a crazy quantum mechanics property is that when it's not observed this qubit is actually representing the probability that it's 0 or 1 so for those of you who remember Schrodinger's cat your physics teacher told you that inside this box is a cat and it is either alive or dead and when you pop open the lid of the box the cat will definitely be alive or definitely be dead but if you close the lid the cat is in some indeterminate state it is a probability somewhere between alive and dead and this was one of the weird quantum mechanical properties of various very small product goals like atoms or electrons we're going to take advantage of this by having the qubit and the probability that it's either 0 or 1 to encode information and so the way to think of it without getting into the math is think of the qubit as representing an arrow or a vector so this vector has a direction and it has a magnitude right so picture of the arrow is pointing in a direction that's its direction and it has a length that's the magnitude of the arrow and so fundamentally the qubit represents this arrow rather than an on or off state and then the analogue to the operations were performing so instead of performing boolean algebra operations in quantum computers what we're using is a set of quantum gates and they implement quantum operations and the way to think about this is as linear algebra operations so for those of you that remember your linear algebra you have a vector think of it as an arrow with the direction in it at length we apply a linear algebra Reiter on it and that fundamentally changes the arrow it might change its direction it might change its magnitude but basically think of it as an arrow goes in to a quantum operation and an arrow comes out just a different arrow but mathematically related to the arrow that came in so the fundamental physical property that we're going to take advantage of is a quantum mechanical property rather than an electrical conductivity property and then the operations were performing aren't boolean algebra operations they are linear algebra applications so that's what's happening at the core of quantum computers let me put this together by describing how a quantum computer would solve a problem and how that's different than a traditional computer and let's use the so-called phonebook problem so the phonebook problem is this you're asked to find a particular phone number but you're given a phone book where the phone numbers are stored by let's say last name and so if you're trying to find a specific phone number with a traditional computer what you would do is look at the first entry and say hey is this the phone number I'm looking for if not go on to the second entry is this the phone number I'm looking for if not go on to the third entry and so on and so forth and if you wanted to guarantee that the phone number existed or didn't exist in this big phonebook you'd have to iterate through all of the entries there is no mathematical shortcut that you can take there's no algorithm in other words that would get you more efficiency than iterating through all of the entries in the phonebook and if you had a very large phonebook this could end up taking a long time in contrast with a quantum algorithm solving this problem and in this particular case the quantum algorithm was designed by love grover working at that labs at the time it's going to take advantage of quantum mechanical properties to solve this problem much much much faster than iterating through all the entries so let's see how that works so remember how I said that qubits can be thought of as vectors which is the representing information that's in the shape of an arrow with a direction and a magnitude what quantum computers are doing is basically passing a lot of these vectors through these quantum gates performing linear algebra operations on them which change the direction or the size of the arrow and essentially the intuition behind Grover's algorithm is there's a vector representing the correct phone number and what we want to do through these quantum operations is to lengthen that vector to get the right answers vector to be bigger and bigger and bigger and to get the vectors representing the wrong answers to be smaller and smaller and smaller until we get to the point where we can reliably detect the difference between the big arrow representing the correct answer and those smaller arrows representing all of the incorrect answers and so basically the magic is as you sort of sweep the arrows through these quantum gates that's exactly what these quantum operations are doing is they're lengthening the length of the right arrow they're shrinking the length of the wrong arrow until we get to the point where we can reliably detect the difference between the right answer and the wrong answer that is the arrow with big magnitude versus the arrow with small magnitudes the visualization you're seeing shows you the quantum operations as they're performed on these arrows and it comes from this fabulous design studio called twisted oak studios and I encourage you to go visit their website for more insight behind how this actually works so here is the big payoff by doing it the quantum way as opposed to the traditional way it's a traditional way we'd have to iterate through all of the entries in the phonebook and depending on the size of the phonebook and how long it takes us to iterate through one particular entry this could take a very very long time and there's no mathematical shortcut in contrast with the quantum computers we only have to perform a small number of operations and it's proportional to the square root of the size of the entries and so this table shows you the number of operations the quantum computer would have to do in contrast to the traditional computer and the advantage grows with the number of numbers to search right so if we have a million numbers that we're trying to search the traditional computer would have to do a million iterations whereas the quantum computer would only have to do a little over 30,000 and so here is the fundamental thing that we're trying to do with quantum computers we're not trying to build smaller computers we're trying to build computers that can solve a specific class of problems much much much faster than traditional computers so if you don't quite understand all of that intuition and the vectors and the size of the vectors don't worry about it quantum mechanics is so counterintuitive that Richard Fineman famously said if you think you understand quantum mechanics then you don't really understand quantum mechanics so don't beat yourself up I'll recommend some reading for you if you are interested in following up and understanding more of this and we'll put that with the blog post now that sounds great so you're probably thinking to yourself wow if there really are a class of problems that can be solved using this class of computers then why aren't we all running quantum computers well it turns out that quantum computers are incredibly hard to build and let me give you some fascinating stats that give you the intuition behind why these are so hard to build so it turns out that most quantum computers are made out of superconducting materials and the reason for that is you need to minimize the interaction between the quantum computer and the outside world it's very easy for the outside word old to disturb the results that you're getting from quantum computers and so one way to minimize it is to run them with superconducting material so most quantum computers are cooled to 0.1 degrees Kelvin to minimize that or interactions with the outside world so that is a very very powerful refrigerator just to give you the intuition interstellar space is 2.7 Kelvin so we need computers that are colder than interstellar space in order to minimize the interactions with the outside world another thing that makes these hard to build is this thing called the coherence time so because quantum computers interact so readily with the outside world we only have a small amount of time in which we can perform all of our calculations and that's called the coherence time researchers have made a lot of progress on raising the length of the conveyance time so we're up to state of the art these days is a hundred microseconds but even 100 microseconds is not a lot of time to perform operations in before the quantum coherence time makes it impossible for us to get a result out of the quantum computer another thing that makes these hard is I showed you the quantum operations that are performed and each of those operations takes 50 nanoseconds so we only have a limited amount of time if each operation takes 50 nanoseconds and our quantum coherence times honour'd microseconds we only have a certain amount of time we've only performed so many operations before we can't get a reliable result and then one last fun stat I talked about how what we were trying to do with groves algorithm was lengthen the arrow enough so that we could tell it from all of the incorrect answers the length of the correct answer was bigger so if you took the energy difference between the correct answer and the wrong answer the energy difference is only a difference of 10 to the negative 24th joules so it's incredibly difficult to detect the answers and so hopefully this gives you some intuition for why quantum computers are so hard to build the good news is that researchers are making a lot of progress on getting the quantum coherence time up inventing more algorithms in particular the quantum coherence time seems to be progressing very very quickly these days and in fact faster than Moore's Law and so we're pretty optimistic that at least on the quantum coherence time we're on a path to longer and longer coherence times so Wow hard to build a quantum computer what could we do if we had quantum computers so one of the things that you could do with quantum computers is that you could train so-called deep learning networks much faster in another podcast I talked about the history of AI and machine learning and deep learning and highlighted that deep learning is one of the most profound techniques that researchers are using to create artificial intelligence programs and if we could train these networks faster we could get much better deep learning results so that's one thing that you could get from a quantum computer another thing that you can get from a quantum computer is finding the prime factors of very very large numbers now everybody likes to say that you've got a supercomputer in your pocket so why don't you just take your supercomputer out of your pocket right now take that number that's on the slide and quickly give me the prime factors of that number no takers okay that still is a very very hard mathematical problem despite the fact that you have a supercomputer in your pocket and it's good news that it is a hard problem even with that supercomputer because all modern encryption depends on this fact that while it's relatively straightforward for a computer to multiply two prime factors to get a very large number it is very difficult for a computer to divide that number to recover its original prime factors in fact this mathematical property is what's behind all of modern-day encryption so if we had a quantum computer we could dramatically reduce the time it took to recover the prime factors and all of modern crypto that we're using today would instantly be susceptible to attack because it wouldn't take a long long time to decrypt somebody's messages you could do it very very quickly this is why the NSA and other state researchers are actively investigating how to use quantum computers and new algorithms to solve this particular mathematical problem so what else can we do with quantum computers well one intriguing area of research is called quantum chemistry and the basic idea here is we're going to try to use quantum computers to perform calculations that would help us find new chemical catalysts so let me give you a prime example of a chemical reaction that would benefit from a new catalyst and that's called the haber-bosch process so the haber-bosch process today creates ammonia from natural gas and it turns out we need ammonia for fertilizer so scientists regard the haber-bosch process as the literal detonator of the population explosion so we had 1.6 billion people living on the planet in 1900 and we have over 7 billion today and a lot of that is credited with finding enough food for 7 billion people and a lot of that is credited to fertilizer now the process that creates ammonia from natural gas happens at very high temperature four to six hundred degrees Celsius and at many times the pressure of the atmosphere and as a result it's very energy intensive scientists estimate that between one and two percent of all of the energy generated in the world today goes to making ammonia from natural gas so we can make fertilizer and this process is so important that 80% of the nitrogen in your very tissues comes from this process and so if we were able to find a catalyst that would allow us to either lower the atmospheric pressure or lower the temperature at which this chemical reaction takes place we could produce ammonia much much more cheaply and feed even more people let me give you another example of quantum chemistry so the picture you see here is a picture of the Tesla gigafactory which will start producing lithium-ion batteries in 2017 to put into the fabulous Tesla electric cars that everybody wants when it's in full production in 2020 this gigafactory will produce more batteries each year than were produced in the entire world cumulatively through 2013 so very very important Factory for the future of electric cars and for Tesla in particular now the chemistry that these batteries depend on which involve lithium ions was discovered in 1980 by an American physicist named professor John Goodenough at the University of Texas in Austin and since that time the energy density in other words the amount of energy we can cram into a given volume of batteries has been progressing at a rate of about 3% a year now that seems like good progress but of course in the computer industry we're used to things progressing much much faster we are used to things like Moore's Law where we're doubling the transistor count every 18 to 24 months in our chips and so 3% a year is pretty slow progress really and so we're hoping for a breakthrough so research scientists around the world are racing to discover new battery chemistry a breakthrough in batteries that would allow us to store either much more energy so that we can drive our electric cars much further so that's another very important application that we could apply quantum computers to so why pay attention now well the reason that we are paying attention now is that a lot of the pieces to making a quantum computer are really coming together and mentioned how difficult it was but research scientists are making progress on all of the key ingredients the hardware the software and the developer tools that enable people to write software and the algorithms that we're going to use and the braids of progress is astounding one of the things that I wished I could have done I was important in the right decade for this is to be a fly on the wall inside Bell Labs when all of the key ingredients for computing as we know today came into being so the transistor itself semiconductors information theory the C programming language the UNIX operating system he also had Grace Hopper outside of Bell Labs with compilers so all of this intellectual ferment that has led to us being able to use the supercomputers in our pockets it would have just been so fun to listen in on the conversations as they were happening and basically that same ferment that same intellectual ferment is happening right now around quantum computing so in the university labs in the corporate R&D centers and at startups there's just so much excitement that right now we should be able to put all the pieces together to learn from the lessons of the past and build these breakthrough computers that can perform these calculations that are mysteriously hitching a ride on the calculations that nature seems to be doing itself so with all the key ingredients coming together it's no surprise that some of the biggest university labs corporate R&D centers and even state-sponsored research is being directed at solving the quantum computing problem so on this slide you see the budgets the team sizes and the investments that well-known organizations are making and this is really to us a sign that now is the time to start looking for startups that can participate in this ecosystem and help bring quantum computing to life and in fact keep your eyes on this space and we'll have announcements to come about companies that we have found that do exactly that in the meantime just marvel the fact that we're going to try to build these classic computers that take advantage of quantum mechanical properties of atoms and sub atomic particles somehow getting them to perform calculations for us that they're doing by themselves in nature already be well

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *