Spatial search using lackadaisical quantum walks
Wong, Tomas
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is a useful model for developing quantum algorithms. For example, many quantum spatial search algorithms are based on coined quantum walks. In this talk, we explore a lazy version of the coined quantum walk, called a lackadaisical quantum walk, which uses a weighted self-loop at each vertex so that the walker has some amplitude of staying put. We show that lackadaisical quantum walks can solve the spatial search problem more quickly than a regular, coined quantum walk for a variety of graphs, suggesting that it is a useful tool for improving quantum algorithms.
 Thank you for the introduction. Thank you to the organizers for inviting me. So I'll be speaking about some work on spatial search. So it's an algorithmic application of quantum walks. And the type of quantum walk I'm going to be using is something called a lackadaisical quantum walk. So lackadaisical is just a synonym for lazy. So it's a lazy quantum walk. So I'll start by introducing what this is by reviewing what you all have seen many times in an expert's in, which is the 1D line. So talk about a normal random walk and then a normal Hadamard quantum walk. And then what makes a lackadaisical quantum walk different? After that, we're going to look at some search problems. So we're going to start with Grover's problem, which is search on the complete graph. And then we're going to look at search on the 2D grid. And then we're going to look at some recent results with one of my undergraduate students on search on the complete bipartite graph. If you want to ask questions as we go, feel free. I'm used to teaching undergrads. So you can just raise your hand or if I don't see you, just shout out or something. All right. But first, before we get to that, it seems like no one knows where Omaha, Nebraska is. So I thought I'd start with that. So where is the state of Nebraska? You want to see it? I start to see some knots. People are picking it up. Yes, it's right there in the middle, in the Midwest, above Kansas. And Omaha is on the eastern border next to Iowa. So that's where Omaha, Nebraska is. Now you know. So Omaha has a population of about half a million. If you count all the towns around it, it's a population of about one million. What is Omaha known for? Well the biggest thing is Warren Buffett. So Warren Buffett is a legendary businessman and investor. So I think he's the fourth richest man in the world. But he's very generous. So he's the billionaire who started this challenge to other billionaires to donate most of their money when they pass away. Yes, so his company is Berkshire Hathaway, which I think is the fourth largest company in the world. And every year they have their shareholders meeting in Omaha. And so tens of thousands of people from all over the world convene onto our mid-sized city for this shareholders meeting. We're also famous for the College World Series, which most of you wouldn't know. Does anyone know what sport this is? How about that? Baseball. Baseball. So yeah, it's American. So the college baseball championship takes place in Omaha every year. And then finally, we actually have a very good zoo. So the San Diego Zoo and the Omaha Zoo actually go back and forth as the number one zoo in America, which you wouldn't expect in Omaha. All right. So let's get into the research. So if you have a quantum walk on the line, as you know, what you do is if your walker starts in the middle, what he does is he flips a coin. And if it's heads, then he faces left. And then if it's tails, he faces right. And then after that, he takes a step. And again, you flip a coin. You face left or you face right. And you take another step. And if you repeat this process, as you know, many times, you get this shape. So this is a binomial distribution. And the spread of this is quite slow. It scales as the square root of the number of steps. OK. So you guys know this. And just to be clear, this is using the Hadamard coin and the moving shift. So if we look at a, sorry, that was Costco, now for the quantum. So you see the quantum. So it's the same idea. So what we'll do is when you flip the coin, we'll flip a quantum coin. And so now the result can be a superposition of heads and tails. So you point left and right. And then when you take your quantum step, you step in a superposition. So now you're in multiple locations at once. And you repeat that so that you're in a superposition of heads and tails and a superposition of positions. And so if we do that a bunch of times, well, here's the classical result we just had. And now the quantum result, as you know, is this two-peak behavior. And the spread of this is much faster. So instead of being stuck around here, you're more likely to be far away at the peaks. And the standard deviation of this scales linearly in time. So it's a quadratically faster spread. And this is some intuition as to why quantum algorithms based on quantum walks might be faster, because it can spread more quickly. This is the part that has a Hadamard coin in the moving shift. So the moving shift means if you're pointing left, or this is your right, if pointing right, you take a step, you just continue pointing right. So that's it. You just move left or right. All right. So let's talk about lazy random walks. So classically, first, lazy random walks are actually really useful algorithmically. So nothing quantum here. And just to give you some intuition for why. Just consider a bipartite graph like this. So a bipartite graph has two vertex sets. So there they are circled. So you see, in each set, they're not connected to each other. They only connect to vertices in the other set. And let's say we do a classical random walk where we start with some probability distribution over the left set. So if we take a step of the walk, where do we end up? We end up in the right set. We take another step of the random walk. Where do we end up? We take another step on the left set. And we see just even with a classical random walk, you only are in one set or the other. You're not over both. And so if you want to be in a probability distribution over both sets, what you can do is you can use a lazy random walk. So you have some probability of jumping and some probability of staying put. And if you do that, then you'll get some probability distribution over both sets. And you might imagine some situations where this might be useful so that you don't just get trapped in one set or the other. And so classically, there's a bunch of applications of this that I'm not an expert in, but there's some citations if you want to look things out. And so a while back, I was thinking about whether or not there were some quantum analogs of this. And so Andrew Childs came up with one in 2010, which he called a lazy quantum walk, which is quite complicated. And so when I came up with mine, I needed a different name because lazy quantum walk was already taken. So I just looked up, what are synonyms for lazy? And I picked lackadaisical quantum walk. This is kind of a fun word, even if it's hard to say. So lackadaisical quantum walk. And so the idea here is very simple. All you do is you add a self-loop at every vertex. So on the one-dimensional line, it would look like this. So you have three directions now. So if you're at the origin, you can point left, or you can point right, or you can point to yourself so that you stay put. And so then if you walk, you can walk left, you can walk right, or you can walk in place and not move at all. And these are weighted edges. So that way you can adjust how lazy the walker is. So if L is bigger, then it's going to be more lazy. You're going to preferentially stay put. And if it's smaller, you're less lazy. All right, so one of the things with this is if we have three directions now, we can't use the Hadamard coin, because that's only for two directions. And the coin that we use in search algorithms is called the Grover coin. And so let me start by reviewing the Grover coin on an unweighted graph. And so let's look at this left, right, and pointing to yourself with no weight. So there's no weight L here. So everything has weight 1, if you will. So with this normal Grover coin, let's see how it acts on the amplitude. So let's say you're here and you're pointing left with amplitude A, you're pointing B with amplitude, sorry, you're pointing right with amplitude B, and you're pointing to yourself with amplitude C. So what we're going to do is we're going to let mu be the average of these amplitudes. So it's literally A plus B plus C divided by 3. So it's just the average of these amplitudes. What the Grover coin does is it transforms this state into the following. So where there was an amplitude A of pointing to the left before, it now becomes 2 times the average minus A. And then where there was B before, it becomes 2 times the average minus B. And where there is amplitude C becomes 2 times the average minus C. And so this transformation actually is an inversion about this average mu. And so if you learn Grover's algorithm from an introductory course in quantum computing, one of the operations is an inversion about the mean. This is exactly that. So this Grover coin implements an inversion about the mean. And so if you try to search algorithms, it ends up having that Grover characteristic. Any questions so far before we get to the lackadaisical version? OK, so for the lackadaisical version, we need to see what happens on a weighted graph. So now we have this self-loop with weight L. And the left and right are unweighted. So they're weight 1. So let's say the amplitudes again are A, B, and C. And let's see what happens. So instead of the average of the amplitudes, I'm going to define this quantity mu bar, which is A plus B. And for C, since it has weight L, it gets multiplied by the square root of L divided by the sum of the weight. So this is weight 1, weight 1, weight L. So this is 1 plus 1 plus L. So this is not the average of the amplitudes anymore. And what this generalized Grover coin does on a weighted graph is amplitude A becomes 2 times this not average minus A. B becomes 2 times this not average minus B. And C becomes something a little different. It's 2 times this average, not not average, times the square root of L minus C. OK, so what happens is A and B get inverted about this non-average, this whatever it is, mu bar. So unweighted edges are inverted about this quantity. And then C is inverted about this thing times the square root of L. So that acts a little differently. And you can generalize this to whatever weighted graphs you want. So this is actually just a quantum walk on a weighted graph now. Looking for a picture, OK? So let's see what happens. So the reason why the Grover coin is defined like that is because if you use that generalized Grover coin and you use the flip-flop shift, what you get is a walk that is exactly the same as Zegadie's quantum Markov chain. Because with a quantum Markov chain, you have different probabilities of moving one way or another. So it's essentially a weighted graph. So this is the quantum, this is the coin quantum walk equivalent of Zegadie's quantum walk. The flip-flop shift I haven't talked about yet, so just to quickly go over that as many of you know. If you're at this vertex and pointing right, so you're here, you're pointing right, what you do is you hop and then you turn around. So you end up here pointing backwards. So you, you, and then you flip. So it's a flip-flop shift because you flip your direction. So that's it. So using that previous coin on a weighted graph and this shift, you get something that's exactly the same as Zegadie's quantum walk or quantum Markov chain. All right. So with all that, let's see how it acts on the 1D line. So here's the classical result. Here's the normal coin quantum walk and the lackadaisical quantum walk is this. And so what you see is that, okay, yeah, there is some probability of staying very close to where you started. But there's also a significant probability of being far from when you started that's actually even further than a normal quantum walk. So in some sense, a lackadaisical quantum walk, even though it's lazy, can actually spread faster-ish because of this middle peak. And so you might start to wonder, well, are there any algorithmic improvements that you can make with this property? The standard deviation of this is still linear in time, but it's a bigger factor in front. And so we're going to look at some search problems with that. Pause the moment so people can finish writing. You're telling me you're a standard grads. All right, so let's go ahead and do that. Let's apply this to some algorithmic problems, to some search problems, and see if we can get any improvements. So let's start by talking about what this search problem is. It's called spatial search. So imagine you're looking for a cafe. So this is Riga Latvia, where I did my first postdoc, and that's the University of Latvia. And so imagine you're new to Latvia, and you're looking for a cafe, and you're starting in front of the university, and you're like, I don't know where a cafe is, but this is Europe. If I just wander around, I'm sure I'll find a cafe. So what you can do is you can do a random walk. So from here, you have three options. You can go up to the left, you can go up to the right, or you can go down to the right, and you just randomly pick one. So let's say you go up to the right. So up to the left, never mind, very random. And now here, again, you're like, well, which way should I go? There's no cafe. Here you can go up to the left, up to the right, or you could actually go back the way you came, maybe that way you don't like. So you randomly pick one, and you end up over there. Again, you have three choices. You go over there. You have more choices now, which way to go, and say you randomly pick that one, and then, oh, there's a cafe there. So the idea is you randomly walk. Go, is your cafe? No, randomly walk. Is your cafe? No, randomly walk. Is your cafe? No, randomly walk. Is your cafe? Yes, you found your item. So this is the spatial search problem. Quantumly, you can do a very similar thing, except with a quantum walk. So if you start there, now you can walk in superposition. So you flip your quantum coin, a three-sided coin, and then you walk in superposition, and now you can end up in all three of those locations. You do the same thing. At all those locations, you flip your coin and walk, and you end up in something like that. And now you see that there's actually some probability at that cafe that's in the corner. There's actually another cafe over here, but whatever. There's actually cafes everywhere. It's Europe. Okay. But this is the idea of spatial search. So let's get to the particulars of it and how fast these algorithms can be, starting with the complete graph. So this corresponds to Grover's algorithm. So here's an example of a complete graph with six vertices. In general, we'll have n vertices. And it's a lackadaisical quantum walk. We have a self-loop of L everywhere. And let's just say that's the marked vertex indicated by a double circle. But the idea is that you don't know that, you're trying to find it. So there's something to explore in a couple of papers. And the complete graph corresponds to Grover's problem. It's this unstructured or this unordered database that Grover's algorithm solves. Because the idea is there's no order here. If you read this vertex, you can jump to any other vertex. There's no constraints as to how you can move. All right. So there it is again. So let's talk specifically about this algorithm, since this is a quantum walk conference. You guys can see more of what's going on under the hood. So for the initial state, all of the amplitudes along these internal edges are the same. So the amplitude of here pointing to there is the same as the amplitude here pointing to there. And the same as the amplitude here pointing to there. And all of these internal edges, you start with the same amplitude everywhere. And then for the self-loops, it's that amplitude, except you multiply it by the score root of L. Because it has some nice properties and stuff. A couple of nice properties. One of them is that this is a uniform superposition over the vertices. So every vertex has the same total probability. Because all of these internal edges are the same. And then they all have the same, all of these self-loops have the same amplitude as well. So basically every vertex has the same total amount of amplitude, same total amount of probability. So this is a uniform superposition over all the vertices. If you were to measure this initial state, you'd get each vertex with probability 1-6 in this case. Another property of this is that this is a one eigenvector of the quantum walk of the coin in the shift. So if you applied only the quantum walk to this initial state, nothing happens. If you want to search, you need to do more than just apply the quantum walk. You need to query the oracle as well. You have to ask, am I at a cafe? So the search algorithm applies the following. You have an oracle query, and then you do the quantum walk, which is just the Grover coin and the flip-flop shift. So this constitutes one step, and you're going to repeatedly step through this. So the Grover coin we talked about, the flip-flop shift we talked about, now let's talk about what the oracle query is. Any questions? OK, so the oracle query here is really simple. All it does is it flips the amplitude at marked vertices. So just give you an example. Let's say we have an unmarked vertex here, and it has amplitude A of pointing up, B pointing to the right, C pointing down, and D pointing to the left. So if you apply the oracle to this, nothing happens because this is unmarked. So you skip the exact same thing when you query the oracle. If it's marked on the other hand, shown by this double circle, then each of these amplitudes, A, B, C, D, become flipped. So you get minus A, minus B, minus C, and minus D. So this is the phase flip oracle that you use in Grover's algorithm for whatever problem you're solving. So it's the same idea here. So that's it. So all you do is you apply this phase flip oracle, so the marked vertices get their amplitudes flipped, and then the Grover coin, and then the flip-flop shift, and you just keep doing that over and over. That's it for the search algorithm. So let's see how this searches the complete graph, let's say, with 1024 vertices. So let's start with no self-loops. So with no self-loops, or when L is zero, what happens is the success probability starts at 1 over 1024, which is pretty small. And as you keep applying this query coin shift over and over and over, the success probability builds up. So more and more probability builds up at your marked vertex until it reaches a peak of a half, and then it's going to go down and then keep going up and down like that. And so this time at which you reach your max success probability, this is order square root of n, which is Grover's order root n runtime. Since the success probability is a half, on average you'll have to run the algorithm twice before you find the marked vertex, but if you double your runtime, it's still order square root of n, so you're fine. So this is the quantum walk version of Grover's algorithm without lackadaisical, anything like that, just normal coin quantum walk version. If you make it a lackadaisical quantum walk, let's see what happens. So instead of L being zero, let's increase L a little bit to 0.1. And you see that the success probability that you reach, instead of reaching half, you reach a little bit higher value. If L is 0.2, you reach a higher value still. If L is 0.4, it's even higher. If L is 0.8, it's almost that one. Let's keep going, let's clear the graph, so we keep going. If L is one, you do reach a success probability of one. If L is greater still, two and a half, oh now it's actually worse. If it gets more lazy, it's worse again. If you get more lazy, it's still worse. And so what we see is that the best amount of laziness is actually, if you increase more, is actually when L equals one. So for this algorithm, there's some optimal amount of laziness, which could be a life lesson. And so we do get algorithmic improvements by using a lackadaisical quantum walk. And you can actually, so yeah, you can search more quickly with a lackadaisical quantum walk. So you can actually prove all this analytically. So that's in the paper. Basically, depending on what value L is, you can find what the runtime and the success probability is. You don't need to parse through all that. The idea though is that this is solved. And basically any question you want to ask, you can get from these results. So for example, the success probability originally was a half, and then it went up, and then it went back down. And at some point, it became less than a half again. So there's some range of L's where you'll do better than a half. You can use these formulas to figure that out. And what you can find is that when L is less than roughly 5.8, the success probability is better than a half. So you can ask whatever question you want like that. Any questions so far? All right, so let's jump to the two-dimensional grid or the torus. And again, say there's n vertices. And this is a torus, so the boundary conditions wrap around. So let's see what happens here. So again, we'll just look at some simulations. So the normal coin quantum walk, no self-loops, not lazy, looks like this. So here n is 256. So the success probability starts at 1 over 256, and it builds up a little bit, and then goes back down and so forth. So if we make it lazy, let's say L is 0.005. And now the success probability actually jumps up quite a bit. It's more lazy. It jumps up some more. Make it more lazy. And oh, it's bad again. So again, we see the same trend where there's some optimal amount of laziness so that your success probability is boosted as much as possible. And so with this one, if it's bigger still, it's still worse. So this optimal amount of laziness is green curve that's 0.015. This actually corresponds to when L is 4 over n. And so for example, if we let L be 4 over n, we can pick different values of n, different size grids. So when n is 256, which is the plot we just had, you get this. When n is 1024, you get this. If n is 4096, you get this. And you basically see that the success probability is constant and it's near 1, which is nice. And so in terms of runtimes, well, a normal quantum walk that's not lazy, it's the time to reach that first peak in success probability, scales as the square root of n log n, and the success probability, so the value of that peak, scales as 1 over log n. And so if you use amplitude amplification, the total runtime is root n times log n. So it's almost square root of n. You have a log factor. With the lazy or lackadaisical quantum walk, when L is 4 over n, what we get is that the runtime has the same scaling, but now your success probability is constant. So you don't have to use amplitude amplification to repeat the algorithm. And so then the total runtime is just root n log n with the log inside the square root as opposed to outside the square root. And so what we see is we actually do get an improvement in the runtime scaling, not just the constant factor. So with the lackadaisical quantum walk, you get an order log n, an order square root of log n speed up. This is all done numerically. I wasn't able to prove this. So this is an open question if you want to work on a proof. Any questions? Yeah, question? OK. All right. So in terms of the graphs that have been explored with the lackadaisical quantum walk, we have the complete graph that I talked about. We have a 2D grid or a torus, as it's talked about, with one marked vertex. Some people have explored different configurations of multiple marked vertices as well. People have also looked at the 1D cycle and this network that has some hierarchy to it. And with my student, again, we looked at the hypercube and some other things. And in all of these graphs, all the self-loops had the same weight. So you had the same amount of laziness everywhere. And the reason for that is because all of these graphs are vertex transitive, meaning every vertex has the same structure. And so there's no structural reason for one vertex to be more lazy than some other vertex. So you have all the weights be the same. That's very reasonable physically. So we were wondering, well, is there a case where you might naturally have different amounts of laziness at different vertices? And I think a very natural example of that is the complete bipartite graph. And this is what my student Mason, Rhodes, and I explored this year. So again, a bipartite graph looks like that. A complete bipartite graph means you have all the edges between them. OK, thank you. OK, good, I have more time. So I'll say there's n1 vertices on the left, n2 vertices on the right. So again, we have two part types sets, n1 and n2 vertices. And every vertex in one set is adjacent to all the vertices in the other because it's complete. And in general, this is not regular. So in general, you can have a different number of vertices in one set versus the other set. And because of that, structurally, these vertices on the left have a different structure from the vertices on the right. And so now it becomes natural to have one amount of laziness for these vertices and some other amount of laziness for these vertices. And so let's call these self-loops weight l1 and these self-loops weight l2. So we have now a lackadaisical quantum walk with different amounts of laziness. All right, so what we'll look at next is we'll look at this case that's not lazy first, and then we'll look at the lazy or lackadaisical case. All right, so let's start with the normal coin quantum walk, not lazy at all. So as a first step, the easiest case would be if you have all your marked vertices in one set. And then later, we'll have marked vertices in both sets. So let's say you have k marked vertices, and they're all in this first set that has size n1. And the initial state here is going to be the following. So all of these edges have the same initial amplitude. So one consequence of this is now this is not a uniform superposition over the vertices. And that's because these vertices have a lot more edges than these vertices here. So these vertices are going to start with a greater initial amplitude. So not all the vertices have the same initial probability now. These actually have a greater probability. If you're curious how the initial state evolves, if you are in a uniform superposition over all the vertices, you can check our paper. But this case that I'm going over here, this is cleaner. So that's what I'll talk about. So here's some simulations of that. So with different values. So say you have three marked vertices in the left set, which has 400 vertices total. And say the right set also has 400 vertices. So what happens is the success probability goes up, reaches a half at this time, and then it goes back down and it's periodic again. Let's say we change the number of vertices in the second set. So instead of 400, let's say it has 200. What you see is we get the exact same evolution. The success probability reaches a half at the same time. And again, if you change the number of vertices in the right set to even just one, you can see these little green dots and it follows the same curve. So what we see is that the number of vertices in the second set doesn't matter. All the marked vertices are in the first set, on the left set. And that does matter. So if we change the number of vertices in the first set, we reach a probability of a half at an earlier runtime, because there's a few vertices in the left set. If we change it even more, if all the vertices in the left set are marked, we're actually just always at a success probability of a half. And so, yeah, so that's what happens. We were able to prove this analytically so that the success probability reaches a half, as you saw in the previous graphs. And the time at which you reach that probability only has N1 and K in it. There's no N2. Again, the number of vertices in the second set doesn't matter. And so again, the only thing that matters in the runtime is the ratio of N1 and K. It's only the first set's properties. Any questions? All right, so now if we have marked vertices in both sets, so say K1 in the left set and K2 in the right set, let's see what happens. So here's some values. So if there's three marked vertices in the left, two marked vertices in the right, and that number in both sets. And one of the things that you'll notice here is that the ratio or the density of marked vertices in each set is the same. I guess you could phrase it like that. And what you find is that, well, let me plot this. So I'm going to plot this as the success probability in the left set separately and then the success probability in the right set so you can see what happens in each set. So the success probability in the left set evolves like this. Again, it reaches a half. The success probability in the right set that has two marked vertices and 400 total vertices evolves like that the same way. And so the total success probability would just be the sum of these two curves, which then of course reaches one. And so what we see here is that because the densities are the same, they end up peaking at the same time and so then you get a total success probability of one. The densities are different. So here I've changed the value. So now the densities are not the same. So I've swapped these two sizes. The first set is going to peak there. The second set on the right is going to peak there at a different time. And so now, of course, if you add them, you won't reach a success probability of one. You'll get something a little bit less. And so we're able to analytically prove this. The runtime in each set, so in the left set, you get a probability of a half. At this time, that only depends on the properties of the left set, the density. And the right set also reaches a success probability of a half. And the time only depends on its density of marked vertices. And so if these two line up, then they add up together, they get a success probability of one. So that's kind of neat. So again, the only thing that matters is what goes on in each set. Otherwise, they evolve independently of each other. Any questions before we get to the lackadaisical versions? All right. OK, so let's make this lackadaisical now. And we'll go back to the first case. That's easier, where you only have K marked vertices in one set. And now you have self-loops with weight L1 here, and self-loops with weight L2 here. So again, they can be different amounts of laziness. Or they could be the same. You can pick the same value on both sides. Doesn't matter. The point is you can now adjust this. All right, so let's see what happens. So just to remind you, with the normal coin quantum walk, it evolves like this. If you make it lackadaisical, let's change L1. So let's say L1 is 0.3. We see that we get a boost in the success probability, which is nice. If we change the L1 some more to 0.6, it gets better still. Make it more lazy, we get that. Make it more lazy, we get that, which reaches 1, which is nice. If you make it more lazy, it goes down. More lazy, it goes down, and down, and down, and so forth. So same story. There's some optimal amount of laziness. And in this case, it's when L1 is 1.2 with these values here. OK, so let's go ahead and, oh, it's more lazy. OK, so it's the best when L1 is 1.2. So let's fix L1 as being 1.2. And now let's see what happens as we vary L2. So this is what we just had before. Now if we change L2 to make that lazy as well, oh, nothing happened. Make L2 even bigger, nothing happens. Make it even bigger, oh, nothing happens. So with marked vertices in the left set, it seems like it doesn't matter how lazy the right set is. It only matters how lazy the left set is. And so we see that L2 doesn't matter here. And so here's another way of visualizing that. So what we did is we varied L1 and we varied L2. And we plotted in color as a heat map the maximum success probability. So you see that the success probability is 1, as long as L1 is 1.2. And then it doesn't matter what L2 is. It's the same thing. So from this, you can see that L2 doesn't matter. Only the left set, where the marked vertices are, matter. And we were able to analytically prove this. So you want L1 to be that, which is 1.2, with the numbers we just had. And then the success probability reaches 1, and the runtime doesn't have N2 in it. It only has what's going on in the left set. Any questions? All right. So now, marked vertices in both sets, k1 in the left, k2 in the right. So with these values, let's just pick different values of laziness. So with no laziness, this is what you would get. It looks a little crazy now, because it's marked vertices in both sets. So they might not add up nicely. If you make it lazy now with, say, L1 is 15, L2 is 5, you do get some improvement here. With these values, L1 is 15, and L2 is 100. It's pretty similar to that. If L1 is 80, and L2 is also 80, you get something that's not very good. And if you look at these, it's kind of hard to compare these. Because even this black curve, I mean, it reaches 1 over here. Like, should we use that peak, or should we use this peak? It's like, how do you compare these? And so a good quantity to look at is the total runtime with classical repetitions, which is basically the idea that if your success probability is, say, 1 half, you have to run the algorithm twice on average before you find your marked vertices. And so the total runtime then is the single runtime divided by your success probability of a single run. And so we can plot that as a heat map here. So this is now the total success probability, which is the total runtime. Sorry, the total runtime, which is the single runtime divided by the success probability. And what you see is that it's not so nice anymore, depending on how lazy each side is. And so the color here is, I picked the middle to correspond to the normal coin quantum walk. So anything that's more yellow, which is less time, which is faster, is better. So we see that if the laziness values are within here, that it's better, but if it's over here, it's worse, and so forth. And in particular, the values that we just saw here, these correspond to these points. So this is the normal coin quantum walk. The red and the green ones where we got an improvement are in this yellow band. And in this blue curve over here, where it's worse is in this dark blue area, which we expect to be worse. And so this is this simulation of what happens. We weren't able to prove this. It's a mess. So that's an open question. If you want to take us, if you want to try that. Here's another example. So here I've actually swapped the number of mark vertices in each set. So before, it's 5 and 2. Now it's 2 and 5. So if we look at that, oh. So again, the middle is the normal quantum walk. And so there's kind of nothing that's better. So at least with these particular values, it seems like there's no improvement with the self-loops, which I thought was kind of surprising. Because if you can pick the weights of the self-loops on each side, it seems like there's got to be some values you can pick to make things better. Because all the previous papers showed that you could do better. And here we're actually showing that for these values, you can't do any better. And here's another set of values where there's the same number of marked vertices in each set, but the sets are different sizes. It looks like this. So you get a little bit of improvement here. But for most values of laziness, you don't get any improvement. And so there's some limited improvement here. And again, this is open for proof, if you want to try proving that. So it's an open question. So just to summarize what we've talked about, we saw that lackadaisical quantum walks spread faster in one dimension-ish, because there is still that central peak. But the two peaks on the side spread faster than a normal coin quantum walk. We see that they improved search for a bunch of problems that were vertex transitive, like the complete graph, the grid, and so forth. And when we apply it to the complete bipartite graph, we do still get an improvement for sure if the marked vertices are only in one set. But if the marked vertices are in both sets, then you might get improvement, or you might not. And exploring that would be some great future work if anyone's interested. And so if you want to see the papers, you can just go to my website, it has all my papers, or you can ask me or email me or something like that, and be happy to take your questions. Thanks for the question. Do you have questions for me? All right, thanks for the nice talk. It's an interesting result that you found. You mentioned in one of your slides that you were just looking at something similar, like a physical quantum walks on the hypercube. And in like around 10 years ago, we did something similar. We extended the SKW search with the self-loops. Are you aware of those? I'm not aware of that work. And if you could email that to me, I'd be really interested. Yeah, OK. Yeah. We should continue in this. Yeah. Although one thing that sounds different is, did we use the same oracle? Because if you use the SKW1, that one uses a different oracle. So we'd have to see how that compares. Yeah, definitely we can talk. Just in your initial model, with one dimension. So the analog of, say, the Hadabard matrix is you're talking about the Grover matrix tree by tree. Well, I guess the analog of the Hadabard matrix would be a Fourier matrix. But I was looking at the Grover coin because I'm specifically interested in search problems. OK. So those parameters you have L and A and B feed into this Fourier matrix? Is for what, sorry? Those parameters, A, B, and the amplitudes, they're part of the Fourier matrix that you're choosing. No, I was just showing how the Grover coin would act if the amplitudes were A, B, and C. OK. Yeah. Just to show that what it does is that it flips around the average if it's unweighted, and if it's weighted, and it does that funny thing. Please. Regarding the 2D letters, you said that you don't use amplitude amplification. So how can you, and you did that numerically, so how can you know numerically that you don't have a square root of log? Yeah. And there is a name multiplying by the log. So the log is hidden by the N. How can you distinguish square root of N log N, log N outside the square root N? I understand. Square root of N log N. Yeah. So if we're fitting a curve, a square root of log factor is very hard to see. And so in that paper, I give plots and try to justify that the fit is correct. I didn't show any of that here. So if you want, we can look over it more closely offline. Yeah. I have another question regarding the truncated simplex lattice. You have an algorithm that search on that lattice, and it seems that it is not square root of N. It is larger than square root of N. Yeah. That was searched with a continuous time. Exactly. Random, a quantum walk. So it's not square root of N? No. Is the first order truncated lattice, is it? So it wasn't square root of N if you have an unweighted graph with a continuous time quantum walk? Is it possible to find a square root of N algorithm in this case? So I was able to get it down to close to square root of N by weighing the edges that connected the clicks. So you have these clicks, right? And then if you weigh the edges that join those clicks, those long distance edges, you are able to improve it. And as the weight increases, the runtime tends towards the square root of N. So I wasn't able to exactly reach square root of N, but it tends towards it. Obtained the story. Yeah. So it like so. OK. Yeah. OK. As the weight increases, then it asymptotically approaches square root of N. And I'll give a quick comment. Historical. So you mentioned child's paper about laser quantum walk, but there is one before, I think it's 2005. OK. By Inui, Kono, and Segawa. I think it's the first one on laser quantum walk. OK. Is that the same as the three state quantum walk? Three state. Yeah. So I didn't talk about the history of the order with which I did this. So I actually didn't look at the 1D line first. I actually looked at search on the complete graph first, and then wrote the paper, submitted it, and then I'm very thankful that the refuge responded saying, oh, this seems very similar to three state quantum walks, which I had never heard of at that time. And so yeah. So basically, I agree that the 1D walk is very similar, but just the way it was developed is kind of from a different perspective that then ends up having a lot of similarities. Thanks for the talk. Could you talk about how robust your search algorithm is to noise? What kind of noise? Any sort of positional noise, coin noise, anything in that regard? Are you talking about deco coherence? Or are you talking about if you just use a different? I would say more decoherence. OK. Any sort of spatial or temporal decoherence? There's been some work on it that I have not done. So I know that maybe experts in this room can comment on that, but that's not something that I know very well. Another question? How familiar are you to this oracle theoretical bounds for oracle searches? And is this, I don't know, does that apply to your scenario? Yeah, it does. So it's still true that the fastest you can search is order square root of n, because of the optimality of Grover's that would still apply, because that has to do with which oracle you use. So we're using the same type of oracle that's in Grover's problem. So you can still only search in the square root of n. Depending on the graph you search on, you may not be able to reach that. So for example, if you search on the one-dimensional line, you actually can't search faster than order n, than a linear n, which means you can't do any better than just randomly guessing for the marketware text. Thanks. So thanks, speaker. Thank you. Thank you.
 Thank you for the introduction.  Thank you to the organizers for inviting me.  So I'll be speaking about some work on spatial search.  So it's an algorithmic application of quantum walks.  And the type of quantum walk I'm going to be using is something called  a lackadaisical quantum walk.  So lackadaisical is just a synonym for lazy.  So it's a lazy quantum walk.  So I'll start by introducing what this is by reviewing what you all have seen  many times in an expert's in, which is the 1D line.  So talk about a normal random walk and then a normal Hadamard quantum walk.  And then what makes a lackadaisical quantum walk different?  After that, we're going to look at some search problems.  So we're going to start with Grover's problem, which is search  on the complete graph.  And then we're going to look at search on the 2D grid.  And then we're going to look at some recent results with one of my undergraduate students  on search on the complete bipartite graph.  If you want to ask questions as we go, feel free.  I'm used to teaching undergrads.  So you can just raise your hand or if I don't see you, just shout out or something.  All right.  But first, before we get to that, it seems like no one knows where Omaha, Nebraska is.  So I thought I'd start with that.  So where is the state of Nebraska?  You want to see it?  I start to see some knots.  People are picking it up.  Yes, it's right there in the middle, in the Midwest, above Kansas.  And Omaha is on the eastern border next to Iowa.  So that's where Omaha, Nebraska is.  Now you know.  So Omaha has a population of about half a million.  If you count all the towns around it, it's a population of about one million.  What is Omaha known for?  Well the biggest thing is Warren Buffett.  So Warren Buffett is a legendary businessman and investor.  So I think he's the fourth richest man in the world.  But he's very generous.  So he's the billionaire who started this challenge to other billionaires to donate most of their  money when they pass away.  Yes, so his company is Berkshire Hathaway, which I think is the fourth largest company  in the world.  And every year they have their shareholders meeting in Omaha.  And so tens of thousands of people from all over the world convene onto our mid-sized city  for this shareholders meeting.  We're also famous for the College World Series, which most of you wouldn't know.  Does anyone know what sport this is?  How about that?  Baseball.  Baseball.  So yeah, it's American.  So the college baseball championship takes place in Omaha every year.  And then finally, we actually have a very good zoo.  So the San Diego Zoo and the Omaha Zoo actually go back and forth as the number one zoo in  America, which you wouldn't expect in Omaha.  All right.  So let's get into the research.  So if you have a quantum walk on the line, as you know, what you do is if your walker  starts in the middle, what he does is he flips a coin.  And if it's heads, then he faces left.  And then if it's tails, he faces right.  And then after that, he takes a step.  And again, you flip a coin.  You face left or you face right.  And you take another step.  And if you repeat this process, as you know, many times, you get this shape.  So this is a binomial distribution.  And the spread of this is quite slow.  It scales as the square root of the number of steps.  OK.  So you guys know this.  And just to be clear, this is using the Hadamard coin and the moving shift.  So if we look at a, sorry, that was Costco, now for the quantum.  So you see the quantum.  So it's the same idea.  So what we'll do is when you flip the coin, we'll flip a quantum coin.  And so now the result can be a superposition of heads and tails.  So you point left and right.  And then when you take your quantum step, you step in a superposition.  So now you're in multiple locations at once.  And you repeat that so that you're in a superposition of heads and tails and a superposition of positions.  And so if we do that a bunch of times, well, here's the classical result we just had.  And now the quantum result, as you know, is this two-peak behavior.  And the spread of this is much faster.  So instead of being stuck around here, you're more likely to be far away at the peaks.  And the standard deviation of this scales linearly in time.  So it's a quadratically faster spread.  And this is some intuition as to why quantum algorithms based on quantum walks might be  faster, because it can spread more quickly.  This is the part that has a Hadamard coin in the moving shift.  So the moving shift means if you're pointing left, or this is your right, if pointing right,  you take a step, you just continue pointing right.  So that's it.  You just move left or right.  All right.  So let's talk about lazy random walks.  So classically, first, lazy random walks are actually really useful algorithmically.  So nothing quantum here.  And just to give you some intuition for why.  Just consider a bipartite graph like this.  So a bipartite graph has two vertex sets.  So there they are circled.  So you see, in each set, they're not connected to each other.  They only connect to vertices in the other set.  And let's say we do a classical random walk where we start with some probability distribution  over the left set.  So if we take a step of the walk, where do we end up?  We end up in the right set.  We take another step of the random walk.  Where do we end up?  We take another step on the left set.  And we see just even with a classical random walk, you only are in one set or the other.  You're not over both.  And so if you want to be in a probability distribution over both sets, what you can  do is you can use a lazy random walk.  So you have some probability of jumping and some probability of staying put.  And if you do that, then you'll get some probability distribution over both sets.  And you might imagine some situations where this might be useful so that you don't just  get trapped in one set or the other.  And so classically, there's a bunch of applications of this that I'm not an expert in, but there's  some citations if you want to look things out.  And so a while back, I was thinking about whether or not there were some quantum analogs  of this.  And so Andrew Childs came up with one in 2010, which he called a lazy quantum walk, which  is quite complicated.  And so when I came up with mine, I needed a different name because lazy quantum walk  was already taken.  So I just looked up, what are synonyms for lazy?  And I picked lackadaisical quantum walk.  This is kind of a fun word, even if it's hard to say.  So lackadaisical quantum walk.  And so the idea here is very simple.  All you do is you add a self-loop at every vertex.  So on the one-dimensional line, it would look like this.  So you have three directions now.  So if you're at the origin, you can point left, or you can point right, or you can point  to yourself so that you stay put.  And so then if you walk, you can walk left, you can walk right, or you can walk in place  and not move at all.  And these are weighted edges.  So that way you can adjust how lazy the walker is.  So if L is bigger, then it's going to be more lazy.  You're going to preferentially stay put.  And if it's smaller, you're less lazy.  All right, so one of the things with this is if we have three directions now, we can't  use the Hadamard coin, because that's only for two directions.  And the coin that we use in search algorithms is called the Grover coin.  And so let me start by reviewing the Grover coin on an unweighted graph.  And so let's look at this left, right, and pointing to yourself with no weight.  So there's no weight L here.  So everything has weight 1, if you will.  So with this normal Grover coin, let's see how it acts on the amplitude.  So let's say you're here and you're pointing left with amplitude A, you're pointing B with  amplitude, sorry, you're pointing right with amplitude B, and you're pointing to yourself  with amplitude C.  So what we're going to do is we're going to let mu be the average of these amplitudes.  So it's literally A plus B plus C divided by 3.  So it's just the average of these amplitudes.  What the Grover coin does is it transforms this state into the following.  So where there was an amplitude A of pointing to the left before, it now becomes 2 times  the average minus A. And then where there was B before, it becomes 2 times the average  minus B. And where there is amplitude C becomes 2 times the average minus C.  And so this transformation actually is an inversion about this average mu.  And so if you learn Grover's algorithm from an introductory course in quantum computing,  one of the operations is an inversion about the mean.  This is exactly that.  So this Grover coin implements an inversion about the mean.  And so if you try to search algorithms, it ends up having that Grover characteristic.  Any questions so far before we get to the lackadaisical version?  OK, so for the lackadaisical version, we need to see what happens on a weighted graph.  So now we have this self-loop with weight L. And the left and right are unweighted.  So they're weight 1.  So let's say the amplitudes again are A, B, and C. And let's see what happens.  So instead of the average of the amplitudes, I'm going to define this quantity mu bar,  which is A plus B. And for C, since it has weight L, it gets multiplied by the square  root of L divided by the sum of the weight.  So this is weight 1, weight 1, weight L. So this is 1 plus 1 plus L.  So this is not the average of the amplitudes anymore.  And what this generalized Grover coin does on a weighted graph is amplitude A becomes  2 times this not average minus A. B becomes 2 times this not average minus B. And C becomes  something a little different.  It's 2 times this average, not not average, times the square root of L minus C.  OK, so what happens is A and B get inverted about this non-average, this whatever it is,  mu bar.  So unweighted edges are inverted about this quantity.  And then C is inverted about this thing times the square root of L. So that acts a little  differently.  And you can generalize this to whatever weighted graphs you want.  So this is actually just a quantum walk on a weighted graph now.  Looking for a picture, OK?  So let's see what happens.  So the reason why the Grover coin is defined like that is because if you use that generalized  Grover coin and you use the flip-flop shift, what you get is a walk that is exactly the  same as Zegadie's quantum Markov chain.  Because with a quantum Markov chain, you have different probabilities of moving one way or  another.  So it's essentially a weighted graph.  So this is the quantum, this is the coin quantum walk equivalent of Zegadie's quantum walk.  The flip-flop shift I haven't talked about yet, so just to quickly go over that as many  of you know.  If you're at this vertex and pointing right, so you're here, you're pointing right, what  you do is you hop and then you turn around.  So you end up here pointing backwards.  So you, you, and then you flip.  So it's a flip-flop shift because you flip your direction.  So that's it.  So using that previous coin on a weighted graph and this shift, you get something that's  exactly the same as Zegadie's quantum walk or quantum Markov chain.  All right.  So with all that, let's see how it acts on the 1D line.  So here's the classical result.  Here's the normal coin quantum walk and the lackadaisical quantum walk is this.  And so what you see is that, okay, yeah, there is some probability of staying very close  to where you started.  But there's also a significant probability of being far from when you started that's  actually even further than a normal quantum walk.  So in some sense, a lackadaisical quantum walk, even though it's lazy, can actually spread  faster-ish because of this middle peak.  And so you might start to wonder, well, are there any algorithmic improvements that you  can make with this property?  The standard deviation of this is still linear in time, but it's a bigger factor in front.  And so we're going to look at some search problems with that.  Pause the moment so people can finish writing.  You're telling me you're a standard grads.  All right, so let's go ahead and do that.  Let's apply this to some algorithmic problems, to some search problems, and see if we can  get any improvements.  So let's start by talking about what this search problem is.  It's called spatial search.  So imagine you're looking for a cafe.  So this is Riga Latvia, where I did my first postdoc, and that's the University of Latvia.  And so imagine you're new to Latvia, and you're looking for a cafe, and you're starting in  front of the university, and you're like, I don't know where a cafe is, but this is Europe.  If I just wander around, I'm sure I'll find a cafe.  So what you can do is you can do a random walk.  So from here, you have three options.  You can go up to the left, you can go up to the right, or you can go down to the right,  and you just randomly pick one.  So let's say you go up to the right.  So up to the left, never mind, very random.  And now here, again, you're like, well, which way should I go?  There's no cafe.  Here you can go up to the left, up to the right, or you could actually go back the way you  came, maybe that way you don't like.  So you randomly pick one, and you end up over there.  Again, you have three choices.  You go over there.  You have more choices now, which way to go, and say you randomly pick that one, and then,  oh, there's a cafe there.  So the idea is you randomly walk.  Go, is your cafe?  No, randomly walk.  Is your cafe?  No, randomly walk.  Is your cafe?  No, randomly walk.  Is your cafe?  Yes, you found your item.  So this is the spatial search problem.  Quantumly, you can do a very similar thing, except with a quantum walk.  So if you start there, now you can walk in superposition.  So you flip your quantum coin, a three-sided coin, and then you walk in superposition, and  now you can end up in all three of those locations.  You do the same thing.  At all those locations, you flip your coin and walk, and you end up in something like  that.  And now you see that there's actually some probability at that cafe that's in the corner.  There's actually another cafe over here, but whatever.  There's actually cafes everywhere.  It's Europe.  Okay.  But this is the idea of spatial search.  So let's get to the particulars of it and how fast these algorithms can be, starting  with the complete graph.  So this corresponds to Grover's algorithm.  So here's an example of a complete graph with six vertices.  In general, we'll have n vertices.  And it's a lackadaisical quantum walk.  We have a self-loop of L everywhere.  And let's just say that's the marked vertex indicated by a double circle.  But the idea is that you don't know that, you're trying to find it.  So there's something to explore in a couple of papers.  And the complete graph corresponds to Grover's problem.  It's this unstructured or this unordered database that Grover's algorithm solves.  Because the idea is there's no order here.  If you read this vertex, you can jump to any other vertex.  There's no constraints as to how you can move.  All right.  So there it is again.  So let's talk specifically about this algorithm, since this is a quantum walk conference.  You guys can see more of what's going on under the hood.  So for the initial state, all of the amplitudes along these internal edges are the same.  So the amplitude of here pointing to there is the same as the amplitude here pointing to there.  And the same as the amplitude here pointing to there.  And all of these internal edges, you start with the same amplitude everywhere.  And then for the self-loops, it's that amplitude, except you multiply it by the score root of L.  Because it has some nice properties and stuff.  A couple of nice properties.  One of them is that this is a uniform superposition over the vertices.  So every vertex has the same total probability.  Because all of these internal edges are the same.  And then they all have the same, all of these self-loops have the same amplitude as well.  So basically every vertex has the same total amount of amplitude, same total amount of probability.  So this is a uniform superposition over all the vertices.  If you were to measure this initial state, you'd get each vertex with probability 1-6 in this case.  Another property of this is that this is a one eigenvector of the quantum walk of the coin in the shift.  So if you applied only the quantum walk to this initial state, nothing happens.  If you want to search, you need to do more than just apply the quantum walk.  You need to query the oracle as well.  You have to ask, am I at a cafe?  So the search algorithm applies the following.  You have an oracle query, and then you do the quantum walk, which is just the Grover coin and the flip-flop shift.  So this constitutes one step, and you're going to repeatedly step through this.  So the Grover coin we talked about, the flip-flop shift we talked about, now let's talk about what the oracle query is.  Any questions?  OK, so the oracle query here is really simple.  All it does is it flips the amplitude at marked vertices.  So just give you an example.  Let's say we have an unmarked vertex here, and it has amplitude A of pointing up, B pointing to the right,  C pointing down, and D pointing to the left.  So if you apply the oracle to this, nothing happens because this is unmarked.  So you skip the exact same thing when you query the oracle.  If it's marked on the other hand, shown by this double circle, then each of these amplitudes, A, B, C, D, become flipped.  So you get minus A, minus B, minus C, and minus D.  So this is the phase flip oracle that you use in Grover's algorithm for whatever problem you're solving.  So it's the same idea here.  So that's it.  So all you do is you apply this phase flip oracle, so the marked vertices get their amplitudes flipped,  and then the Grover coin, and then the flip-flop shift, and you just keep doing that over and over.  That's it for the search algorithm.  So let's see how this searches the complete graph, let's say, with 1024 vertices.  So let's start with no self-loops.  So with no self-loops, or when L is zero, what happens is the success probability starts at 1 over 1024, which is pretty small.  And as you keep applying this query coin shift over and over and over, the success probability builds up.  So more and more probability builds up at your marked vertex until it reaches a peak of a half, and then it's going to go down and then keep going up and down like that.  And so this time at which you reach your max success probability, this is order square root of n, which is Grover's order root n runtime.  Since the success probability is a half, on average you'll have to run the algorithm twice before you find the marked vertex,  but if you double your runtime, it's still order square root of n, so you're fine.  So this is the quantum walk version of Grover's algorithm without lackadaisical, anything like that, just normal coin quantum walk version.  If you make it a lackadaisical quantum walk, let's see what happens.  So instead of L being zero, let's increase L a little bit to 0.1.  And you see that the success probability that you reach, instead of reaching half, you reach a little bit higher value.  If L is 0.2, you reach a higher value still. If L is 0.4, it's even higher.  If L is 0.8, it's almost that one.  Let's keep going, let's clear the graph, so we keep going.  If L is one, you do reach a success probability of one.  If L is greater still, two and a half, oh now it's actually worse.  If it gets more lazy, it's worse again.  If you get more lazy, it's still worse.  And so what we see is that the best amount of laziness is actually, if you increase more, is actually when L equals one.  So for this algorithm, there's some optimal amount of laziness, which could be a life lesson.  And so we do get algorithmic improvements by using a lackadaisical quantum walk.  And you can actually, so yeah, you can search more quickly with a lackadaisical quantum walk.  So you can actually prove all this analytically.  So that's in the paper.  Basically, depending on what value L is, you can find what the runtime and the success probability is.  You don't need to parse through all that.  The idea though is that this is solved.  And basically any question you want to ask, you can get from these results.  So for example, the success probability originally was a half, and then it went up, and then it went back down.  And at some point, it became less than a half again.  So there's some range of L's where you'll do better than a half.  You can use these formulas to figure that out.  And what you can find is that when L is less than roughly 5.8, the success probability is better than a half.  So you can ask whatever question you want like that.  Any questions so far?  All right, so let's jump to the two-dimensional grid or the torus.  And again, say there's n vertices.  And this is a torus, so the boundary conditions wrap around.  So let's see what happens here.  So again, we'll just look at some simulations.  So the normal coin quantum walk, no self-loops, not lazy, looks like this.  So here n is 256.  So the success probability starts at 1 over 256, and it builds up a little bit, and then goes back down and so forth.  So if we make it lazy, let's say L is 0.005.  And now the success probability actually jumps up quite a bit.  It's more lazy.  It jumps up some more.  Make it more lazy.  And oh, it's bad again.  So again, we see the same trend where there's some optimal amount of laziness so that your success probability is boosted as much as possible.  And so with this one, if it's bigger still, it's still worse.  So this optimal amount of laziness is green curve that's 0.015.  This actually corresponds to when L is 4 over n.  And so for example, if we let L be 4 over n, we can pick different values of n, different size grids.  So when n is 256, which is the plot we just had, you get this.  When n is 1024, you get this.  If n is 4096, you get this.  And you basically see that the success probability is constant and it's near 1, which is nice.  And so in terms of runtimes, well, a normal quantum walk that's not lazy,  it's the time to reach that first peak in success probability,  scales as the square root of n log n, and the success probability, so the value of that peak, scales as 1 over log n.  And so if you use amplitude amplification, the total runtime is root n times log n.  So it's almost square root of n.  You have a log factor.  With the lazy or lackadaisical quantum walk, when L is 4 over n, what we get is that the runtime has the same scaling,  but now your success probability is constant.  So you don't have to use amplitude amplification to repeat the algorithm.  And so then the total runtime is just root n log n with the log inside the square root as opposed to outside the square root.  And so what we see is we actually do get an improvement in the runtime scaling, not just the constant factor.  So with the lackadaisical quantum walk, you get an order log n, an order square root of log n speed up.  This is all done numerically.  I wasn't able to prove this.  So this is an open question if you want to work on a proof.  Any questions?  Yeah, question?  OK.  All right.  So in terms of the graphs that have been explored with the lackadaisical quantum walk,  we have the complete graph that I talked about.  We have a 2D grid or a torus, as it's talked about, with one marked vertex.  Some people have explored different configurations of multiple marked vertices as well.  People have also looked at the 1D cycle and this network that has some hierarchy to it.  And with my student, again, we looked at the hypercube and some other things.  And in all of these graphs, all the self-loops had the same weight.  So you had the same amount of laziness everywhere.  And the reason for that is because all of these graphs are vertex transitive,  meaning every vertex has the same structure.  And so there's no structural reason for one vertex  to be more lazy than some other vertex.  So you have all the weights be the same.  That's very reasonable physically.  So we were wondering, well, is there a case where you might naturally have  different amounts of laziness at different vertices?  And I think a very natural example of that is the complete bipartite graph.  And this is what my student Mason, Rhodes, and I explored this year.  So again, a bipartite graph looks like that.  A complete bipartite graph means you have all the edges between them.  OK, thank you.  OK, good, I have more time.  So I'll say there's n1 vertices on the left,  n2 vertices on the right.  So again, we have two part types sets, n1 and n2 vertices.  And every vertex in one set is adjacent to all the vertices in the other  because it's complete.  And in general, this is not regular.  So in general, you can have a different number of vertices in one set  versus the other set.  And because of that, structurally, these vertices on the left  have a different structure from the vertices on the right.  And so now it becomes natural to have one amount of laziness  for these vertices and some other amount of laziness for these vertices.  And so let's call these self-loops weight l1 and these self-loops weight l2.  So we have now a lackadaisical quantum walk with different amounts of laziness.  All right, so what we'll look at next is we'll look at this case that's not lazy  first, and then we'll look at the lazy or lackadaisical case.  All right, so let's start with the normal coin quantum walk, not lazy at all.  So as a first step, the easiest case  would be if you have all your marked vertices in one set.  And then later, we'll have marked vertices in both sets.  So let's say you have k marked vertices,  and they're all in this first set that has size n1.  And the initial state here is going to be the following.  So all of these edges have the same initial amplitude.  So one consequence of this is now this is not a uniform superposition over the vertices.  And that's because these vertices have a lot more edges than these vertices here.  So these vertices are going to start with a greater initial amplitude.  So not all the vertices have the same initial probability now.  These actually have a greater probability.  If you're curious how the initial state evolves,  if you are in a uniform superposition over all the vertices,  you can check our paper.  But this case that I'm going over here, this is cleaner.  So that's what I'll talk about.  So here's some simulations of that.  So with different values.  So say you have three marked vertices in the left set,  which has 400 vertices total.  And say the right set also has 400 vertices.  So what happens is the success probability goes up,  reaches a half at this time, and then it goes back down and it's periodic again.  Let's say we change the number of vertices in the second set.  So instead of 400, let's say it has 200.  What you see is we get the exact same evolution.  The success probability reaches a half at the same time.  And again, if you change the number of vertices in the right set to even just one,  you can see these little green dots and it follows the same curve.  So what we see is that the number of vertices in the second set doesn't matter.  All the marked vertices are in the first set, on the left set.  And that does matter.  So if we change the number of vertices in the first set,  we reach a probability of a half at an earlier runtime,  because there's a few vertices in the left set.  If we change it even more, if all the vertices in the left set are marked,  we're actually just always at a success probability of a half.  And so, yeah, so that's what happens.  We were able to prove this analytically so that the success probability reaches a half,  as you saw in the previous graphs.  And the time at which you reach that probability only has N1 and K in it.  There's no N2.  Again, the number of vertices in the second set doesn't matter.  And so again, the only thing that matters in the runtime is the ratio of N1 and K.  It's only the first set's properties.  Any questions?  All right, so now if we have marked vertices in both sets,  so say K1 in the left set and K2 in the right set, let's see what happens.  So here's some values.  So if there's three marked vertices in the left, two marked vertices in the right,  and that number in both sets.  And one of the things that you'll notice here is that the ratio or the density of marked vertices in each set is the same.  I guess you could phrase it like that.  And what you find is that, well, let me plot this.  So I'm going to plot this as the success probability in the left set separately  and then the success probability in the right set so you can see what happens in each set.  So the success probability in the left set evolves like this.  Again, it reaches a half.  The success probability in the right set that has two marked vertices and 400 total vertices  evolves like that the same way.  And so the total success probability would just be the sum of these two curves,  which then of course reaches one.  And so what we see here is that because the densities are the same,  they end up peaking at the same time and so then you get a total success probability of one.  The densities are different.  So here I've changed the value.  So now the densities are not the same.  So I've swapped these two sizes.  The first set is going to peak there.  The second set on the right is going to peak there at a different time.  And so now, of course, if you add them, you won't reach a success probability of one.  You'll get something a little bit less.  And so we're able to analytically prove this.  The runtime in each set, so in the left set, you get a probability of a half.  At this time, that only depends on the properties of the left set, the density.  And the right set also reaches a success probability of a half.  And the time only depends on its density of marked vertices.  And so if these two line up, then they add up together,  they get a success probability of one.  So that's kind of neat.  So again, the only thing that matters is what goes on in each set.  Otherwise, they evolve independently of each other.  Any questions before we get to the lackadaisical versions?  All right.  OK, so let's make this lackadaisical now.  And we'll go back to the first case.  That's easier, where you only have K marked vertices in one set.  And now you have self-loops with weight L1 here, and self-loops with weight L2 here.  So again, they can be different amounts of laziness.  Or they could be the same.  You can pick the same value on both sides.  Doesn't matter.  The point is you can now adjust this.  All right, so let's see what happens.  So just to remind you, with the normal coin quantum walk,  it evolves like this.  If you make it lackadaisical, let's change L1.  So let's say L1 is 0.3.  We see that we get a boost in the success probability, which is nice.  If we change the L1 some more to 0.6, it gets better still.  Make it more lazy, we get that.  Make it more lazy, we get that, which reaches 1, which is nice.  If you make it more lazy, it goes down.  More lazy, it goes down, and down, and down, and so forth.  So same story.  There's some optimal amount of laziness.  And in this case, it's when L1 is 1.2 with these values here.  OK, so let's go ahead and, oh, it's more lazy.  OK, so it's the best when L1 is 1.2.  So let's fix L1 as being 1.2.  And now let's see what happens as we vary L2.  So this is what we just had before.  Now if we change L2 to make that lazy as well,  oh, nothing happened.  Make L2 even bigger, nothing happens.  Make it even bigger, oh, nothing happens.  So with marked vertices in the left set,  it seems like it doesn't matter how lazy the right set is.  It only matters how lazy the left set is.  And so we see that L2 doesn't matter here.  And so here's another way of visualizing that.  So what we did is we varied L1 and we varied L2.  And we plotted in color as a heat map the maximum success  probability.  So you see that the success probability is 1,  as long as L1 is 1.2.  And then it doesn't matter what L2 is.  It's the same thing.  So from this, you can see that L2 doesn't matter.  Only the left set, where the marked vertices are, matter.  And we were able to analytically prove this.  So you want L1 to be that, which is 1.2,  with the numbers we just had.  And then the success probability reaches 1,  and the runtime doesn't have N2 in it.  It only has what's going on in the left set.  Any questions?  All right.  So now, marked vertices in both sets,  k1 in the left, k2 in the right.  So with these values, let's just pick different values  of laziness.  So with no laziness, this is what you would get.  It looks a little crazy now, because it's marked vertices  in both sets.  So they might not add up nicely.  If you make it lazy now with, say, L1 is 15, L2 is 5,  you do get some improvement here.  With these values, L1 is 15, and L2 is 100.  It's pretty similar to that.  If L1 is 80, and L2 is also 80, you  get something that's not very good.  And if you look at these, it's kind of hard to compare these.  Because even this black curve, I mean, it reaches 1 over here.  Like, should we use that peak, or should we use this peak?  It's like, how do you compare these?  And so a good quantity to look at is the total runtime  with classical repetitions, which is basically the idea that  if your success probability is, say, 1 half,  you have to run the algorithm twice on average  before you find your marked vertices.  And so the total runtime then is the single runtime  divided by your success probability of a single run.  And so we can plot that as a heat map here.  So this is now the total success probability, which  is the total runtime.  Sorry, the total runtime, which is the single runtime  divided by the success probability.  And what you see is that it's not so nice anymore,  depending on how lazy each side is.  And so the color here is, I picked the middle to correspond  to the normal coin quantum walk.  So anything that's more yellow, which is less time, which  is faster, is better.  So we see that if the laziness values are within here,  that it's better, but if it's over here, it's worse,  and so forth.  And in particular, the values that we just saw here,  these correspond to these points.  So this is the normal coin quantum walk.  The red and the green ones where we got an improvement  are in this yellow band.  And in this blue curve over here,  where it's worse is in this dark blue area,  which we expect to be worse.  And so this is this simulation of what happens.  We weren't able to prove this.  It's a mess.  So that's an open question.  If you want to take us, if you want to try that.  Here's another example.  So here I've actually swapped the number of mark vertices  in each set.  So before, it's 5 and 2.  Now it's 2 and 5.  So if we look at that, oh.  So again, the middle is the normal quantum walk.  And so there's kind of nothing that's better.  So at least with these particular values,  it seems like there's no improvement with the self-loops,  which I thought was kind of surprising.  Because if you can pick the weights of the self-loops  on each side, it seems like there's  got to be some values you can pick to make things better.  Because all the previous papers showed that you could do better.  And here we're actually showing that for these values,  you can't do any better.  And here's another set of values where  there's the same number of marked vertices in each set,  but the sets are different sizes.  It looks like this.  So you get a little bit of improvement here.  But for most values of laziness, you don't get any improvement.  And so there's some limited improvement here.  And again, this is open for proof,  if you want to try proving that.  So it's an open question.  So just to summarize what we've talked about,  we saw that lackadaisical quantum walks spread faster  in one dimension-ish, because there is still that central peak.  But the two peaks on the side spread faster  than a normal coin quantum walk.  We see that they improved search for a bunch of problems  that were vertex transitive, like the complete graph,  the grid, and so forth.  And when we apply it to the complete bipartite graph,  we do still get an improvement for sure  if the marked vertices are only in one set.  But if the marked vertices are in both sets,  then you might get improvement, or you might not.  And exploring that would be some great future work  if anyone's interested.  And so if you want to see the papers,  you can just go to my website, it has all my papers,  or you can ask me or email me or something like that,  and be happy to take your questions.  Thanks for the question.  Do you have questions for me?  All right, thanks for the nice talk.  It's an interesting result that you found.  You mentioned in one of your slides  that you were just looking at something similar,  like a physical quantum walks on the hypercube.  And in like around 10 years ago, we did something similar.  We extended the SKW search with the self-loops.  Are you aware of those?  I'm not aware of that work.  And if you could email that to me, I'd be really interested.  Yeah, OK.  Yeah.  We should continue in this.  Yeah.  Although one thing that sounds different is,  did we use the same oracle?  Because if you use the SKW1, that one  uses a different oracle.  So we'd have to see how that compares.  Yeah, definitely we can talk.  Just in your initial model, with one dimension.  So the analog of, say, the Hadabard matrix  is you're talking about the Grover matrix tree by tree.  Well, I guess the analog of the Hadabard matrix  would be a Fourier matrix.  But I was looking at the Grover coin  because I'm specifically interested in search problems.  OK.  So those parameters you have L and A and B  feed into this Fourier matrix?  Is for what, sorry?  Those parameters, A, B, and the amplitudes,  they're part of the Fourier matrix that you're choosing.  No, I was just showing how the Grover coin would  act if the amplitudes were A, B, and C.  OK.  Yeah.  Just to show that what it does is that it  flips around the average if it's unweighted,  and if it's weighted, and it does that funny thing.  Please.  Regarding the 2D letters, you said that you don't use  amplitude amplification.  So how can you, and you did that numerically,  so how can you know numerically that you don't have  a square root of log?  Yeah.  And there is a name multiplying by the log.  So the log is hidden by the N. How can you distinguish  square root of N log N, log N outside the square root N?  I understand.  Square root of N log N.  Yeah.  So if we're fitting a curve, a square root of log factor  is very hard to see.  And so in that paper, I give plots  and try to justify that the fit is correct.  I didn't show any of that here.  So if you want, we can look over it more closely offline.  Yeah.  I have another question regarding the truncated simplex  lattice.  You have an algorithm that search on that lattice,  and it seems that it is not square root of N.  It is larger than square root of N.  Yeah.  That was searched with a continuous time.  Exactly.  Random, a quantum walk.  So it's not square root of N?  No.  Is the first order truncated lattice, is it?  So it wasn't square root of N if you have an unweighted graph  with a continuous time quantum walk?  Is it possible to find a square root of N algorithm  in this case?  So I was able to get it down to close to square root of N  by weighing the edges that connected the clicks.  So you have these clicks, right?  And then if you weigh the edges that join those clicks,  those long distance edges, you are able to improve it.  And as the weight increases, the runtime  tends towards the square root of N.  So I wasn't able to exactly reach square root of N,  but it tends towards it.  Obtained the story.  Yeah.  So it like so.  OK.  Yeah.  OK.  As the weight increases, then it asymptotically approaches  square root of N.  And I'll give a quick comment.  Historical.  So you mentioned child's paper about laser quantum walk,  but there is one before, I think it's 2005.  OK.  By Inui, Kono, and Segawa.  I think it's the first one on laser quantum walk.  OK.  Is that the same as the three state quantum walk?  Three state.  Yeah.  So I didn't talk about the history of the order with which  I did this.  So I actually didn't look at the 1D line first.  I actually looked at search on the complete graph first,  and then wrote the paper, submitted it,  and then I'm very thankful that the refuge responded saying,  oh, this seems very similar to three state quantum walks,  which I had never heard of at that time.  And so yeah.  So basically, I agree that the 1D walk is very similar,  but just the way it was developed  is kind of from a different perspective  that then ends up having a lot of similarities.  Thanks for the talk.  Could you talk about how robust your search algorithm is  to noise?  What kind of noise?  Any sort of positional noise, coin noise, anything  in that regard?  Are you talking about deco coherence?  Or are you talking about if you just use a different?  I would say more decoherence.  OK.  Any sort of spatial or temporal decoherence?  There's been some work on it that I have not done.  So I know that maybe experts in this room can comment on that,  but that's not something that I know very well.  Another question?  How familiar are you to this oracle theoretical bounds  for oracle searches?  And is this, I don't know, does that  apply to your scenario?  Yeah, it does.  So it's still true that the fastest you can search  is order square root of n, because of the optimality of Grover's  that would still apply, because that  has to do with which oracle you use.  So we're using the same type of oracle that's  in Grover's problem.  So you can still only search in the square root of n.  Depending on the graph you search on,  you may not be able to reach that.  So for example, if you search on the one-dimensional line,  you actually can't search faster than order n,  than a linear n, which means you can't do any better  than just randomly guessing for the marketware text.  Thanks.  So thanks, speaker.  Thank you.  Thank you.
