Skip to main content
Loading Explore guides…
Quantum Computing Misconceptions · Acedra
Home
Explore
Computer Science
Quantum Computing Misconceptions
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
97 segments
Copy
Hide video
0:00
A lot of pop science outlets give a certain summary of quantum computing that I can almost guarantee leads to misconceptions. The summary goes something like this. In a classical computer, data is stored with bits, some sequence of ones and zeros, but in a quantum computer, you are able to represent every possible sequence of bits of some fixed length all at once in one big thing known as a superposition. And sometimes the implication of these summaries is that quantum
0:25
computers can be faster by basically doing whatever a classical computer would do, but to all of these sequences in parallel.
0:33
Now, this does gesture at something that's kind of true, but let me see if I can prove to you why I think this leads to misconceptions, and I'll prove it using a quiz. To set it up, I want you to imagine that I have a mystery function, and I tell you that there's a certain secret number among all the numbers from 0 up to n-1, where if you plug that value into my function, it returns true, but if you were to plug in any other value, it returns false.
0:57
And let's say you can't look at the innards of the function to learn anything about it, the only thing you're allowed to do with it is just try it out on numbers. The warmup question is, how many times, on average, would you have to apply this mystery function in order to find the secret key?
1:11
Well, if the setup was in an ordinary classical computer, there's really nothing better that you can do than guess and check. You go through all the numbers, and maybe you're lucky and find it early, maybe you're unlucky and it doesn't come up until later, but on average, with a list of n possibilities, it takes one half of n attempts to find the key. Now, in computer science, people care about how runtimes scale. If you had a list ten times as big, how much longer would it take?
1:36
And computer scientists have a way of categorizing runtimes. They would call this one O of n, where that big O communicates that maybe there's some constants like the one half, or maybe some factors that grow slower than n, but the factor of n is what explains how quickly it scales as n grows. If n goes up by a factor of ten, the runtime also goes up by a factor of ten. Now, here's your quiz. For the equivalent of this setup, but in a quantum computer,
2:01
what's the best runtime for finding the secret key? I've asked a variant of this quiz many times in a certain lecture that I've given over the years, and the options I typically offer are O of square root of n, O of log of n, O of log of log of n, and O of one, where here O of one would mean that the runtime is just some constant that doesn't actually grow as n grows. Now, to be fair, I have not defined quantum computing.
2:24
In fact, doing so from the ground up is going to be the goal of this video. So without showing you what this mystery function would look like in that setting, it's kind of an incoherent question. But it's not really meant as a quiz that I'm grading you on or anything, it's just meant to be a gut check of intuition before we dive in. In principle, it's the same task. Finding a needle in a haystack, where you want to discover which value out of many options uniquely triggers some function.
2:48
I asked this as a YouTube post last month, which 100,000 of you kindly answered. The most recent time I gave it live was to a group of Stanford students. I also posed it to those attending the International Math Olympiad. And in all of these and many other instances, the answer distribution looks very similar. The most common answer is always O of one. And this is wrong, and I'm pretty sure that it stems from that misleading summary.
3:10
That summary implies that you would put all of the n values that you need to search into this mysterious superposition, and then you would process them all in parallel, and then somehow the answer would be revealed. The second most common answer is typically O of log of n, and this is also wrong. You would call this an exponential speedup. For example, if you increase the size of the list by factors of 10, an O of log n runtime would only tick up by the same additive increment each time.
3:37
Now this wrong answer I suspect stems from a misconception about how much better quantum computers are in general. There are very certain special problems where you can achieve an exponential speedup. The most famous case is probably Shor's algorithm for factoring large numbers. But most problems are not like that. In this case, the correct answer is O of square root of n. And this is a lot more representative of the typical speedup that you could get with a quantum computer.
4:02
In 1994, it was proven that a quantum computer could not possibly do any better than O of square root of n on this task. And then two years later, Lav Grover found a specific procedure that actually achieves that runtime. So searching through a bag of a million options takes on the order of a thousand steps. A bag of a trillion options takes on the order of a million. This big O actually hides something that's pretty fun, which is the constant of pi fourths in the precise runtime,
4:27
and that pi has its own whole fun story to tell, which I'll get to later. You might think that this puzzle with a mystery function triggered by one specific value is super contrived. But I want you to keep in mind this is meant to be a generic stand-in for any problem where you know how to quickly verify a solution, even if you don't know how to find that solution in the first place. This describes an enormous class of problems in computer science known as NP problems.
4:55
So while a square root speedup is frankly not as earth-shattering as an exponential speedup would be, and while big O runtimes are often a lot less important than other practical considerations, it is thought-provoking that something like Grover's algorithm is even possible at all, providing this catch-all method for speeding up any NP problem.
5:13
My goal with this lesson is to build up to a step-by-step walkthrough of how that algorithm works. It's actually very geometric and very beautiful. But we need to build up a lot of background in order to get there. The first two-thirds or so of the video will be spent building up the fundamentals of quantum computing, not with a set of analogies, which as we've seen can lead to misconceptions, but as a piece of math,
5:33
which I think offers you a pair of glasses through which you can see a much more honest depiction of the whole field. This is one of those topics that has a few premises that are just going to feel a little bit strange at first, and I should warn you they take a little getting used to. My current plan is to follow this lesson with another one about some of the underlying physics, which hopefully can help motivate a few of the odd-looking rules that you'll see here.
5:56
But today the goal is to provide the minimal viable path to seeing a genuine, bona fide quantum algorithm.
6:04
Let me pull up again that contrast between classical computing and quantum computing, and let's see if we can build up something of a more representative mental model. It is true of course that data in a classical computer looks like a series of ones and zeros, and at a higher layer of abstraction that might represent an actual data type, like an integer or some text, and at a lower layer of abstraction, those ones and zeros represent some actual thing in the physical world,
6:27
like voltages across a capacitor or something like that. These same layers of abstraction provide a pretty helpful framing when we discuss quantum computing. Over there, there's also some underlying physical measurement, and again you represent the outcome of that measurement with some sequence of ones and zeros, and again this might implement some actual data type that you care about, like a number. This symbol that I'm showing by the way is called a ket.
6:52
I'll explain it properly in a couple minutes, but for right now just think of it as conveying that something is coming from a quantum computer. Let's start things off with a description of quantum computing through the lens of that middle layer of abstraction, meaning we're going to postpone all of the underlying physics for now, which is a little bit like teaching computer science without discussing hardware. In a classical computer, there's no need to distinguish between the state of
7:15
memory and what you read out from the memory, both of them just look like the same sequence of bits, but it's a very different story in a quantum computer. Our main job today is going to be to understand something called the state vector, which is continuous, this is the thing the computer actually operates on, but it has a very unusual relationship with the values that you actually read out, those discrete sequences of bits. Before I can define this state vector, you need to know one other key
7:39
difference from classical computers, which is that this value that you read out, which again just looks like some sequence of ones and zeros, is random. Or to be a little more accurate, I should say it's typically random. The way you can think about this is that if you run a program on a quantum computer, that program doesn't necessarily determine a particular output, instead it determines a probability distribution across all possible outputs.
8:03
So for the example I'm showing on screen, this would be a very small quantum computer where the thing that you read out has four bits, meaning that there are 2 to the 4, or 16 possible outputs, and the specific program you run determines some kind of distribution across all those possible outputs. Some programs might manage to concentrate more probability on just one of those outputs, but other programs might give a more even spread across everything.
8:27
This example, by the way, where the thing you read out has four bits, would be called a 4-qubit quantum computer, and more generally, if you have a k-qubit quantum computer, that means there are 2 to the k distinct possible outputs, and any program gives a distribution across all of those, and the thing that you read out has k distinct bits. That word qubit, by the way, is another thing I'm going to define more precisely in just a minute.
8:50
I do want to emphasize that this distribution is implicit. You never actually see it directly, you instead infer what it must be based on the program that you run. You never see all bit strings coexisting at once in some kind of way. You just see one of them, drawn at random, according to this distribution. At a lower layer of abstraction, what I'm describing as reading out from memory looks like a physical measurement, and the randomness stems from the laws of quantum mechanics.
9:17
If you're curious about the physics, that lower layer of abstraction, that's exactly what the next video is for. Up in this layer, you just think about probability distributions over all possible bit strings. One more funny rule here, which does bubble up from the underlying quantum mechanics, is that after you read out from memory, and you see some particular value, the underlying state of the computer changes such that now all of the probability is concentrated on whatever value you read out.
9:42
So if you kept reading out from memory over and over, you would just keep seeing that same value. You might imagine these programs as creating a very delicate and sensitive probability distribution, where the moment you look at it, sampling from that distribution, the whole thing collapses to one value. Now you might be wondering, where does this distribution come from? This is both the most important and the most confusing part.
10:03
You think of the state of the computer as being described by a big vector. Right now when I say the word vector, you can just think big list of numbers, although as you'll see later on, it can be helpful to think of this as a direction in some super high dimensional space.
10:18
Each component of this vector corresponds to one of the possible values you might read out, one of those distinct bit strings. So in this example where what you read out has 4 bits, the state vector would have 16 distinct components. The state vector is not the same thing as the probability distribution over all possible outputs, but it is very closely related. The fundamental rule, which I admit is going to look very strange at first,
10:42
is that if you take the magnitude of each component in that state vector and you square it, that gives you the probability of seeing the corresponding output, the corresponding bit string. Let me just say up front, a lot of people learning quantum computing find this state vector a bit weird. What is it actually, and why are we squaring things to get probability? As it is, for the sake of simplicity, there's a certain important detail that I'm neglecting until the end of the video here.
11:06
I just want to flag that for most people, this takes a little getting used to. And to be super clear on what I mean with the fundamental rule here, let's suppose that after this program processes this vector, maybe the component of it associated with some specific bit string, like 0011, happened to be 0.5. Then when you square that value, 0.5 squared is 0.25, so the observable implication of this is that when you read out from memory, you have a 25% chance of seeing that bit string, 0011.
11:37
One thing I'll highlight is that it is perfectly valid for the values in this state vector to be negative, and at first you might think that has no real impact, since flipping the sign doesn't change the square, and therefore all the probabilities stay the same. It is true that the probabilities stay the same, but we absolutely consider this to be a distinct state, and as you'll see, the idea of flipping signs plays a very central role in Grover's algorithm.
12:01
Here, this example with four qubits has kind of a lot on screen, with not a lot of visualization to back it up, so let's scale things down to the smallest possible case where the computer has just two possible outputs, represented with a 0 and a 1. In this simplest possible case, the state vector would only be two-dimensional, so we can actually represent it geometrically as an arrow inside a 2D space. In this case, the x-coordinate corresponds to the outcome 0,
12:27
in the sense that the square of that coordinate tells you the probability that when you read out from the computer, you would read a 0. Maybe it's helpful if I add a little bar to show that probability. You'll notice that as the vector points more in the horizontal direction, more of that probability mass is concentrated on the 0. Similarly, the y-coordinate corresponds to a 1 in the same way. A more vertical state vector means you're more likely to see a 1 when you read out from the computer.
12:54
Now, notice, because the two probabilities should add up to 1, after all, something is going to happen, x squared plus y squared should equal 1. Geometrically, this means that the state vector has a length of 1, so you could think of it as being confined to a unit circle.
13:10
More generally, the state vector for a quantum computer will always have a length of 1, and you can think of it as living on some very high-dimensional unit sphere.
13:18
This two-dimensional example has a special name, which I've already mentioned. It's called a qubit, short for quantum bit. The analogy with a classical bit is that when you read out from the computer, you see either a 0 or a 1, but other than that, it is a completely different animal. Mathematically, a qubit is a unit vector in a two-dimensional space, together with a coordinate system where these two perpendicular x and y
13:40
directions correspond to the two values that you might read out when you measure. You should know there is that added bit of complexity that I'm postponing, but this is 90% of the right idea. And again, you have this funny rule where when you measure the qubit, seeing either a 0 or a 1, the vector then collapses to fall onto that corresponding direction. So unless something is done to prepare that qubit back into a diagonal direction,
14:05
any follow-on observations that you make are always going to show the same outcome. It's very possible that at this point you're thinking something like, okay, grant, this is a super bizarre set of premises you're asking me to accept, and if so, you are not alone. What I'm describing, as you can no doubt probably tell, are basically the postulates of quantum mechanics. There are many systems throughout physics, like the spin of an electron or the
14:28
polarization of a photon, that have this property, where the outcome of a measurement is random, and our best laws of physics have us model the state of that system using a vector, just like the one I'm describing here, where squaring the magnitudes of that vector's components give you the probabilities for seeing various possible outcomes. That actually has a special name, it's called the Born rule. This idea of a qubit is basically meant to be an abstraction over many possible
14:54
systems like this, in just the same way that a bit is meant to be an abstraction over many possible physical systems that can toggle one of two directions.
15:03
The symbol I've been showing, by the way, is used throughout any subject with the word quantum in its name to refer to a unit vector in this state space. What you put inside that ket is often going to give some kind of readable meaning for what that vector represents. So in our example with a qubit, the unit vector to the right is often shown with a zero inside the ket, because if that's the state vector, it means you deterministically read out a zero from the computer.
15:29
Likewise, the unit vector in the vertical direction is represented with a ket that has a one inside of it. And if you go on and read more about this, something that you'll very commonly see is that instead of writing down a general qubit with a column vector, the way I've been showing you, a lot of people like to write it as an explicit weighted sum of these two unit vectors in the two coordinate directions. That's a very physicist kind of convention.
15:52
Now classical computing has this idea of logic gates, certain basic operations like AND, OR, and NOT that you can use to process bits and that you can string together to create arbitrarily complicated functions. Analogously we have what are called quantum gates, which are certain fundamental operations that you can apply to a qubit or to a system of multiple qubits. And they always look like somehow flipping or rotating the state vector.
16:17
Now I'm not going to delve too deeply into the details of all the different quantum gates, but if you are curious, I'll show you an example of what one of them looks like. Here's a very standard one known as a Hadamard gate. What it does is it maps the unit vector in that horizontal zero direction into the diagonal northeast direction, and it maps the unit vector in the vertical one direction into that kind of diagonal southeast direction.
16:40
You would very commonly use this to take a deterministic state, something that's either a zero or a one, and turn it into something with a 50-50 equal balance, or vice versa, too. This is just one example, but there are a number of others forming the building blocks for quantum computing, and the art of writing an algorithm in this setting is to somehow compose a bunch of different quantum gates together that will progressively manipulate
17:03
and flip and massage this vector until it points almost entirely in one particular coordinate direction, presumably one that actually answers a question you care about.
17:12
Now down with the simplest example of a qubit, you only have two coordinate directions to work with, so you would be constrained to answer simple yes-no questions. And although I can't illustrate a geometric vector with more than three dimensions, in principle, a system with k qubits is going to have 2 to the k distinct coordinate directions, one for each bit string. So if you can somehow manage to coerce this vector to point along just one of those directions, you could potentially
17:38
answer some more interesting question, carrying more information. Maybe one of them represents a prime divisor in a very large number you're trying to factor, or maybe one of them represents that secret key value from the opening puzzle of this video. Even though the potential power of quantum computers has a long tradition now of being greatly exaggerated, insofar as there really is potentially more power there, one of the key reasons is that the size of the state vector grows exponentially.
18:05
As few as 100 qubits would already imply a mind-bogglingly massive state vector. But the catch is that you have no direct access to the values inside this vector. It's effectively invisible to you. The only way it can be useful is if you have a way to manipulate it in such a way that all of the probability, or at least most of it, gets concentrated on one single component, and if that component corresponds to an answer to a question that you care about.
18:31
Grover's algorithm offers us a really great example to actually see how this looks, and it's high time that we get there.
18:41
Let me offer you a very high-level preview for how it looks. I promise I will explain all of this in more detail, but here's the bird's eye view. It initializes this state vector in such a way that there's an equal balance of probability across all possible outcomes. One of those outcomes is going to be the secret key that you're searching for, and the tool that you'll have available, which I promise to motivate later, is to flip the sign of the state vector at that coordinate.
19:07
This doesn't immediately affect the probabilities, but when you interleave this with a certain other operation, and you kind of go back and forth between the two of these, what happens is that the probability mass slowly starts to get concentrated over that secret key value, and at a certain point, almost all of it will be there, so when you read out from the computer, you will almost certainly see the secret key
19:27
you're looking for. Okay, so that's the high level, but let's unpack it in some more detail. The first thing to address is this idea of flipping the sign of the component associated with the secret key. That might feel a little bit weird. Why would we assume that that operation is available to us? Backing up, remember that Grover's algorithm is meant to apply to any problem where you can verify a solution quickly, even if finding a solution in the first place is hard.
19:53
Examples here would include solving Sudokus, finding a valid coloring of a map where no two border regions share a color, or countless tasks throughout cryptography, where security often depends on a certain value being hard to find, even though for pragmatism it has to be easily verifiable. We began this video with a generic stand-in for all of these problems, where you imagine some function that takes in any number from 0 to n-1 and returns true on one and only one of those.
20:19
In principle, we'll think of such a function as being built out of a bunch of classical logic gates. Those logic gates act on some binary representation of the inputs, and the final output is either 0 or 1. Now here's the key point. Grover knew that given any ensemble of logic gates like this, you can translate it into a system of quantum gates so that if in the classical case the function takes in some binary input and returns a 1, for true,
20:44
then in the quantum case the effect of all of these gates is to flip the sign of that state, the state associated with the same bit string. Similarly, if in the classical case the function maps some binary input to 0, for false, then in this quantum translation the effect on the corresponding state would be to leave it unchanged. More generally, because all of these quantum operations are linear, if the state is a combination of multiple pure coordinate directions,
21:10
then the effect is to simply flip the sign for the component associated with whatever bit string triggers that classical function. It means that if you have any NP problem, anything where you can quickly verify solutions, you're able to create an operation on a quantum computer that flips the sign of a state vector at the position corresponding to a solution of that problem. This might feel kind of useless at first. After all, flipping signs doesn't affect the probabilities.
21:37
But Grover realized that this could be used in conjunction with another step that slowly amplifies the probability of that key value. There's actually a really nice way to visualize his algorithm. To set it up, let's imagine that our state vector has only three dimensions. Obviously in principle it would be way bigger, but this lets me draw the first picture. The three directions here would correspond to the values 0, 1, and 2, and the whole problem statement here is that one
22:02
of those values would be a secret key that we're searching for. Many different quantum algorithms will begin by putting that state vector into a kind of equal balance, where all of the components have the same value. I want to give that equal balance vector a name. Let's call it B. I hope you don't object too much to me simply declaring that this is possible without dwelling on the underlying quantum gates that make it happen. In this case it essentially looks like a big pile of Hadamard gates,
22:26
but all you need to know is that this equal balance direction is abundantly accessible. So starting from here, the goal is to somehow coerce this vector to instead point up in that secret key direction. And what's very helpful for the visualization purposes here is that throughout Grover's algorithm, the vector only ever moves inside the 2D plane that's spanned by these two vectors. So what I'm going to do is draw everything on that two-dimensional slice.
22:53
And this is going to give us a faithful representation even when the full dimension is way too big for me to draw literally. The convention I'll use here in drawing that slice will be to put the secret key direction, whatever it is, along this y-axis, and then the x-axis is going to represent something that's an equal balance of all of the other states, the non-key states. So in our very small three-dimensional example, if that secret key was the 2 state up in the z direction,
23:18
that would mean this perpendicular is an equal balance of 0 and 1, which sits on the xy plane perpendicular to that z-axis. Notice the fully equally balanced state, b, has some component in that secret key direction, since by its definition it has a little bit of that secret key within it. Instead of drawing this slice from three dimensions, here's what it would look like if it was taken from some larger number of dimensions.
23:42
It's almost identical, but the main difference is that that equal balance state vector gets closer and closer to being perpendicular to the secret key direction. Crucially though, this angle is never quite 90 degrees, since that balance state always has a little bit of that secret key value inside of it. In fact, calculating this angle is going to be essential for understanding the runtime of Grover's algorithm. This is the main bit of math you actually have to do for it.
24:07
You can find this angle by taking a dot product between the balance state and the key direction. The components of that balance state vector are all going to look like 1 divided by the square root of n, since remember it needs to be true that when you add the squares of all of these, it would give you 1. Since the key vector is 0 almost everywhere but 1 in one of the components, it means that the dot product between these two is 1 divided by the square root of n.
24:32
If you know a little about dot products, you'll know that this is also the cosine of the angle between those two vectors. I'm going to translate this fact a little to make it more useful for our purposes later. This is the same as saying the sine of the complementary angle down over here, which I'll call theta, is 1 over the square root of n. For really small angles, the sine of theta and theta are approximately the same, so if n is very large, we can safely say that this angle is about 1
24:58
divided by the square root of n, as long as it's measured in radians. This value for theta is ultimately where the square root in the runtime is going to come from. So let's remember it. I'll throw it up in the corner here. Okay, having spent a while setting up the actual picture, let me show you the procedure here. It's surprisingly simple. Remember that key operation we were looking at earlier? The one where you take the verification function for whatever NP problem
25:22
you're trying to solve, and you translate it into some quantum gates, and the effect is to flip the sign associated with that key value? Well, what does that look like inside our diagram? In this diagram, if you flip the sign for the component associated with the key value, but all other components stay the same, what it looks like is flipping about the x-axis.
25:44
And the final ingredient you need to know is that it is also possible to flip this state vector around this equal balance direction. I realize it might be a little unsatisfying for me to keep declaring that certain operations are available, but one thing to know is that in general, if you can clearly describe and access one of these state vectors, it's also perfectly possible to reflect around it. There are some quantum gates, they let you flip around this balance direction,
26:09
but trust me that dwelling on the details of how those look isn't really going to add much clarity or intuition to the whole algorithm. The insight really just comes from geometry. Notice how if you first flip around the x-axis, and then flip around this off-diagonal direction, the state now points slightly more in the vertical direction. If you were to read out from memory now, you would have a slightly larger chance of seeing the secret key value than all the others.
26:33
Here, maybe it's helpful if I show the actual coordinates, in this case where n equals 100, along with some probability bars based on the squares of those coordinates. Notice how each time I flip around the x-axis, and then flip around this off-diagonal axis, the component associated with that secret key gets a little bit larger. So Grover's algorithm is remarkably simple. All you do is repeat this over and over until the vector points as close as it can get to the secret key direction.
27:00
The final bit of reasoning you have to do is to figure out how many repetitions that should be. A wonderful fact from geometry is that if you successively flip about two different lines like this, the overall effect is the same as a rotation, more specifically a rotation by two times the angle between those two lines. So in our case, applying the two operations we have available one after the other, the net effect is to rotate the state vector by two times theta,
27:26
where again theta is that little angle that we calculated earlier, approximately one over the square root of n. The ultimate goal is to rotate our initial state a little under 90 degrees, or about pi halves radians. This means the optimal number of repetitions looks like pi halves divided by two theta, which is pi fourths times one over theta, and critically, because theta is about one divided by the square root of n,
27:50
it means the total number of steps looks like pi fourths times the square root of n. So what Grover's algorithm says is first find whatever whole number is closest to this value and then repeat your two available flips that specific number of times. As a concrete example, let's say that n was two to the power of twenty, meaning you're searching for a secret key out of about a million options. You would be running this on a computer with at least twenty qubits,
28:15
and what the algorithm would say is first compute pi fourths times the square root of this number, which is around eight hundred and four, meaning you now repeat those two operations you have available, the one flipping the sign of the key state and the one that's flipping around the balance direction eight hundred and four times. Now remember, this state vector is invisible to you. There is nothing that you can do that will read out the values that it has.
28:37
You instead have to infer where it must be through reasoning, and in this case, through all the geometric reasoning, you can conclude that after this specific number of times, the vector should be pointed almost entirely in that secret key direction. So when you read out from the computer, you are almost guaranteed to see that secret key value. Now to be clear, you're not guaranteed to see it. There is some small chance that after reading out, you would see something that's not the secret key.
29:02
So to be sure, you could always quickly verify the answer, since after all, the whole premise of this situation is that you have some quick way of verifying answers. You can just do that on a classical computer. Worst case, if you got unlucky and sampled a different number, you run the whole thing again, and it becomes vanishingly unlikely that you would ever need to run this more than just a couple times.
29:22
To wrap up, I want to come clean about a lie that I've been telling you, and also reflect a little bit about where this speedup came from, and then highlight a surprising analogy. Before I do, now might be as good a time as any to say a thanks to the community of channel supporters on Patreon. Putting together visualized lessons like this takes an enormous amount of time. As you probably know, most YouTubers monetize their content with in-video sponsorships,
29:44
but for many years now that's something that I've opted to decline. I think it makes the videos better, and the only reason it's not a wildly costly decision is that enough viewers who agree with that directly support the channel through Patreon. In exchange, I offer supporters early views of new content, which is actually very helpful for developing it, and there's other perks in there too. In general though, if you like this content, it would mean a lot if you considered joining.
30:07
No pressure though, one of the big values is that the content can be free.
30:12
Anyway, back to those three finishing points. The lie is a lie by omission. I've been showing these state vectors with positive and negative real number values, but more generally, these components can be complex numbers. Now my hope is to motivate why that's the case in the follow-on video about physics. The general idea is that any time you're working with waves, you care about both amplitude and phase, and a complex number is a really elegant way to encode an amplitude and phase together.
30:38
So if you look at one of the components inside the state vector, the fuller picture for how to think about it is that it has some magnitude and some phase. The magnitude is the thing that you square to get the probability, and the phase is essentially a more general version of our whole discussion here around positive and negative values. Changing phase doesn't immediately affect the probabilities, but it does affect the state, which in turn affects how it gets processed and how it
31:01
interacts with the world. Now needless to say, throwing in a bunch of complex numbers adds a lot of potential confusion to an already complicated topic. That's why I avoided it. But we were safe to ignore complex values for the purposes of Grover's algorithm, since very mercifully, during that algorithm, you only ever see positive and negative values. I want you to know, though, that this availability of complex values plays a
31:23
crucial role in other quantum algorithms, like Shor's for factoring numbers. Next, even if you understood everything that I described with this whole algorithm, it's not easy to summarize where exactly the speedup came from. The fact that you begin by applying a certain operation to this equal balance state makes it very tempting to say that the speedup comes from parallelizing the operation over all possible inputs. But like I mentioned at the start, that summary, at least to me,
31:48
just really doesn't feel right, and it definitely leads to misconceptions. As you now know, that step, on its own, does nothing to reveal the key value. I'll leave it up to your interpretation whether it feels apt to describe this first step as applying a function to many inputs in parallel, or if it feels better to say that the balance state is just its own new thing, and the function we have always applies to individual inputs one at a time, never multiple at once.
32:13
It's just that those inputs are now a new kind of thing. In my view, for this algorithm, if you want the one-word summary for where the speedup comes from, I think a better choice would be Pythagoras. As a loose analogy, if you want to get from one corner of a unit square to the opposite, if you're limited to move only in the x and y directions, you have to walk two units. But if you're allowed to move diagonally, you can get there in the square root of two.
32:36
And more generally, if you're up in n dimensions, you would have to walk n units to get from one corner of a cube to the opposite one if you can only move along the edges, but if you can go diagonally, you can get there in the square root of n. In the worldview of quantum mechanics, different observable states all represent perpendicular directions in some state space. So viewed from this framework, what the classical deterministic world looks
33:00
like is one where you only have access to these pure coordinate directions. If you think about it, anytime you're doing computation, your computer is somehow walking through a series of different states that are available to it, and algorithmic runtime is all about understanding how many steps you have to walk in the space of all possible states. So from this quantum worldview, where classical states look like pure coordinate
33:22
directions, the key difference with quantum computing is that you now also have available to you a panoply of additional diagonal directions that you can work with. Now, to be clear, the analogy is not too literal, you should take it with a grain of salt. It's not like runtime necessarily looks like a distance travelled through this particular state space. But it is true that if you follow the state vector throughout Grover's algorithm,
33:45
what it's doing is slowly walking along a quarter circle arc from an initial condition to the target condition, tracing a path that would be entirely unavailable if you were limited to move only in pure coordinate directions. And the effect is to provide this square root-sized shortcut. And as the very last point before I let you go, regular viewers will know that one of my reasons for covering this topic is because of
34:07
a promised analogy between this algorithm and something we covered last video, about two colliding blocks that can compute pi. In that video, we are also studying a point in a certain two-dimensional state space bouncing around a circle, and in fact, the series of bounces that it took is essentially identical to what we just saw here with Grover's algorithm. The story here is that when a physicist friend of mine, Adam Brown, saw the first version of that video, he had recently been reading up on
34:32
Grover's algorithm and immediately realized that both processes were identical. Now I had this whole cockamamie plan for this video where I was going to explain quantum computing and Grover's algorithm in the context of that analogy, but it turned out to be just a terrible idea. The whole thing only really made sense if you already understood Grover's algorithm. So instead, now that you have seen both topics in isolation, what I'll do is leave up a rough outline of how the analogy looks.
34:55
Think of this as an open-ended homework puzzle, where the task is to draw the connection for yourself. As an answer key of sorts, I will link to the very delightful paper by Adam Brown outlining precisely what that analogy looks like. If you want to learn more of the fundamentals of quantum computing, several years ago two very smart friends of mine, Andy Matuszczak and Michael Nielsen, put together a really nice resource for learning the topic,
35:17
offering a pretty unique approach to making sure that you actually remember it in the long term. To learn some of the fundamental quantum mechanics, Mithina Yoganathan from the channel Looking Glass Universe has been putting together a very beginner-friendly course on the topic. She was actually the one to teach me how Grover's algorithm works many years ago, and honestly I owe a lot of the content of this video to many helpful conversations with her.
35:39
And as a very last note to end on, one of the conversations I had while making this video was with Scott Aaronson, a very widely respected researcher and utterly delightful author on the topic. I recorded the Zoom call for notes, and there's one little piece of it which I just wanted to share with you. You know, I have this dream of writing a science fiction novel where I know it's going to be the climactic scene, where the heroes will be, you know,
36:02
Ron and Grover's algorithm to try to find this cryptographic key, right? The whole fate of the world will depend on whether they can find it, OK? The bad guys have surrounded their base, you know, they're bashing down the walls. But Grover's algorithm is still running, and it has only like a 30 percent probability of giving you the solution if you measure. So the question is, like, do you measure now or do you let it run for another minute? Right?
36:29
And if you measure now, you know, and you don't get it, then you've lost everything. Then you have to restart from the beginning. So this is this is not a plot that you could have with any classical algorithm. Right.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat