Prática de Shadowing: But what is quantum computing? (Grover's Algorithm) - Aprenda a falar inglês com vídeo
Criando lição...
1
A lot of pop science outlets give a certain summary of quantum computing that I can almost guarantee leads to misconceptions.
2
The summary goes something like this.
3
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
4
some fixed length all at once in one big thing known as a superposition.
5
And sometimes the implication of these summaries is
6
that quantum computers can be faster by by basically doing whatever a classical computer would do, but to all of these sequences in parallel.
7
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.
8
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,
9
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.
10
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.
11
The warm -up question is, how many times, on average, would you have to apply this mystery function in order to find the secret key?
12
Well, if the setup was in an ordinary classical computer, there's really nothing better that you can do than guess and check.
13
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,
14
it takes one half of n attempts to find the key.
15
Now in computer science people care about how run times scale.
16
If you had a list ten times as big, how much longer would it take?
17
And computer scientists have a way of categorizing run times.
18
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.
19
But the factor of n is what explains how quickly it scales as n grows.
20
If n goes up by a factor of 10, the runtime also goes up by a factor of 10.
21
Now, here's your quiz.
22
For the equivalent of this setup, but in a quantum computer, what's the best runtime for finding the secret key?
23
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,
24
o of log of log of n, and o of 1, where here o of 1 would mean
25
that the runtime is just some constant that doesn't actually grow as n grows.
26
Now, to be fair, I have not defined quantum computing.
27
In fact, doing so from the ground up is going to be the goal of this video.
28
So without showing you what this mystery function would look like in that setting, it's kind of an incoherent question.
29
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.
30
In principle, it's the same task.
31
Finding a needle in a haystack, where you want to discover which value, out of many options, uniquely triggers some function.
32
I asked this as a YouTube post last month, which 100 ,000 of you kindly answered.
33
The most recent time I gave it live was to a group of Stanford students.
34
I also posed it to those attending the International Math Olympiad.
35
And in all of these and many other instances, the answer distribution looks very similar.
36
The most common answer is always O .
37
And this is wrong, and I'm pretty sure that it stems from that misleading summary.
38
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,
39
and then somehow the answer would be revealed.
40
The second most common answer is typically O , and this is also wrong.
41
You would call this an exponential speedup.
42
For example, if you increase the size of the list by factors of 10, an O runtime would only tick up by the same additive increment each time.
43
Now this wrong answer, I suspect, stems from a misconception about how much better quantum computers are in general.
44
There are very certain special problems where you can achieve an exponential speedup.
45
The most famous case is probably Shor's algorithm for factoring large numbers.
46
But most problems are not like that.
47
In this case, the correct answer is O of square root of n.
48
And this is a lot more representative of the typical speedup that you could get with a quantum computer.
49
In 1994, it was proven that a quantum computer could not possibly do any better than O on this task.
50
And then two years later, Law of Grover found a specific procedure that actually achieves that runtime.
51
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.
52
This big O actually hides something that's pretty fun, which is the constant of pi fourths in the precise runtime, and that pi has its own whole fun story to tell, which I'll get to later.
53
You might think that this puzzle with a mystery function triggered by one specific value is super contrived.
54
But I want you to keep in mind this is meant
55
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.
56
This describes an enormous class of problems in computer science known as NP problems.
57
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,
58
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.
59
My goal with this lesson is to build up to a step -by -step walkthrough of how that algorithm works.
60
It's actually very geometric and very beautiful, but we need to build up a lot of background in order to get there.
61
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,
62
but as a piece of math, which I think offers you a pair of glasses through
63
which you can see a much more honest depiction of the whole field.
64
This is one of those topics that has a few premises
65
that are just going to feel a little bit strange at first, and I should warn you they take a little getting used to.
66
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.
67
But today, the goal is to provide the minimal viable path to seeing a genuine bona fide quantum algorithm.
68
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.
69
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,
70
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,
71
like voltages across a capacitor or something like that.
72
Now these same layers of abstraction provide a pretty helpful framing when we discuss quantum computing.
73
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,
74
and again this might implement some actual data type that you care about, like a number.
75
This symbol that I'm showing, by the way, is called a ket.
76
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.
77
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,
78
which is a little bit like teaching computer science without discussing hardware.
79
In a classical computer, there's no You don't need to distinguish between the state of memory
80
and what you read out from the memory.
81
Both of them just look like the same sequence of bits.
82
But it's a very different story in a quantum computer.
83
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,
84
but it has a very unusual relationship with the values that you actually read out, those discrete sequences of bits.
85
Before I can define this state vector, you need to know one other key difference from classical computers, which is that this value that you read out,
86
which again just looks like some sequence of ones and zeros, is random.
87
Or to be a little more accurate, I should say it's typically random.
88
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.
89
Instead, it determines a probability distribution across all possible outputs.
90
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,
91
or 16, possible outputs, and the specific program you run determines some kind of distribution across all those possible outputs.
92
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.
93
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.
94
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.
95
That word qubit, by the way, is another thing I'm going to define more precisely in just a minute.
96
I do want to emphasize that this distribution is implicit.
97
You never actually see it directly, you instead infer what it must be based on the program that you run.
98
You never see all bit strings coexisting at once in some kind of way.
99
You just see one of them drawn at random according to this distribution.
100
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.
101
If you're curious about the physics, that lower layer of abstraction, that's exactly what the next video is for.
102
Up in this layer, you just think about probability distributions over all possible bit strings.
103
Now, one more funny rule here, which does bubble up from the underlying quantum mechanics is
104
that after you read out from memory and you see some particular value,
105
the underlying state of the computer changes such that now all of the probability is concentrated on whatever value you read out.
106
So if you kept reading out from memory over and over, you would just keep seeing that same value.
107
You might imagine these programs as creating a very delicate and sensitive probability distribution where the moment you look at it,
108
sampling from that distribution, the whole thing collapses to one value.
109
Now you might be wondering, where does this distribution come from?
110
This is both the most important and the most confusing part.
111
You think of the state of the computer as being described by a big vector.
112
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.
113
Each component of this vector corresponds to one of the possible values you might read out, one of those distinct bit strings.
114
So, in this example where what you read out has four bits, the state vector would have 16 distinct components.
115
The state vector is not the same thing as the probability distribution over all possible outputs, but it is very closely related.
116
The fundamental rule, which I admit is going to look very strange at first, is that if you take the magnitude of each component in that state vector and you square it,
117
that gives you the probability of seeing the corresponding output, the corresponding bit string.
118
Let me just say up front, a lot of people learning quantum computing find this state vector a bit weird.
119
What is it actually, and why are we squaring things to get probability?
120
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.
121
I just want to flag that for most people, this takes a little getting used to.
122
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,
123
I don't know, 0011 happened to be 0 .5.
124
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,
125
you have a 25 % chance of seeing that bit string, 0011.
126
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,
127
since flipping the sign doesn't change the square, and therefore all the probabilities stay the same.
128
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.
129
Here, this example with 4 qubits has kind of a lot
130
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,
131
represented with a 0 and a 1.
132
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.
133
In this case, the x -coordinate corresponds to the outcome 0, in the sense that the square of that coordinate tells you the probability
134
that when you read out from the computer you would read a 0.
135
Here, maybe it's helpful if I add a little bar to show that probability.
136
And you'll notice that as the vector points more in the horizontal direction, more of that probability mass is concentrated on the zero.
137
And then similarly the y -coordinate corresponds to a 1 in the same way.
138
A more vertical state vector means you're more likely to see a 1 when you read out from the computer.
139
Now notice, because the two probabilities should add up to 1, after all something is going to happen,
140
x squared plus y squared should equal 1 and geometrically this means that the state vector has a length of 1.
141
So you could think of it as being confined to a unit circle.
142
More generally the state vector for a quantum computer will always have a length of 1
143
and you can think of it as living on some very high dimensional unit sphere.
144
This two -dimensional example has a special name, which I've already mentioned.
145
It's called a qubit, short for quantum bit.
146
The analogy with a classical bit is that
147
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.
148
Mathematically, a qubit is a unit vector in a two -dimensional space, together with a coordinate system where these two perpendicular x
149
and y directions correspond to the two values that you might read out when you measure.
150
You should know there is that added bit of complexity that I am postponing, but this is 90 % of the right idea.
151
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.
152
So unless something is done to prepare that qubit back into a diagonal direction, any follow -on observations that you make are always going to show the same outcome.
153
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.
154
And if so, you are not alone.
155
What I'm describing, as you can no doubt probably tell, are basically the postulates of quantum mechanics.
156
There are many systems throughout physics, like the spin of an electron or the polarization of a photon, that have this property, where the outcome of a measurement is random,
157
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,
158
where squaring the magnitudes of that vector's components give you the probabilities for seeing various possible outcomes.
159
That actually has a special name.
160
It's called the Born Rule.
161
This idea of a qubit is basically meant to be an abstraction over many possible systems like this, in just the same way
162
that a bit is meant to be an abstraction over many possible physical systems that can toggle one of two directions.
163
Now the symbol
164
that I've been showing by the way is used throughout any
165
subject with the word quantum in its name to refer to a unit vector in this state space.
166
And what you put inside that ket is often going to give some kind of readable meaning for what that vector represents.
167
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,
168
it means you deterministically read out a zero from the computer.
169
Likewise, the unit vector in the vertical direction is represented with a ket that has a one inside of it.
170
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,
171
a lot of people like to write it as an explicit
172
weighted sum of these two unit vectors in the two coordinate directions.
173
That's a very physicist kind of convention.
174
Now classical computing has this idea of logic gates, certain basic operations like AND,
175
OR, and NOT, that you can use to process bits and that you can string together to create arbitrarily complicated functions.
176
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,
177
and they always look like somehow flipping or rotating the state vector.
178
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.
179
Here's a very standard one known as a Hadamard gate, and what it does is it maps the unit vector in that horizontal 0 direction into the diagonal northeast direction,
180
and it maps the unit vector in the vertical 1 direction into that kind of diagonal southeast direction.
181
You would very commonly use this to take a deterministic state, something that's either a 0 or a 1, and turn it into something with a 50 -50 equal balance.
182
Or vice versa, too.
183
This is just one example, but there are a number of others forming the building blocks for quantum computing,
184
and the art of writing an algorithm in this setting is to somehow compose a bunch of different quantum gates together,
185
they will progressively manipulate and flip and massage this vector until it points almost entirely in one particular coordinate direction,
186
presumably one that actually answers a question you care about.
187
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.
188
And although I can't illustrate a geometric vector with more than three dimensions,
189
in principle a system with k qubits is going to have two to the k distinct coordinate directions, one for each bitstring.
190
So if you can somehow manage to coerce this vector to point along just one of those directions, you could potentially answer some more interesting question, carrying more information.
191
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.
192
Even though the potential power of quantum computers has a long tradition now of being greatly exaggerated.
193
Insofar as there really is potentially more power there, one of the key reasons is that the size of the state vector grows exponentially.
194
As few as 100 qubits would already imply a mind -bogglingly massive state vector.
195
But the catch is that you have no direct access to the values inside this vector.
196
It's effectively invisible to you.
197
The only way it can be useful is
198
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,
199
and if that component corresponds to an answer to a question that you care about.
200
Grover's algorithm offers us a really great example to actually see how this looks, and it's high time that we get there.
201
Let me offer you a very high -level preview for how it looks.
202
I promise I will explain all of this in more detail, but here's the bird's -eye view.
203
It initializes this state vector in such a way that there's an equal balance of probability across all possible outcomes.
204
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 promised to motivate later,
205
is to flip the sign of the state vector at that coordinate.
206
Now 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,
207
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,
208
so when you read out from the computer you will almost certainly see the secret key you're looking for.
209
Okay, so that's the high level, but let's unpack it in some more detail.
210
The first thing to address is this idea of flipping the sign of the component associated with the secret key.
211
That might feel a little bit weird.
212
Why would we assume that that operation is available to us?
213
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.
214
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,
215
where security often depends on a certain value being hard to find, even though for pragmatism it has to be easily verifiable.
216
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,
217
and returns true on one and only one of those.
218
In principle, we'll think of such a function as being built out of a bunch of classical logic gates.
219
Those logic gates act on some binary representation of the inputs, and the final output is either 0 or 1.
220
Now here's the key point.
221
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,
222
the function takes in some binary input and returns a 1 for true, then in the quantum case, the effect of all of these gates is to flip the sign of that state,
223
the state associated with the same bit string.
224
And then similarly, if in the classical case, the function maps some binary input to zero for false, then in this quantum translation,
225
the effect on the corresponding state would be to leave it unchanged.
226
And then more generally, because all of these quantum operations are linear, if the state is a combination of multiple pure coordinate directions,
227
then the effect is to simply flip the sign for the component associated with whatever bit string triggers that classical function.
228
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
229
that flips the sign of a state vector at the position corresponding to a solution of that problem.
230
This might feel kind of useless at first, after all flipping signs doesn't affect the probabilities,
231
but Grover realized that this could be used in conjunction with another step that slowly amplifies the probability of that key value.
232
And there's actually a really nice way to visualize his algorithm.
233
To set it up, let's imagine that our state vector has only three dimensions.
234
Obviously in principle it would be way bigger, but this lets me draw the first picture.
235
The three directions here would correspond to the values 0, 1, and 2, and the whole problem statement here is
236
that one of those values would be a secret key that we're searching for.
237
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.
238
And I want to give that equal balance vector a name.
239
Let's call it B.
240
I hope you don't object too much to me simply declaring
241
that this is possible without dwelling on the underlying quantum gates that make it happen.
242
In this case, it essentially looks like a big pile of Hadamard gates, but all you need to know is that this equal balance direction is abundantly accessible.
243
So, starting from here, the goal is to somehow coerce this vector to instead point up in that secret key direction.
244
And what's very helpful for the visualization purposes here is
245
that throughout Grover's algorithm the vector only ever moves inside the 2d plane that's spanned by these two vectors
246
So what I'm gonna do is draw everything on
247
that two -dimensional slice and this is gonna give us a faithful representation Even
248
when the full dimension is way too big for me to draw literally The convention I'll use here in drawing
249
that slice will be to put the secret key direction Whatever it is along this y -axis
250
And then the x -axis is gonna represent something that's an
251
equal balance of all of the other states the non -key states.
252
So in our very small three -dimensional example, if that secret key was the 2 state up in the z direction, that would mean this perpendicular is an equal balance of 0 and 1,
253
which sits on the xy -plane perpendicular to that z -axis.
254
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.
255
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.
256
It's almost identical, but the main difference is that that equal balance state vector gets closer
257
and closer to being perpendicular to the secret key direction.
258
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.
259
In fact, calculating this angle is going to be essential for understanding the runtime of Grover's algorithm.
260
This is the main bit of math you actually have to do for it.
261
You can find this angle by taking a dot product between the balanced state and the key direction.
262
The components of that balanced 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,
263
it would give you 1.
264
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.
265
And if you know a little about dot products, you'll know that this is also the cosine of the angle between those two vectors.
266
I'm going to translate this fact a little to make it more useful for our purposes later.
267
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.
268
And 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 divided by the square root of n,
269
as long as it's measured in radians.
270
This value for theta is ultimately where the square root in the runtime is going to come from.
271
So let's remember it.
272
I'll throw it up in the corner here.
273
Okay, having spent a while setting up the actual picture, let me show you the procedure here.
274
It's surprisingly simple.
275
Remember that key operation we were looking at earlier?
276
The one where you take the verification function for whatever NP problem you're trying to solve, and you translate it into some quantum gates,
277
and the effect is to flip the sign associated with that key value?
278
Well, what does that look like inside our diagram?
279
In this diagram, if you flip the sign for the component associated with the key value, but all other components stay the same.
280
What it looks like is flipping about the x -axis.
281
And the final ingredient you need to know is
282
that it is also possible to flip this state vector around this equal balance direction.
283
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,
284
if you can clearly describe and access one of these state vectors, it's also perfectly possible to reflect around it.
285
There are some quantum gates, they let you flip around this balance direction, but trust me
286
that dwelling on the details of how those look isn't really going to add much clarity or intuition to the whole algorithm.
287
The insight really just comes from geometry.
288
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.
289
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.
290
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.
291
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.
292
So Grover's algorithm is remarkably simple.
293
All you do is repeat this over
294
and over until the vector points as close as it can get to the secret key direction.
295
The final bit of reasoning you have to do is to figure out how many repetitions that should be.
296
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.
297
More specifically, a rotation by 2 times the angle between those two lines.
298
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 2 times theta,
299
where again, theta is that little angle that we calculated earlier, approximately 1 over the square root of n.
300
The ultimate goal is to rotate our initial state a little under 90 degrees, or about pi halves radians.
301
This means the optimal number of repetitions looks like pi halves divided by 2 theta, which is pi fourths times 1 over theta,
302
and critically, because theta is about 1 divided by the square root of n, it means the total number of steps looks like pi fourths times the square root of n.
303
So what Grover's algorithm says is first find whatever whole number is closest to this value
304
and then repeat your two available flips that specific number of times.
305
As a concrete example let's say that n was 2 to the power of 20, meaning you're searching for a secret key out of about a million options.
306
You would be running this on a computer with at least 20 qubits
307
and what the algorithm would say is first compute pi fourths times the square root of this number which is around 804, meaning you now repeat those two operations you have available,
308
the the one flipping the sign of the key state and the one that's flipping around the balance direction, 804 times.
309
Now remember, this state vector is invisible to you.
310
There's nothing that you can do that will read out the values that it has.
311
You instead have to infer where it must be through reasoning.
312
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.
313
So when you read out from the computer, you are almost guaranteed to see that secret key value.
314
Now to be clear, you're not guaranteed to see it.
315
There's some small chance that after reading out you would see something that's not the secret key.
316
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.
317
You can just do that on a classical computer.
318
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.
319
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 speed up came from, and then highlight a surprising analogy.
320
Before I do, now might be as good a time as any to say a thanks to the community of channel supporters on Patreon.
321
Putting together visualized lessons like this takes an enormous amount of time.
322
As you probably know, most YouTubers monetize their content with in -video sponsorships, but for many years now that's something that I've opted to decline.
323
I think it makes the videos better, and the only reason it's not a wildly costly decision is
324
that enough viewers who agree with that directly support the channel through Patreon.
325
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.
326
In general though, if you like this content, it would mean a lot if you consider joining.
327
No pressure though, one of the big values is that the content can't be free.
328
Anyway, back to those three finishing points.
329
The lie is a lie by omission.
330
I've been showing these state vectors with positive and negative real number values, but more generally, these components can be complex numbers.
331
Now my hope is to motivate why that's the case in the follow -on video about physics.
332
The general idea is that anytime 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.
333
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.
334
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.
335
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 interacts with the world.
336
Now needless to say, throwing in a bunch of complex numbers adds a lot of potential confusion to an already complicated topic.
337
That's why I avoided it.
338
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.
339
I want you to know, though, that this availability of complex values plays a crucial role in other quantum algorithms, like Shor's for factoring numbers.
340
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.
341
The fact
342
that you begin by applying a certain operation to this equal balance state makes it very tempting to say
343
that the speedup comes from parallelizing the operation over all possible inputs.
344
But like I mentioned at the start, that summary, at least to me, just really doesn't feel right, and it definitely leads to misconceptions.
345
As you now know, that step on its own does nothing to reveal the key value.
346
I'll leave it up to your interpretation whether it feels apt
347
to describe this first step as applying a function to many inputs in parallel, or if it feels better to say that the balanced state is just its own new thing,
348
and the function we have always applies to individual inputs one at a time, never multiple at once.
349
It's just that those inputs are now a new kind of thing.
350
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.
351
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.
352
But if you're allowed to move diagonally, you can get there in the square root of 2.
353
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,
354
you can get there in the square root of n.
355
In the world view of quantum mechanics, different observable states all represent perpendicular directions in some state space.
356
So viewed from this framework, what the classical deterministic world looks like is one where you only have access to these pure coordinate directions.
357
And if you think about it, anytime that you're doing computation, your computer is somehow walking through a series of different states that are available to it,
358
and algorithmic runtime is all about understanding how many steps you have to walk in the space of all possible states.
359
So from this quantum world view, where classical states look like pure coordinate directions, the key difference with quantum computing is
360
that you now also have available to you a panoply of additional diagonal directions that you can work with.
361
Now to be clear the analogy is not too literal, you should take it with a grain of salt.
362
It's not like runtime necessarily looks like a distance traveled through this particular state space, but it is true that if you follow the state vector throughout Grover's algorithm,
363
what it's doing is slowly walking along a quarter circle arc from an initial condition to the target condition,
364
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.
365
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
366
because of a promised analogy between this algorithm and something we covered last video, about two colliding blocks that can compute pi.
367
In that video we are also studying a point in a certain two -dimensional state space, bouncing around a circle, and in fact,
368
the series of bounces that it took is essentially identical to what we just saw here with Grover's algorithm.
369
The story here is that when a physicist friend of mine, Adam Brown, saw the first version of that video,
370
he had recently been reading up on Grover's algorithm and immediately realized that both processes were identical.
371
Now I had this whole cockamamie plan for this video where I was going to explain quantum computing
372
and Grover's algorithm in the context of that analogy, but it turned out to be just a terrible idea.
373
The whole thing only really made sense if you already understood Grover's algorithm.
374
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.
375
Think of this as an open -ended homework puzzle, where the task is to draw the connection for yourself.
376
As an answer key of sorts, I will link to the very delightful paper by Adam Brown, outlining precisely what that analogy looks like.
377
If you want to learn more of the fundamentals of quantum computing, Several years ago, two very smart friends of mine, Andy Matuszczyk and Michael Nielsen, put together a really nice resource for learning the topic,
378
offering a pretty unique approach to making sure that you actually remember it in the long term.
379
To learn some of the fundamental quantum mechanics, Mithinayogonathan from the channel Looking Glass Universe has been putting together a very beginner -friendly course on the topic.
380
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.
381
And as a very last note to end on, one of the conversations I had while making this video was with Scott Aronson,
382
a very widely respected researcher and utterly delightful author on the topic.
383
I recorded the Zoom call for notes, and there's one little piece of it which I just wanted to share with you.
384
You know, I have this dream of writing a science fiction novel where, you know, I know what's going to be the climactic scene, where the heroes will be,
385
you know, running Grover's algorithm to try to find this cryptographic key, right?
386
The whole fate of the world will depend on whether they can find it.
387
OK, the bad guys have surrounded their base.
388
You know, they're bashing down the walls.
389
But Grover's algorithm is still running
390
and it has only like a 30 percent probability of giving you the solution if you measure.
391
So the question is, like, do you measure now or do you let it run for another minute?
392
Right.
393
And if you measure now that, you know, and you don't get it, then you've lost everything and you have to restart from the beginning.
394
So this is not a plot that you could have with any classical algorithm.
📺 Mesmo canal
C14
Fourier series
American AccentUniversity StudentsWorking Adults
C112
Essence of linear algebra preview
American AccentBusiness EnglishUniversity StudentsWorking Adults
C13
The inscribed square problem
American AccentUniversity StudentsWorking Adults
C12
Euler's Formula Poem
American AccentIELTS PrepTOEFL PrepUniversity Students
C11
Linear combinations, span, and basis vectors | Chapter 2, Essence of linear algebra
American AccentCambridge Exam PrepUniversity StudentsWorking Adults
C13
The Newton art puzzle
American AccentUniversity StudentsWorking Adults
C12
How might LLMs store facts | Deep Learning Chapter 7
American AccentIELTS PrepTOEFL PrepUniversity Students
C15
Transformers, the tech behind LLMs | Deep Learning Chapter 5
American AccentBusiness EnglishUniversity StudentsWorking Adults
C235
Large Language Models explained briefly
American AccentBusiness EnglishUniversity StudentsWorking Adults
C21
Hilbert's Curve: Is infinite math useful?
American AccentBusiness EnglishUniversity StudentsWorking Adults
C12
Vectors | Chapter 1, Essence of linear algebra
American AccentBusiness EnglishUniversity StudentsWorking Adults
C23
But what is a neural network? | Deep learning chapter 1
American AccentBusiness EnglishUniversity StudentsWorking Adults
C12
Oh, wait, actually the best Wordle opener is not “crane”…
American AccentBusiness EnglishUniversity StudentsWorking Adults
C1Divergence and curl: The language of Maxwell's equations, fluid flow, and more
American AccentBusiness EnglishUniversity StudentsWorking Adults
C1Tie random ends: How many loops?
American AccentUniversity StudentsWorking Adults
✨ Vídeo recomendado
C12
162 frases
Crypto Agility Explained: Protect Data from Quantum Computing Threats
Business EnglishUniversity StudentsWorking Adults
C115
37 frases
Nvidia CUDA in 100 Seconds
American AccentBusiness EnglishUniversity StudentsWorking Adults
C12
255 frases
Physicist Brian Cox explains quantum physics in 22 minutes
Business EnglishUniversity StudentsWorking Adults
C13
58 frases
The mystery is solved... and the answer is 40x cheaper than Claude
American AccentBusiness EnglishUniversity StudentsWorking Adults
C12
283 frases
The Banach–Tarski Paradox
American AccentUniversity StudentsWorking Adults
C16
249 frases
My Puzzle Robot is 200x Faster Than a Human
American AccentBusiness EnglishUniversity StudentsWorking Adults
C17
107 frases
Gaussian Naive Bayes, Clearly Explained!!!
Business EnglishUniversity StudentsWorking Adults
C11
54 frases
Traceroute: You're Probably Reading the Results Wrong
Business EnglishUniversity StudentsWorking Adults
C18
156 frases
How Quantum Batteries Break Every Rule of Charging
Business EnglishUniversity StudentsWorking Adults
C14
81 frases
Turing & The Halting Problem - Computerphile
Business EnglishUniversity StudentsWorking Adults
Vocabulário e dicas de fala para esta lição
Este vídeo tem 394 frases e 7483 palavras para praticar shadowing. A fala dura 36:39. O falante fala rápido, cerca de 204 palavras por minuto, então espere sons ligados e reduzidos. Apenas 80% das palavras estão entre as 3.000 mais comuns do inglês, por isso o vocabulário é exigente.
Vocabulário principal deste vídeo
15 palavras menos comuns do vídeo, com pronúncia e significado:
- vector /ˈvɛktɚ/ (substantivo) — vector, vetor. A directed quantity, one with both magnitude and direction; the signed difference between two points.
- quantum /ˈkwɑntəm/ (substantivo) — quantidade. The total amount of something; quantity.
- algorithm /ˈælɡəɹɪðm̩/ (substantivo) — algoritmo. A collection of ordered steps that solve a mathematical problem. A precise step-by-step plan for a computational procedure that possibly begins with an input…
- flip /flɪp/ (verbo) — virar. To throw so as to turn over.
- component /kəmˈpoʊ.nənt/ (substantivo) — componente. A smaller, self-contained part of a larger entity. Often refers to a manufactured object that is part of a larger device.
- probability /ˌpɹɑ.bəˈbɪl.ə.ti/ (substantivo) — probabilidade. The state of being probable.
- coordinate /koʊˈɔɹ.dəˌneɪt/ (verbo) — coordenar. To place in the same order or rank.
- gate /ˈɡeɪ̯t/ (substantivo) — portão. A doorlike structure outside a house.
- correspond /ˌkoɹəˈspɑnd/ (verbo) — corresponder. To be equivalent or similar in character, quantity, quality, origin, structure, function etc.
- string /stɹɪŋ/ (substantivo) — barbante, corda. A long, thin and flexible structure made from threads twisted together.
- angle /ˈæŋ.ɡəl/ (substantivo) — ângulo. A figure formed by two rays which start from a common point (a plane angle) or by three planes that intersect (a solid angle).
- dimensional /daɪˈmɛn.ʃə.nəl/ (adjetivo) — dimensional. Of or pertaining to dimensions.
- analogy /əˈnæləd͡ʒi/ (substantivo) — analogia. A relationship of resemblance or equivalence between two situations, people, or objects, especially when used as a basis for explanation or extrapolation.
- topic /ˈtɑpɪk/ (substantivo) — tópico, assunto. A subject; a theme; a category or general area of interest.
- helpful /ˈhɛlp.fl̩/ (adjetivo) — prestável, útil. Furnishing help; giving aid; useful.
Phrasal verbs que você vai ouvir
- come from (verbo) — vir de, ser de. To have as one's origin, birthplace or nationality.
- think about /ˈθɪŋk əˌbaʊt/ (verbo) — pensar em, pensar sobre. To ponder.
- look at (verbo) — observar, ver. To observe or watch.
- go up (verbo) — subir. To move upwards.
- put together (verbo) — montar, construir. To assemble, construct, build, or formulate.
- take on (verbo) — aparecer. To acquire, bring in, or introduce.
- call for (verbo) — chamar. To shout out in order to summon (a person).
Pronúncia para ficar de olho
O falante usa 82 contrações e formas reduzidas, como you're, I'm, I'll. Diga-as na forma curta, do jeito que você ouve.
- Os sons de “th”: algorithm /ˈælɡəɹɪðm̩/, mathematics /mæθ(.ə)ˈmæt.ɪks/, southeast /sawˈθɪjst/
- Os sons de “sh” e “zh”: dimensional /daɪˈmɛn.ʃə.nəl/, dimension /daɪˈmɛn.ʃən/, measurement /ˈmɛʒ.ə.mənt/, essentially /ɪˈsɛnʃəli/, potentially /pəˈtɛnʃ(ə)li/
- Palavras longas — acerte a sílaba tônica: probability /ˌpɹɑ.bəˈbɪl.ə.ti/, coordinate /koʊˈɔɹ.dəˌneɪt/, dimensional /daɪˈmɛn.ʃə.nəl/, analogy /əˈnæləd͡ʒi/, fundamental /ˌfʌn.dəˈmɛn.təl/
Como praticar com este vídeo
- Ouça o vídeo inteiro uma vez sem falar e anote as palavras que você não conhece.
- Comece na velocidade 0,75×, faça shadowing frase por frase e volte à velocidade normal quando ficar fácil.
- Grave a sua voz e compare com o original, prestando atenção a palavras como vector, quantum, algorithm.
Gramática neste vídeo
As estruturas que o falante mais usa, com as palavras exatas do vídeo:
| Estrutura | No vídeo |
|---|---|
| Present perfect continuous have/has been + -ing — uma ação que começou antes e continua | I've been showing · I've been telling · has been putting |
| Frases condicionais if + oração, will/would + verbo — uma condição e seu resultado | if you are curious, I'll show · if you like this content, it would mean |
| Voz passiva be + particípio passado — o foco está no que acontece, não em quem faz | is stored · would be revealed · was proven |
| Present perfect have/has + particípio passado — uma ação passada que ainda importa agora | I've asked · have not defined · we've seen |
O que é a Técnica de Shadowing?
Shadowing é uma técnica de aprendizado de idiomas com base científica, originalmente desenvolvida para o treinamento de intérpretes profissionais. O método é simples, mas poderoso: você ouve áudio em inglês nativo e repete imediatamente em voz alta — como uma sombra seguindo o falante com 1-2 segundos de atraso. Pesquisas mostram melhora significativa na precisão da pronúncia, entonação, ritmo, sons conectados, compreensão auditiva e fluência na fala.