Katie Barr: Simulating quantum physics in less than 20 lines of pure Python

I'm Katie bar I'm currently a technical consultant the test people though only for the next week where I mostly do cool stuff in Python before that I did a PhD in quantum information where I also did some cool ish stuff with Python so today I'm going to tell you about that because I think it's fantastic the something that a lot of people find so intimidating if you have a tiny bit of Python knowledge like becomes really easy to simulate and play about with and you can properly learn what superposition means what amplitude means you can see interference phenomena you can see measurement so it's my way of trying to get my love of quantum physics over to the masses so we're going to talk to you about a particular model which is called the quantum walk and I'll tell you about that in quite some detail so that hopefully when we get to the simulation which I'm going to rush over a little bit because you can all just email me and ask if you want the details I'm going to try and convince you that this is an interesting thing to study and by showing you some really cool applications and you with the simulation I'll give you a you can go away and do research that is publishable like I publish research on something that's almost identical to what I go go through with you today about two years ago so this isn't a trivial system this is something that is an open topic of research so I'm not just giving you a baby thing to make it easy alright I'm giving you something that is still of interest to the quantum information community so the quantum walk is hopefully what you guessed it was which is the quantum analog of the classical random walk boats really similar so you have a calling operation and the shift operation so in the classical random walk you just flip your coin that tells you whether you go left or right and then you apply your shift operation which is simply a permutation and then you repeat that for as many steps as you like they can both take place on arbitrary structures so the most obvious example is the line but you can really run this on anything and they can be to be modeled in continuous and discrete time and which one you choose really depends on what you want to do so people looking to model physical phenomena tend to look at continuous time versions of things because the flow of time is continuous and computer scientists we're all used to like computational steps of Turing machines and stuff like that so we tend to look at things more in discrete times and they're both really easy to simulate okay the classical random walk on the line was the first piece of code I have a wrote the piece of code I'm going to show you today it's the third piece of code I ever wrote so you don't need any skill whatsoever which for me I find quite useful and so why did we do this so classical random walks are used in loads of algorithms they're really really useful quantum computers are known to be fast and but it's not enough to know that we have this fast computing system we need to be do be able to do things with it so we need to be able to develop algorithmic tools and like where do you look for for algorithmic tools we're quite lazy in academia we usually think someone's had an idea before so we'll just go and Nick that so it's all a classical random walks yeah they're really useful maybe we'll make a quantum analog of that and that might be useful and it turns out it is like if you have pretty much any problem in computer science can be mapped or already has a mapping to this paradigm so it's already proven algorithmically useful now we just need to build a quantum computer to run them on which I'll also say these exist in the lab the thing I'm showing you today has has been run so if you can turn your problem into something like this then you might not need to wait around for us to build quantum computers you might be able to like modify an existing experiment and that'll doing a computation for you so I think that's pretty cool but hopefully I'll comment to you by be able to talk so the system's defined and this goes for all of quantum mechanics is vectors matrices and operators operators are simply a mapping from a vector space to another vector space in this case we're actually mapping from a vector space to the same vector space and I'll use the word system later quite a lot and to me a system is just a vector in a vector space so please don't be confused by that so I need to tell you a tiny bit about quantum mechanics and so I'll be talking about amplitude this is what you use to calculate probabilities and we usually denote it alpha and it's a complex number and that's really important because controlling interference and is what gives us a lot a lot of quantum algorithms are based on the ability to quant control interference so if you didn't have these complex numbers which if you've done any sort of wave mechanics ever it's just a phase and then you wouldn't get a lot of the richness of quantum systems so we have unitary operators and this just means validly quantum mechanical so the time reversible and probability has to be conserved because otherwise it doesn't make much physical sense and orthogonal states are mapped to orthogonal States so I mean tolds that in principle component analysis you have a similar mapping so if any of you have done that then you can probably think of these in a language that's much better known to you so we have the coin state and the reason for that is to make the system reversible people originally tried to make quantum analogues of classical random walks by just summing up paths but if you're at position 5 after tie after time 10 times steps and you have no information about where stuff has come from you don't know which path which parts of your amplitude have come from then you can traverse it so the quantum the coin state is what preserves the sort of memory of where you've been and enables you to turn reverse it and a time step is literally just a multiplication of the state vector by the time evolution operator and so all we're doing here is matrix multiplication apart from I'm not going to show it to you like that because I promise I'm not doing this in person with no imports so but fundamentally that is all that you're doing so the quantum walk model for an arbitrary graph so this is just a set of edges and vertices we have a coin operator this acts locally each vertex and don't worry I'll show you this and more concrete terms on the next card slide and and it just has to be any unitary operator if you have irregular graphs so graphs where there are different numbers of edges going into different vertices then obviously you need a different coin apply to every node and then we have the shift operator that is simply a permutation so it's saying if we're at the eighth coin state of node V then after we've applied the shift then we are at the eighth coin state of node U and permutation matrices are always unit free so just because they're 0-1 matrices everywhere so to make this a little bit more concrete we have a little diagram here so say we're starting our walk and we're putting all the amplitude into our system through this edge here so we're all coming from the top coin state at vertex one will apply our coin operator and we're going to assume it's a non-trivial coin operator so that's going to give us amplitude in all three coin States here and then when we apply or shift the amplitude in this coin States that's going to the right it's just going to be swapped with the amplitude in this coin state at node two which is going to the left so hopefully you're all following so far but I'll make it a bit more concrete again so we're going to be doing it on the lattice and out so that we can use something called the 4d grover operator and well I'll show you later while that's cool but I'm so this we're going to start in an equal in magnitude superposition so here superposition is just a combination of basis States that just means you're in a combination of you've come from up right left under all at once and I've really out in direct notation which is what quantum information theorists use this it just vectors so any combined quantum systems by taking a tensor product and the tensor product is pretty much like a full outer join on a database so I'm pretty sure that all of you've done one of those at some point and I'll make that analogy because then hopefully you can see why these things grow really quickly as you combine them and therefore why they're hard to simulate on a classical computer and therefore why we need quantum computers that have this nature inherently in order to properly and explore quantum mechanics so to get a lattice we literally just combine a line on me and in the horizontal direction with the line in the vertical direction and then we're going to combine that with our position space so we're going to start like that and I'll show you that in code in a second so the first step will have applied our coin here will have done off shift and we've moved in a combination of all the directions so the second step I hope you can see I've made this lighter to try and show that there's less amplitude at each position but then we have moved a little bit back into the middle and we've moved outwards as well and I've kept this diagram and consistent with the simulation that I'm running in general you'd move out to these nodes and the ones at the top as well but I also wouldn't fit on our side but that hopefully gives you an inkling of how you get a quantum speed-up with this thing straight away because our classical thing and you always expect it to just get back to the origin but this thing after two steps it's already spread out up to two nodes away from the origin so if you control your initial state in your coin correctly then you can get a very high probability of being measured a long way from the origin in tea-time steps so it's ballistic transport and which is the same in human terms you're walking in a straight line instead of taking a random walk so I get on to the tiny bit of code I don't know what happened to this box at the bottom sorry so we we have to initialize the array that we're going to walk on and our initial state so to determine the size you just decide how many steps you want or wrong to walk for and double luck because you're going to start from the middle and if you're going to hit the edge then you're gonna have some problems so you need to take care in that case either by looping things back to create a sphere or applying a different operator on yeah and just so in the easiest case just don't hit the edge so literally all we have is a list of lists and each element in our array is just going to have four values that are the up down left and right amplitudes so we're going to set that I've chosen these particular values because they give some nice evolution very distinctive so that's a good way of telling if your simulation is correct pick something you know it's going to give you very distinctive evolution so to do the time step because you have a regular lattice like you are actually you know we're amplitude is going to end up from each position you know it can only go up from a certain coin state in your current position or down from a certain coins day so instead of having to do matrix multiplication you just initialize a new array to give you to put your intermediate amplitudes in and the ease of following I've just made some assignments here so we're saying the zero state is going left the two state is going right and then one and three or up and down and here and these A's are 0.5 by the way because this is just the operators that we're giving and we're basically applying the coin flip all at once here and so I'll show you the matrix version of this operator very shortly but if you remember matrix multiplication you just take one row and then you multiply it by your vector and then that gives you the component now so this our vector is left up right down and our row of our matrix is - eh eh-eh-eh so we're just doing that directly and that is going to go into the left coin state at a new position zero so just run that for 40 50 steps and you've done your walk and so I wanted to show you just again what we're actually doing mathematically at each name so this is the four-dimensional grover operator which is famous due to Grover's algorithm which will show you very shortly and so see here Ras was 0.5 so I really was just taking this row this matrix and multiplying it by these components here that's a first step just written out for you after the coin flip and their knees are what get shifted into the new positions here okay so there's not really a huge amount of point in running a simulation if you're not going to look at the results of it so in order to get the results we're not really interested in the coin state we only want to know the probability of being in a certain position and the way you calculate that is by using me something called ball rule and and this is just saying to the probability of being measured in state I is the projection of your state vector onto the subspace re and then the multiplication of that by the conjugate transpose of your state vector so programmatically that's literally just there this here you times your amplitude by its complex conjugate so just loop over all positions and then you have your probability distribution at the end so I'll show you some example dynamics and I would recommend if you're interested in this that you go away and sort of look at this yourself because it's really interesting you know to me it is anyway this is the simulation that I've told you about so you'll see this is dramatically different the other two which I'll get to in a second you have this high peak I don't know if you can read these values here but this is 0.4 this is 0.04 and that's the 0.04 so this peak is 10 times larger than the highest peaks these two and you get these sort of waves traveling outwards as well and your choice of initial condition determines how much probability stays in the center and how much probability moves outwards so I've shown you these for comparison this is the discrete Fourier transform so hopefully you've all come across Fourier analysis they it's really hard to see here you need to really have the graph in front of you and twiddle it about the this is something called the Hadamard operator which is just the 2d Fourier transform and applied to the left and right and up and down directions and what you actually get I told you that to make a lattice you just combine a line in one direction and in another direction if you act just on those directions then if I flip this over you'd see a cross like this you've really just got Lorentz going in two directions so that's because you don't have entanglement between the sort of left and right and up and down directions so entanglement is just a property of systems when you interact them they they become well they become just one system you can't really consider them as a single system anymore but it's also useful to look up because you can treat that as a computational resource so if you want to analyze this their own it really depends on what you're looking for but you can look at the shape of the distribution so I told you I've shown you a couple of different shapes you can get you can see how different features of the coin contribute so it's really hard to show on a static slide but I told you entanglement between left and right up and down directions makes quite a big difference and you can look for things like rotational symmetry or you can just look at things like the expected distance from the mean if you're interested in transport properties it really depends why you're running the simulation and also again it's probably too complicated to go on now but entanglement between coin and position can be quite interesting so pretty much just stat everything on this slide so different transport properties that you can look at depending on what you want from your walk so perfect state transfer is literally just going completely from A to B in some architectures of quantum computers you need that to get your quantum state to the next stage of the computation so there's a lot of work in that or if you're more interested in modeling physical phenomena then you will do it with the continuous time or in general that tends to be really difficult so I would argue against it and if you're interested in algorithmic properties then generally you'll write your algorithm and you'll just run a simulation to confirm that you've not messed it up somehow and so if you are actually want to do research with these sorts of things then there are quite a lot of things that you need to do referees tend to ask for comparison with the classical case now because you have a quadratic speed-up in comparison to the classical case so you need to run if you run your quantum walk 40 steps you need to run your classic classical walk 40 squared steps so my advice would be don't make the quantum one too big because otherwise the referees will come back and ask you to run a simulation that you can't physically do on the hardware you have you can't just pick random values for the for the initial state and think that you're going to get something that actually represents the and behavior so aggregated behavior of the system because they're not uniformly distributed so if you want to look at sort of well properties of things the independent of initial state in there for wrong things for lots of initial states then you need to do some transformations and because these tend to be computationally intensive I would say just try not to run simulations because people prefer analytical results anyway like if if you think that you've found something by simulation and you don't prove it then again your referees are just gonna come back and say all right prove it so I only run simulations if you need so the way I run these was with a mathematician and we sort of paired and where he got stuck I'll run some simulation so I'd say go and look at this and then we sort of had a really good relationship where we encouraged each other and pushed each other on and so try and find a mascot so to prove to you the vote on training isn't just some trivial thing I wanted to mention Grover's algorithm so we're using the grover operator this is asymptotically the fastest possible that way of solving this problem using a quantum computer so this is an algorithm to search an unsorted database and classically you can't do this in less than linear time which means basically checking everything in a roam is as fast as you can get so it's not too much more work to get from the stuff I've told you about today too Grover's algorithm so you need to work on a hypercube rather than and a lattice and your hypercube so the things you're looking for a binary strings and they're binary strings of a given length and each point on your hypercube represents one of those binary strings you start in a uniform superposition over all of the nodes on your hypercube when you apply the Grover coin every node apart from your marked node which is the node that actually is the string you're looking for you run this for a predetermined number of stats and then you measure the particle position and there's a very high probability that your particle is going to be where the at the Moret state and if it's not this is really fast and you just run it again so in general quantum computing is probabilistic so you can't get as a proper answer out of a single shot of your computation you need to run it for long enough to actually get the probability distribution and and but that's not really an issue for quantum information theorists because these things I don't know numbers but we generally talk about things and that evolve in sort of scales of nanoseconds so if you're doing and these are for really large things that you can't like a thousand qubit and quantum computer would beat a super modern super computer so yeah they're fast we just need to build one that big and I also wanted to show you because this is cool because it uses the exact operator that I've told you to use as your coin operator but in a different way and this is used to prove that quantum marks or computationally universal so that means that they can simulate anything you like and the proof has been done via logic gates so hopefully you're all familiar with the circuit model of computation and so I'm going to show you two parts of the proof I also say having studied lots of theoretical computer science in quantum systems it's very easy to get computational universality so in classical logic systems it is as well so you can have a single gates that seem that's a fairly gate so it's sort of not surprising if you can turn this into a circuit that it's Universal then so we've proved it's Universal by showing it can simulate in our elementary gate set so there are a number of ways that you can do that but roughly it always needs a two qubit gate so we have qubits instead of bits so these are our wires and these you can tell they're qubits because they're in direct brackets and so there are a number of ways that you can build an elementary gate set but fundamentally I mentioned earlier need you need to be able to control interference so you need to have a way of changing the face of your and qubit because that's what determines the interference phenomena and yeah you need a two qubit guy and his otherwise if you just had a load of qubits all on separate wires never interacting with each other then it wouldn't really be a multi qubit computation so I'm gonna show you don't do really well then only I mean I've probably forgotten to stay loads of stuff in that case time for questions so I can fill in the blanks then so I'm going to show you how to make the wires so previously we were applying operator on something that have amplitude in every position of every coin state or just any coin state if you're going and past the first step of the simulation here there's a property and this works for all dimensions if you have an even dimensional Grover operator so it's acting on a node of your graph of even degree and half of the coin states in your node are equal in magnitude and phase then so phase is just like a complex coefficient if I'm making from losing people with that but I'm so yeah if they're equal in magnitude and face and half of them are populated then it deterministically transfers all those amplitudes into the previously unpopulated half of your node so you can use this to build wires that have two inputs coming from one side and two inputs going out at the other side to deterministically propagate amplitude across your workers because it wouldn't really be a great circuit if you didn't know where your amplitude was going to be at a given time you wouldn't know where to apply your logic gates so it would be pretty useless so I'm going to show you the simplest logic gate that there is so you're all I really hope you're all familiar with the controlled-not gate it's literally you have a control bit or qubit and you have the sort of ancilla bit or qubit and the control bit does nothing but if it's in state 1 then the and Sylla bits and flipped so if it was a zero before and you change it into a 1 and you do that literally by just crossing these wires so that I'm showing these two examples that Grover's algorithm in the circuit to show that these quantum walks have lots of applications in computer science and you can I did a lot of work on quantum finite automata and they are sort of equivalent in quite nice ways to quite a few different quantum finite automata if you like cellular automata then they there's a really simple transformation that you can do to get from a quantum cellular automata into a quantum walk and so and because we know that Universal might we know basically that the reefs are mapping from any sort of paradigm of computation to the quantum walk if someone hasn't worked it out unfortunately you'll have to work it out yourself and a lot people have done a lot of work on this so um now a lot earlier than I anticipated got to my final slide and so and I've introduced the discrete-time quantum walk I really hope that I've made that clear and not garbled it by rushing too much because I was so worried about going over and I've showed you how to simulate it on the lattice and I've discussed two applications of quantum walks and just because I have a little bit more time there was one more I was going to put in that I missed out which is to me the coolest one so I'll tell you about very briefly and this is the continuous time walk rather than a discrete time walk but that just evolves according to the Schrodinger equation so you don't need 20 lines of Python for that you need one import and then do an undo matrix multiplication sexplanations exponentiation through numpy but i'm that is this does this antenna complex called which exists on a photosynthetic bacteria that live in really really murky horrible lakes and these guys they get one photon per hour if that photon doesn't go to the reactant reactional center where photosynthesis takes place it's going to really really damage the bacteria think about what Sun does to your skin now imagine you're a single-celled organism and you have that amount of energy just floating around in you it's going to mess things up so these things are really really efficient at capturing might and we have not been able to explain that classically and we recently developed quantum mechanical and models for that and when looking at the successful trajectories so lights that goes from the antenna into the reaction center to make ATP then the trajectory is a quantum walk so I'd say but they're also fundamental to life on Earth and well we'll see because I think they did some new experiments and got totally different data than they previously had so I'm not sure if this is any any longer true but I'm yeah so you can use them to model loads of processes or just talks about computer science because oh I did computer science but I'm so yeah I'd also like to thank Calvin dials for trying to help me make this talk sort of accessible to you guys I really really hope that we've implemented ways that and then Florian and Ian of helps as well I should have probably put my PhD supervisor on there as well you probably don't know her so it doesn't thank you very much listening do you have any questions yeah so okay so I mentioned the quantum cellular automata as well and then quantum finite automata and there are also so these sort of like nouns trees I don't really know what they are like people have done work on that so those are the three main ones that I know of and then there are also rather than particular models of computation like people have done work to implement other algorithms using this as well so yes yes they have in fact I really wanted to troll the person doing my Python training course because they had a game of life and I wanted to give them a cultivation but I'm yeah if you look it up it's on the archive so yeah well that really depends and so if you're Google then you've already bought one that's d-wave but so people are really mean about d-wave because they don't show it to anybody and actually when they come so does and not a universal computer and it does this thing called simulated annealing it takes a month to startup and then when they compared it to the classical case it wasn't any faster so by the time you add the month-long startup time then you're really hot so yeah if you have a billion dollars then you can buy someone that somebody one that somebody claims is one right now so as I said already the the walk on the lattice is implemented in the lab already so if you really wanted to go and buy yourself an optical table dig down into the foundations of your house and do some fancy stuff see no vibrations get through and stand get stuff to make sure it can be properly dark and all that stuff then you could do that now but yeah when it if you're asking when you'll be able to buy a multi-purpose quantum computer I I can't tell you that I think that we'll see a scientific revolution on the back of these within our lifetimes but I'm an optimist okay you have any more questions okay well I'll assume you're being sarcastic

Channel: PyData

Views: 16,609

Rating: 4.8836365 out of 5

Keywords:

Id: 6j3J-LC0cck

Length: 36min 31sec (2191 seconds)

Published: Tue Oct 06 2015