2020-01-23_Wong_0_47.png 2020-01-23_Wong_48_95.png 2020-01-23_Wong_96_155.png 2020-01-23_Wong_156_203.png 2020-01-23_Wong_204_275.png 2020-01-23_Wong_276_395.png 2020-01-23_Wong_396_2879.png 2020-01-23_Wong_2880_4523.png 2020-01-23_Wong_4524_6119.png 2020-01-23_Wong_6120_6179.png 2020-01-23_Wong_6180_6311.png 2020-01-23_Wong_6312_9935.png 2020-01-23_Wong_9936_10343.png 2020-01-23_Wong_10344_17687.png 2020-01-23_Wong_17688_17843.png 2020-01-23_Wong_17844_19799.png 2020-01-23_Wong_19800_22559.png 2020-01-23_Wong_22560_26531.png 2020-01-23_Wong_26532_31259.png 2020-01-23_Wong_31260_31355.png 2020-01-23_Wong_31356_32543.png 2020-01-23_Wong_32544_32939.png 2020-01-23_Wong_32940_33155.png 2020-01-23_Wong_33156_34943.png 2020-01-23_Wong_34944_35375.png 2020-01-23_Wong_35376_35567.png 2020-01-23_Wong_35568_37031.png 2020-01-23_Wong_37032_38339.png 2020-01-23_Wong_38340_45611.png 2020-01-23_Wong_45612_45659.png 2020-01-23_Wong_45660_46355.png 2020-01-23_Wong_46356_52787.png 2020-01-23_Wong_52788_52895.png 2020-01-23_Wong_52896_55979.png 2020-01-23_Wong_55980_56039.png 2020-01-23_Wong_56040_58091.png 2020-01-23_Wong_58092_61235.png 2020-01-23_Wong_61236_64187.png 2020-01-23_Wong_64188_64307.png 2020-01-23_Wong_64308_64475.png 2020-01-23_Wong_64476_69395.png 2020-01-23_Wong_69396_69647.png 2020-01-23_Wong_69648_70319.png 2020-01-23_Wong_70320_70391.png 2020-01-23_Wong_70392_70439.png 2020-01-23_Wong_70440_70550.png
Thank you for the introduction. Thank you to the organizers for inviting me. So I'll be speaking about some work on spatial search. So it's an algorithmic application of quantum walks. And the type of quantum walk I'm going to be using is something called a lackadaisical quantum walk. So lackadaisical is just a synonym for lazy. So it's a lazy quantum walk. So I'll start by introducing what this is by reviewing what you all have seen many times in an expert's in, which is the 1D line. So talk about a normal random walk and then a normal Hadamard quantum walk. And then what makes a lackadaisical quantum walk different? After that, we're going to look at some search problems. So we're going to start with Grover's problem, which is search on the complete graph. And then we're going to look at search on the 2D grid. And then we're going to look at some recent results with one of my undergraduate students on search on the complete bipartite graph. If you want to ask questions as we go, feel free. I'm used to teaching undergrads. So you can just raise your hand or if I don't see you, just shout out or something. All right. But first, before we get to that, it seems like no one knows where Omaha, Nebraska is. So I thought I'd start with that. So where is the state of Nebraska? You want to see it? I start to see some knots. People are picking it up. Yes, it's right there in the middle, in the Midwest, above Kansas. And Omaha is on the eastern border next to Iowa. So that's where Omaha, Nebraska is. Now you know. So Omaha has a population of about half a million. If you count all the towns around it, it's a population of about one million. What is Omaha known for? Well the biggest thing is Warren Buffett. So Warren Buffett is a legendary businessman and investor. So I think he's the fourth richest man in the world. But he's very generous. So he's the billionaire who started this challenge to other billionaires to donate most of their money when they pass away. Yes, so his company is Berkshire Hathaway, which I think is the fourth largest company in the world. And every year they have their shareholders meeting in Omaha. And so tens of thousands of people from all over the world convene onto our mid-sized city for this shareholders meeting. We're also famous for the College World Series, which most of you wouldn't know. Does anyone know what sport this is? How about that? Baseball. Baseball. So yeah, it's American. So the college baseball championship takes place in Omaha every year. And then finally, we actually have a very good zoo. So the San Diego Zoo and the Omaha Zoo actually go back and forth as the number one zoo in America, which you wouldn't expect in Omaha. All right. So let's get into the research. So if you have a quantum walk on the line, as you know, what you do is if your walker starts in the middle, what he does is he flips a coin. And if it's heads, then he faces left. And then if it's tails, he faces right. And then after that, he takes a step. And again, you flip a coin. You face left or you face right. And you take another step. And if you repeat this process, as you know, many times, you get this shape. So this is a binomial distribution. And the spread of this is quite slow. It scales as the square root of the number of steps. OK. So you guys know this. And just to be clear, this is using the Hadamard coin and the moving shift. So if we look at a, sorry, that was Costco, now for the quantum. So you see the quantum. So it's the same idea. So what we'll do is when you flip the coin, we'll flip a quantum coin. And so now the result can be a superposition of heads and tails. So you point left and right. And then when you take your quantum step, you step in a superposition. So now you're in multiple locations at once. And you repeat that so that you're in a superposition of heads and tails and a superposition of positions. And so if we do that a bunch of times, well, here's the classical result we just had. And now the quantum result, as you know, is this two-peak behavior. And the spread of this is much faster. So instead of being stuck around here, you're more likely to be far away at the peaks. And the standard deviation of this scales linearly in time. So it's a quadratically faster spread. And this is some intuition as to why quantum algorithms based on quantum walks might be faster, because it can spread more quickly. This is the part that has a Hadamard coin in the moving shift. So the moving shift means if you're pointing left, or this is your right, if pointing right, you take a step, you just continue pointing right. So that's it. You just move left or right. All right. So let's talk about lazy random walks. So classically, first, lazy random walks are actually really useful algorithmically. So nothing quantum here. And just to give you some intuition for why. Just consider a bipartite graph like this. So a bipartite graph has two vertex sets. So there they are circled. So you see, in each set, they're not connected to each other. They only connect to vertices in the other set. And let's say we do a classical random walk where we start with some probability distribution over the left set. So if we take a step of the walk, where do we end up? We end up in the right set. We take another step of the random walk. Where do we end up? We take another step on the left set. And we see just even with a classical random walk, you only are in one set or the other. You're not over both. And so if you want to be in a probability distribution over both sets, what you can do is you can use a lazy random walk. So you have some probability of jumping and some probability of staying put. And if you do that, then you'll get some probability distribution over both sets. And you might imagine some situations where this might be useful so that you don't just get trapped in one set or the other. And so classically, there's a bunch of applications of this that I'm not an expert in, but there's some citations if you want to look things out. And so a while back, I was thinking about whether or not there were some quantum analogs of this. And so Andrew Childs came up with one in 2010, which he called a lazy quantum walk, which is quite complicated. And so when I came up with mine, I needed a different name because lazy quantum walk was already taken. So I just looked up, what are synonyms for lazy? And I picked lackadaisical quantum walk. This is kind of a fun word, even if it's hard to say. So lackadaisical quantum walk. And so the idea here is very simple. All you do is you add a self-loop at every vertex. So on the one-dimensional line, it would look like this. So you have three directions now. So if you're at the origin, you can point left, or you can point right, or you can point to yourself so that you stay put. And so then if you walk, you can walk left, you can walk right, or you can walk in place and not move at all. And these are weighted edges. So that way you can adjust how lazy the walker is. So if L is bigger, then it's going to be more lazy. You're going to preferentially stay put. And if it's smaller, you're less lazy. All right, so one of the things with this is if we have three directions now, we can't use the Hadamard coin, because that's only for two directions. And the coin that we use in search algorithms is called the Grover coin. And so let me start by reviewing the Grover coin on an unweighted graph. And so let's look at this left, right, and pointing to yourself with no weight. So there's no weight L here. So everything has weight 1, if you will. So with this normal Grover coin, let's see how it acts on the amplitude. So let's say you're here and you're pointing left with amplitude A, you're pointing B with amplitude, sorry, you're pointing right with amplitude B, and you're pointing to yourself with amplitude C. So what we're going to do is we're going to let mu be the average of these amplitudes. So it's literally A plus B plus C divided by 3. So it's just the average of these amplitudes. What the Grover coin does is it transforms this state into the following. So where there was an amplitude A of pointing to the left before, it now becomes 2 times the average minus A. And then where there was B before, it becomes 2 times the average minus B. And where there is amplitude C becomes 2 times the average minus C. And so this transformation actually is an inversion about this average mu. And so if you learn Grover's algorithm from an introductory course in quantum computing, one of the operations is an inversion about the mean. This is exactly that. So this Grover coin implements an inversion about the mean. And so if you try to search algorithms, it ends up having that Grover characteristic. Any questions so far before we get to the lackadaisical version? OK, so for the lackadaisical version, we need to see what happens on a weighted graph. So now we have this self-loop with weight L. And the left and right are unweighted. So they're weight 1. So let's say the amplitudes again are A, B, and C. And let's see what happens. So instead of the average of the amplitudes, I'm going to define this quantity mu bar, which is A plus B. And for C, since it has weight L, it gets multiplied by the square root of L divided by the sum of the weight. So this is weight 1, weight 1, weight L. So this is 1 plus 1 plus L. So this is not the average of the amplitudes anymore. And what this generalized Grover coin does on a weighted graph is amplitude A becomes 2 times this not average minus A. B becomes 2 times this not average minus B. And C becomes something a little different. It's 2 times this average, not not average, times the square root of L minus C. OK, so what happens is A and B get inverted about this non-average, this whatever it is, mu bar. So unweighted edges are inverted about this quantity. And then C is inverted about this thing times the square root of L. So that acts a little differently. And you can generalize this to whatever weighted graphs you want. So this is actually just a quantum walk on a weighted graph now. Looking for a picture, OK? So let's see what happens. So the reason why the Grover coin is defined like that is because if you use that generalized Grover coin and you use the flip-flop shift, what you get is a walk that is exactly the same as Zegadie's quantum Markov chain. Because with a quantum Markov chain, you have different probabilities of moving one way or another. So it's essentially a weighted graph. So this is the quantum, this is the coin quantum walk equivalent of Zegadie's quantum walk. The flip-flop shift I haven't talked about yet, so just to quickly go over that as many of you know. If you're at this vertex and pointing right, so you're here, you're pointing right, what you do is you hop and then you turn around. So you end up here pointing backwards. So you, you, and then you flip. So it's a flip-flop shift because you flip your direction. So that's it. So using that previous coin on a weighted graph and this shift, you get something that's exactly the same as Zegadie's quantum walk or quantum Markov chain. All right. So with all that, let's see how it acts on the 1D line. So here's the classical result. Here's the normal coin quantum walk and the lackadaisical quantum walk is this. And so what you see is that, okay, yeah, there is some probability of staying very close to where you started. But there's also a significant probability of being far from when you started that's actually even further than a normal quantum walk. So in some sense, a lackadaisical quantum walk, even though it's lazy, can actually spread faster-ish because of this middle peak. And so you might start to wonder, well, are there any algorithmic improvements that you can make with this property? The standard deviation of this is still linear in time, but it's a bigger factor in front. And so we're going to look at some search problems with that. Pause the moment so people can finish writing. You're telling me you're a standard grads. All right, so let's go ahead and do that. Let's apply this to some algorithmic problems, to some search problems, and see if we can get any improvements. So let's start by talking about what this search problem is. It's called spatial search. So imagine you're looking for a cafe. So this is Riga Latvia, where I did my first postdoc, and that's the University of Latvia. And so imagine you're new to Latvia, and you're looking for a cafe, and you're starting in front of the university, and you're like, I don't know where a cafe is, but this is Europe. If I just wander around, I'm sure I'll find a cafe. So what you can do is you can do a random walk. So from here, you have three options. You can go up to the left, you can go up to the right, or you can go down to the right, and you just randomly pick one. So let's say you go up to the right. So up to the left, never mind, very random. And now here, again, you're like, well, which way should I go? There's no cafe. Here you can go up to the left, up to the right, or you could actually go back the way you came, maybe that way you don't like. So you randomly pick one, and you end up over there. Again, you have three choices. You go over there. You have more choices now, which way to go, and say you randomly pick that one, and then, oh, there's a cafe there. So the idea is you randomly walk. Go, is your cafe? No, randomly walk. Is your cafe? No, randomly walk. Is your cafe? No, randomly walk. Is your cafe? Yes, you found your item. So this is the spatial search problem. Quantumly, you can do a very similar thing, except with a quantum walk. So if you start there, now you can walk in superposition. So you flip your quantum coin, a three-sided coin, and then you walk in superposition, and now you can end up in all three of those locations. You do the same thing. At all those locations, you flip your coin and walk, and you end up in something like that. And now you see that there's actually some probability at that cafe that's in the corner. There's actually another cafe over here, but whatever. There's actually cafes everywhere. It's Europe. Okay. But this is the idea of spatial search. So let's get to the particulars of it and how fast these algorithms can be, starting with the complete graph. So this corresponds to Grover's algorithm. So here's an example of a complete graph with six vertices. In general, we'll have n vertices. And it's a lackadaisical quantum walk. We have a self-loop of L everywhere. And let's just say that's the marked vertex indicated by a double circle. But the idea is that you don't know that, you're trying to find it. So there's something to explore in a couple of papers. And the complete graph corresponds to Grover's problem. It's this unstructured or this unordered database that Grover's algorithm solves. Because the idea is there's no order here. If you read this vertex, you can jump to any other vertex. There's no constraints as to how you can move. All right. So there it is again. So let's talk specifically about this algorithm, since this is a quantum walk conference. You guys can see more of what's going on under the hood. So for the initial state, all of the amplitudes along these internal edges are the same. So the amplitude of here pointing to there is the same as the amplitude here pointing to there. And the same as the amplitude here pointing to there. And all of these internal edges, you start with the same amplitude everywhere. And then for the self-loops, it's that amplitude, except you multiply it by the score root of L. Because it has some nice properties and stuff. A couple of nice properties. One of them is that this is a uniform superposition over the vertices. So every vertex has the same total probability. Because all of these internal edges are the same. And then they all have the same, all of these self-loops have the same amplitude as well. So basically every vertex has the same total amount of amplitude, same total amount of probability. So this is a uniform superposition over all the vertices. If you were to measure this initial state, you'd get each vertex with probability 1-6 in this case. Another property of this is that this is a one eigenvector of the quantum walk of the coin in the shift. So if you applied only the quantum walk to this initial state, nothing happens. If you want to search, you need to do more than just apply the quantum walk. You need to query the oracle as well. You have to ask, am I at a cafe? So the search algorithm applies the following. You have an oracle query, and then you do the quantum walk, which is just the Grover coin and the flip-flop shift. So this constitutes one step, and you're going to repeatedly step through this. So the Grover coin we talked about, the flip-flop shift we talked about, now let's talk about what the oracle query is. Any questions? OK, so the oracle query here is really simple. All it does is it flips the amplitude at marked vertices. So just give you an example. Let's say we have an unmarked vertex here, and it has amplitude A of pointing up, B pointing to the right, C pointing down, and D pointing to the left. So if you apply the oracle to this, nothing happens because this is unmarked. So you skip the exact same thing when you query the oracle. If it's marked on the other hand, shown by this double circle, then each of these amplitudes, A, B, C, D, become flipped. So you get minus A, minus B, minus C, and minus D. So this is the phase flip oracle that you use in Grover's algorithm for whatever problem you're solving. So it's the same idea here. So that's it. So all you do is you apply this phase flip oracle, so the marked vertices get their amplitudes flipped, and then the Grover coin, and then the flip-flop shift, and you just keep doing that over and over. That's it for the search algorithm. So let's see how this searches the complete graph, let's say, with 1024 vertices. So let's start with no self-loops. So with no self-loops, or when L is zero, what happens is the success probability starts at 1 over 1024, which is pretty small. And as you keep applying this query coin shift over and over and over, the success probability builds up. So more and more probability builds up at your marked vertex until it reaches a peak of a half, and then it's going to go down and then keep going up and down like that. And so this time at which you reach your max success probability, this is order square root of n, which is Grover's order root n runtime. Since the success probability is a half, on average you'll have to run the algorithm twice before you find the marked vertex, but if you double your runtime, it's still order square root of n, so you're fine. So this is the quantum walk version of Grover's algorithm without lackadaisical, anything like that, just normal coin quantum walk version. If you make it a lackadaisical quantum walk, let's see what happens. So instead of L being zero, let's increase L a little bit to 0.1. And you see that the success probability that you reach, instead of reaching half, you reach a little bit higher value. If L is 0.2, you reach a higher value still. If L is 0.4, it's even higher. If L is 0.8, it's almost that one. Let's keep going, let's clear the graph, so we keep going. If L is one, you do reach a success probability of one. If L is greater still, two and a half, oh now it's actually worse. If it gets more lazy, it's worse again. If you get more lazy, it's still worse. And so what we see is that the best amount of laziness is actually, if you increase more, is actually when L equals one. So for this algorithm, there's some optimal amount of laziness, which could be a life lesson. And so we do get algorithmic improvements by using a lackadaisical quantum walk. And you can actually, so yeah, you can search more quickly with a lackadaisical quantum walk. So you can actually prove all this analytically. So that's in the paper. Basically, depending on what value L is, you can find what the runtime and the success probability is. You don't need to parse through all that. The idea though is that this is solved. And basically any question you want to ask, you can get from these results. So for example, the success probability originally was a half, and then it went up, and then it went back down. And at some point, it became less than a half again. So there's some range of L's where you'll do better than a half. You can use these formulas to figure that out. And what you can find is that when L is less than roughly 5.8, the success probability is better than a half. So you can ask whatever question you want like that. Any questions so far? All right, so let's jump to the two-dimensional grid or the torus. And again, say there's n vertices. And this is a torus, so the boundary conditions wrap around. So let's see what happens here. So again, we'll just look at some simulations. So the normal coin quantum walk, no self-loops, not lazy, looks like this. So here n is 256. So the success probability starts at 1 over 256, and it builds up a little bit, and then goes back down and so forth. So if we make it lazy, let's say L is 0.005. And now the success probability actually jumps up quite a bit. It's more lazy. It jumps up some more. Make it more lazy. And oh, it's bad again. So again, we see the same trend where there's some optimal amount of laziness so that your success probability is boosted as much as possible. And so with this one, if it's bigger still, it's still worse. So this optimal amount of laziness is green curve that's 0.015. This actually corresponds to when L is 4 over n. And so for example, if we let L be 4 over n, we can pick different values of n, different size grids. So when n is 256, which is the plot we just had, you get this. When n is 1024, you get this. If n is 4096, you get this. And you basically see that the success probability is constant and it's near 1, which is nice. And so in terms of runtimes, well, a normal quantum walk that's not lazy, it's the time to reach that first peak in success probability, scales as the square root of n log n, and the success probability, so the value of that peak, scales as 1 over log n. And so if you use amplitude amplification, the total runtime is root n times log n. So it's almost square root of n. You have a log factor. With the lazy or lackadaisical quantum walk, when L is 4 over n, what we get is that the runtime has the same scaling, but now your success probability is constant. So you don't have to use amplitude amplification to repeat the algorithm. And so then the total runtime is just root n log n with the log inside the square root as opposed to outside the square root. And so what we see is we actually do get an improvement in the runtime scaling, not just the constant factor. So with the lackadaisical quantum walk, you get an order log n, an order square root of log n speed up. This is all done numerically. I wasn't able to prove this. So this is an open question if you want to work on a proof. Any questions? Yeah, question? OK. All right. So in terms of the graphs that have been explored with the lackadaisical quantum walk, we have the complete graph that I talked about. We have a 2D grid or a torus, as it's talked about, with one marked vertex. Some people have explored different configurations of multiple marked vertices as well. People have also looked at the 1D cycle and this network that has some hierarchy to it. And with my student, again, we looked at the hypercube and some other things. And in all of these graphs, all the self-loops had the same weight. So you had the same amount of laziness everywhere. And the reason for that is because all of these graphs are vertex transitive, meaning every vertex has the same structure. And so there's no structural reason for one vertex to be more lazy than some other vertex. So you have all the weights be the same. That's very reasonable physically. So we were wondering, well, is there a case where you might naturally have different amounts of laziness at different vertices? And I think a very natural example of that is the complete bipartite graph. And this is what my student Mason, Rhodes, and I explored this year. So again, a bipartite graph looks like that. A complete bipartite graph means you have all the edges between them. OK, thank you. OK, good, I have more time. So I'll say there's n1 vertices on the left, n2 vertices on the right. So again, we have two part types sets, n1 and n2 vertices. And every vertex in one set is adjacent to all the vertices in the other because it's complete. And in general, this is not regular. So in general, you can have a different number of vertices in one set versus the other set. And because of that, structurally, these vertices on the left have a different structure from the vertices on the right. And so now it becomes natural to have one amount of laziness for these vertices and some other amount of laziness for these vertices. And so let's call these self-loops weight l1 and these self-loops weight l2. So we have now a lackadaisical quantum walk with different amounts of laziness. All right, so what we'll look at next is we'll look at this case that's not lazy first, and then we'll look at the lazy or lackadaisical case. All right, so let's start with the normal coin quantum walk, not lazy at all. So as a first step, the easiest case would be if you have all your marked vertices in one set. And then later, we'll have marked vertices in both sets. So let's say you have k marked vertices, and they're all in this first set that has size n1. And the initial state here is going to be the following. So all of these edges have the same initial amplitude. So one consequence of this is now this is not a uniform superposition over the vertices. And that's because these vertices have a lot more edges than these vertices here. So these vertices are going to start with a greater initial amplitude. So not all the vertices have the same initial probability now. These actually have a greater probability. If you're curious how the initial state evolves, if you are in a uniform superposition over all the vertices, you can check our paper. But this case that I'm going over here, this is cleaner. So that's what I'll talk about. So here's some simulations of that. So with different values. So say you have three marked vertices in the left set, which has 400 vertices total. And say the right set also has 400 vertices. So what happens is the success probability goes up, reaches a half at this time, and then it goes back down and it's periodic again. Let's say we change the number of vertices in the second set. So instead of 400, let's say it has 200. What you see is we get the exact same evolution. The success probability reaches a half at the same time. And again, if you change the number of vertices in the right set to even just one, you can see these little green dots and it follows the same curve. So what we see is that the number of vertices in the second set doesn't matter. All the marked vertices are in the first set, on the left set. And that does matter. So if we change the number of vertices in the first set, we reach a probability of a half at an earlier runtime, because there's a few vertices in the left set. If we change it even more, if all the vertices in the left set are marked, we're actually just always at a success probability of a half. And so, yeah, so that's what happens. We were able to prove this analytically so that the success probability reaches a half, as you saw in the previous graphs. And the time at which you reach that probability only has N1 and K in it. There's no N2. Again, the number of vertices in the second set doesn't matter. And so again, the only thing that matters in the runtime is the ratio of N1 and K. It's only the first set's properties. Any questions? All right, so now if we have marked vertices in both sets, so say K1 in the left set and K2 in the right set, let's see what happens. So here's some values. So if there's three marked vertices in the left, two marked vertices in the right, and that number in both sets. And one of the things that you'll notice here is that the ratio or the density of marked vertices in each set is the same. I guess you could phrase it like that. And what you find is that, well, let me plot this. So I'm going to plot this as the success probability in the left set separately and then the success probability in the right set so you can see what happens in each set. So the success probability in the left set evolves like this. Again, it reaches a half. The success probability in the right set that has two marked vertices and 400 total vertices evolves like that the same way. And so the total success probability would just be the sum of these two curves, which then of course reaches one. And so what we see here is that because the densities are the same, they end up peaking at the same time and so then you get a total success probability of one. The densities are different. So here I've changed the value. So now the densities are not the same. So I've swapped these two sizes. The first set is going to peak there. The second set on the right is going to peak there at a different time. And so now, of course, if you add them, you won't reach a success probability of one. You'll get something a little bit less. And so we're able to analytically prove this. The runtime in each set, so in the left set, you get a probability of a half. At this time, that only depends on the properties of the left set, the density. And the right set also reaches a success probability of a half. And the time only depends on its density of marked vertices. And so if these two line up, then they add up together, they get a success probability of one. So that's kind of neat. So again, the only thing that matters is what goes on in each set. Otherwise, they evolve independently of each other. Any questions before we get to the lackadaisical versions? All right. OK, so let's make this lackadaisical now. And we'll go back to the first case. That's easier, where you only have K marked vertices in one set. And now you have self-loops with weight L1 here, and self-loops with weight L2 here. So again, they can be different amounts of laziness. Or they could be the same. You can pick the same value on both sides. Doesn't matter. The point is you can now adjust this. All right, so let's see what happens. So just to remind you, with the normal coin quantum walk, it evolves like this. If you make it lackadaisical, let's change L1. So let's say L1 is 0.3. We see that we get a boost in the success probability, which is nice. If we change the L1 some more to 0.6, it gets better still. Make it more lazy, we get that. Make it more lazy, we get that, which reaches 1, which is nice. If you make it more lazy, it goes down. More lazy, it goes down, and down, and down, and so forth. So same story. There's some optimal amount of laziness. And in this case, it's when L1 is 1.2 with these values here. OK, so let's go ahead and, oh, it's more lazy. OK, so it's the best when L1 is 1.2. So let's fix L1 as being 1.2. And now let's see what happens as we vary L2. So this is what we just had before. Now if we change L2 to make that lazy as well, oh, nothing happened. Make L2 even bigger, nothing happens. Make it even bigger, oh, nothing happens. So with marked vertices in the left set, it seems like it doesn't matter how lazy the right set is. It only matters how lazy the left set is. And so we see that L2 doesn't matter here. And so here's another way of visualizing that. So what we did is we varied L1 and we varied L2. And we plotted in color as a heat map the maximum success probability. So you see that the success probability is 1, as long as L1 is 1.2. And then it doesn't matter what L2 is. It's the same thing. So from this, you can see that L2 doesn't matter. Only the left set, where the marked vertices are, matter. And we were able to analytically prove this. So you want L1 to be that, which is 1.2, with the numbers we just had. And then the success probability reaches 1, and the runtime doesn't have N2 in it. It only has what's going on in the left set. Any questions? All right. So now, marked vertices in both sets, k1 in the left, k2 in the right. So with these values, let's just pick different values of laziness. So with no laziness, this is what you would get. It looks a little crazy now, because it's marked vertices in both sets. So they might not add up nicely. If you make it lazy now with, say, L1 is 15, L2 is 5, you do get some improvement here. With these values, L1 is 15, and L2 is 100. It's pretty similar to that. If L1 is 80, and L2 is also 80, you get something that's not very good. And if you look at these, it's kind of hard to compare these. Because even this black curve, I mean, it reaches 1 over here. Like, should we use that peak, or should we use this peak? It's like, how do you compare these? And so a good quantity to look at is the total runtime with classical repetitions, which is basically the idea that if your success probability is, say, 1 half, you have to run the algorithm twice on average before you find your marked vertices. And so the total runtime then is the single runtime divided by your success probability of a single run. And so we can plot that as a heat map here. So this is now the total success probability, which is the total runtime. Sorry, the total runtime, which is the single runtime divided by the success probability. And what you see is that it's not so nice anymore, depending on how lazy each side is. And so the color here is, I picked the middle to correspond to the normal coin quantum walk. So anything that's more yellow, which is less time, which is faster, is better. So we see that if the laziness values are within here, that it's better, but if it's over here, it's worse, and so forth. And in particular, the values that we just saw here, these correspond to these points. So this is the normal coin quantum walk. The red and the green ones where we got an improvement are in this yellow band. And in this blue curve over here, where it's worse is in this dark blue area, which we expect to be worse. And so this is this simulation of what happens. We weren't able to prove this. It's a mess. So that's an open question. If you want to take us, if you want to try that. Here's another example. So here I've actually swapped the number of mark vertices in each set. So before, it's 5 and 2. Now it's 2 and 5. So if we look at that, oh. So again, the middle is the normal quantum walk. And so there's kind of nothing that's better. So at least with these particular values, it seems like there's no improvement with the self-loops, which I thought was kind of surprising. Because if you can pick the weights of the self-loops on each side, it seems like there's got to be some values you can pick to make things better. Because all the previous papers showed that you could do better. And here we're actually showing that for these values, you can't do any better. And here's another set of values where there's the same number of marked vertices in each set, but the sets are different sizes. It looks like this. So you get a little bit of improvement here. But for most values of laziness, you don't get any improvement. And so there's some limited improvement here. And again, this is open for proof, if you want to try proving that. So it's an open question. So just to summarize what we've talked about, we saw that lackadaisical quantum walks spread faster in one dimension-ish, because there is still that central peak. But the two peaks on the side spread faster than a normal coin quantum walk. We see that they improved search for a bunch of problems that were vertex transitive, like the complete graph, the grid, and so forth. And when we apply it to the complete bipartite graph, we do still get an improvement for sure if the marked vertices are only in one set. But if the marked vertices are in both sets, then you might get improvement, or you might not. And exploring that would be some great future work if anyone's interested. And so if you want to see the papers, you can just go to my website, it has all my papers, or you can ask me or email me or something like that, and be happy to take your questions. Thanks for the question. Do you have questions for me? All right, thanks for the nice talk. It's an interesting result that you found. You mentioned in one of your slides that you were just looking at something similar, like a physical quantum walks on the hypercube. And in like around 10 years ago, we did something similar. We extended the SKW search with the self-loops. Are you aware of those? I'm not aware of that work. And if you could email that to me, I'd be really interested. Yeah, OK. Yeah. We should continue in this. Yeah. Although one thing that sounds different is, did we use the same oracle? Because if you use the SKW1, that one uses a different oracle. So we'd have to see how that compares. Yeah, definitely we can talk. Just in your initial model, with one dimension. So the analog of, say, the Hadabard matrix is you're talking about the Grover matrix tree by tree. Well, I guess the analog of the Hadabard matrix would be a Fourier matrix. But I was looking at the Grover coin because I'm specifically interested in search problems. OK. So those parameters you have L and A and B feed into this Fourier matrix? Is for what, sorry? Those parameters, A, B, and the amplitudes, they're part of the Fourier matrix that you're choosing. No, I was just showing how the Grover coin would act if the amplitudes were A, B, and C. OK. Yeah. Just to show that what it does is that it flips around the average if it's unweighted, and if it's weighted, and it does that funny thing. Please. Regarding the 2D letters, you said that you don't use amplitude amplification. So how can you, and you did that numerically, so how can you know numerically that you don't have a square root of log? Yeah. And there is a name multiplying by the log. So the log is hidden by the N. How can you distinguish square root of N log N, log N outside the square root N? I understand. Square root of N log N. Yeah. So if we're fitting a curve, a square root of log factor is very hard to see. And so in that paper, I give plots and try to justify that the fit is correct. I didn't show any of that here. So if you want, we can look over it more closely offline. Yeah. I have another question regarding the truncated simplex lattice. You have an algorithm that search on that lattice, and it seems that it is not square root of N. It is larger than square root of N. Yeah. That was searched with a continuous time. Exactly. Random, a quantum walk. So it's not square root of N? No. Is the first order truncated lattice, is it? So it wasn't square root of N if you have an unweighted graph with a continuous time quantum walk? Is it possible to find a square root of N algorithm in this case? So I was able to get it down to close to square root of N by weighing the edges that connected the clicks. So you have these clicks, right? And then if you weigh the edges that join those clicks, those long distance edges, you are able to improve it. And as the weight increases, the runtime tends towards the square root of N. So I wasn't able to exactly reach square root of N, but it tends towards it. Obtained the story. Yeah. So it like so. OK. Yeah. OK. As the weight increases, then it asymptotically approaches square root of N. And I'll give a quick comment. Historical. So you mentioned child's paper about laser quantum walk, but there is one before, I think it's 2005. OK. By Inui, Kono, and Segawa. I think it's the first one on laser quantum walk. OK. Is that the same as the three state quantum walk? Three state. Yeah. So I didn't talk about the history of the order with which I did this. So I actually didn't look at the 1D line first. I actually looked at search on the complete graph first, and then wrote the paper, submitted it, and then I'm very thankful that the refuge responded saying, oh, this seems very similar to three state quantum walks, which I had never heard of at that time. And so yeah. So basically, I agree that the 1D walk is very similar, but just the way it was developed is kind of from a different perspective that then ends up having a lot of similarities. Thanks for the talk. Could you talk about how robust your search algorithm is to noise? What kind of noise? Any sort of positional noise, coin noise, anything in that regard? Are you talking about deco coherence? Or are you talking about if you just use a different? I would say more decoherence. OK. Any sort of spatial or temporal decoherence? There's been some work on it that I have not done. So I know that maybe experts in this room can comment on that, but that's not something that I know very well. Another question? How familiar are you to this oracle theoretical bounds for oracle searches? And is this, I don't know, does that apply to your scenario? Yeah, it does. So it's still true that the fastest you can search is order square root of n, because of the optimality of Grover's that would still apply, because that has to do with which oracle you use. So we're using the same type of oracle that's in Grover's problem. So you can still only search in the square root of n. Depending on the graph you search on, you may not be able to reach that. So for example, if you search on the one-dimensional line, you actually can't search faster than order n, than a linear n, which means you can't do any better than just randomly guessing for the marketware text. Thanks. So thanks, speaker. Thank you. Thank you.
algorithmic application of quantum walks. And the intuition as to why quantum algorithms based on called a lazy quantum walk, which is quite on a weighted graph now. Looking for a picture, as many of you know. If you're at this vertex and yeah, there is some probability of staying very found your item. So this is the spatial search lackadaisical quantum walk. We have a self-loop edges are the same. So the amplitude of here this is a one eigenvector of the quantum walk of version of Grover's algorithm without so yeah, you can search more quickly with a this network that has some hierarchy to it. And l2. So we have now a lackadaisical quantum walk analytically so that the success probability