Shadowing Practice: But what is quantum computing? (Grover's Algorithm) - Learn English Speaking with Video

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 computers can be faster by by basically doing whatever a classical computer would do, but to all of these sequences in parallel.

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.

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 warm -up question is, how many times, on average, would you have to apply this mystery function in order to find the secret key?

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 run times scale.

If you had a list ten times as big, how much longer would it take?

And computer scientists have a way of categorizing run times.

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 10, the runtime also goes up by a factor of 10.

Now, here's your quiz.

For the equivalent of this setup, but in a quantum computer, 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 1, where here o of 1 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.

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.

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 .

And this is wrong, and I'm pretty sure that it stems from that misleading summary.

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 , 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 runtime would only tick up by the same additive increment each time.

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.

In 1994, it was proven that a quantum computer could not possibly do any better than O on this task.

And then two years later, Law of 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, 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.

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.

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, 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.

But today, the goal is to provide the minimal viable path to seeing a genuine bona fide quantum algorithm.

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,

like voltages across a capacitor or something like that.

Now 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.

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 You don't need to distinguish between the state of 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 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.

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.

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.

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.

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.

📺 Same Channel

Essence of linear algebra preview

Business EnglishUniversity StudentsWorking Adults

Linear combinations, span, and basis vectors | Chapter 2, Essence of linear algebra

Cambridge Exam PrepUniversity StudentsWorking Adults

✨ Recommend Video

162 sentences

Crypto Agility Explained: Protect Data from Quantum Computing Threats

Business EnglishUniversity StudentsWorking Adults

37 sentences

Nvidia CUDA in 100 Seconds

Business EnglishUniversity StudentsWorking Adults

255 sentences

Physicist Brian Cox explains quantum physics in 22 minutes

Business EnglishUniversity StudentsWorking Adults

58 sentences

The mystery is solved... and the answer is 40x cheaper than Claude

Business EnglishUniversity StudentsWorking Adults

283 sentences

The Banach–Tarski Paradox

University StudentsWorking Adults

249 sentences

My Puzzle Robot is 200x Faster Than a Human

Business EnglishUniversity StudentsWorking Adults

107 sentences

Gaussian Naive Bayes, Clearly Explained!!!

Business EnglishUniversity StudentsWorking Adults

54 sentences

Traceroute: You're Probably Reading the Results Wrong

Business EnglishUniversity StudentsWorking Adults

156 sentences

How Quantum Batteries Break Every Rule of Charging

Business EnglishUniversity StudentsWorking Adults

81 sentences

Turing & The Halting Problem - Computerphile

Business EnglishUniversity StudentsWorking Adults

Vocabulary and speaking notes for this lesson

This video has 394 sentences and 7483 words to shadow. The speech runs for 36:39. The speaker talks fast, about 204 words per minute, so expect linked and reduced sounds. Only 80% of the words are among the 3,000 most common in English, so the vocabulary is demanding.

Key vocabulary in this video

15 less common words from the video, with pronunciation and meaning:

vector /ˈvɛktɚ/ (noun) — A directed quantity, one with both magnitude and direction; the signed difference between two points.
quantum /ˈkwɑntəm/ (noun) — The total amount of something; quantity.
algorithm /ˈælɡəɹɪðm̩/ (noun) — 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/ (verb) — To throw so as to turn over.
component /kəmˈpoʊ.nənt/ (noun) — 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/ (noun) — The state of being probable.
classical /ˈklæs.ɪ.k(ə)l/ (adjective) — Of or relating to the first class or rank, especially in literature or art.
coordinate /koʊˈɔɹ.dəˌneɪt/ (verb) — To place in the same order or rank.
gate /ˈɡeɪ̯t/ (noun) — A doorlike structure outside a house.
correspond /ˌkoɹəˈspɑnd/ (verb) — To be equivalent or similar in character, quantity, quality, origin, structure, function etc.
string /stɹɪŋ/ (noun) — A long, thin and flexible structure made from threads twisted together.
angle /ˈæŋ.ɡəl/ (noun) — 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/ (adjective) — Of or pertaining to dimensions.
analogy /əˈnæləd͡ʒi/ (noun) — 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/ (noun) — A subject; a theme; a category or general area of interest.

Phrasal verbs you will hear

read out /ˌɹiːd ˈaʊt/ (verb) — To read something and say the words to inform other people; to call.
come from (verb) — To have as one's origin, birthplace or nationality.
think about /ˈθɪŋk əˌbaʊt/ (verb) — To ponder.
build up (verb) — To erect; to construct.
look at (verb) — To observe or watch.
search for (verb) — Synonym of look for.
go up (verb) — To move upwards.
put together (verb) — To assemble, construct, build, or formulate.

Pronunciation to watch

The speaker uses 82 contractions and reduced forms, such as you're, I'm, I'll. Say them the short way, as you hear them.

The “th” sounds: algorithm /ˈælɡəɹɪðm̩/, mathematics /mæθ(.ə)ˈmæt.ɪks/, southeast /sawˈθɪjst/
The “sh” and “zh” sounds: dimensional /daɪˈmɛn.ʃə.nəl/, dimension /daɪˈmɛn.ʃən/, measurement /ˈmɛʒ.ə.mənt/, essentially /ɪˈsɛnʃəli/, potentially /pəˈtɛnʃ(ə)li/
Long words — get the stress right: 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/

How to practise with this video

Listen to the whole video once without speaking and note the words you do not know.
Start at 0.75× speed, shadow it sentence by sentence, then go back to normal speed once it feels easy.
Record yourself and compare with the original, paying attention to words like vector, quantum, algorithm.

Grammar in this video

The structures the speaker uses most, with the exact words from the video:

Structure	In the video
Present perfect continuous have/has been + -ing — an action that started earlier and is still going on	I've been showing · I've been telling · has been putting
Conditional sentences if + clause, will/would + verb — a condition and its result	if you are curious, I'll show · if you like this content, it would mean
Passive voice be + past participle — the focus is on what happens, not who does it	is stored · would be revealed · was proven
Present perfect have/has + past participle — a past action that still matters now	I've asked · have not defined · we've seen

What is the Shadowing Technique?

Shadowing is a science-backed language learning technique originally developed for professional interpreter training and popularized by polyglot Dr. Alexander Arguelles. The method is simple but powerful: you listen to native English audio and immediately repeat it out loud — like a shadow following the speaker with just a 1–2 second delay. Unlike passive listening or grammar drills, shadowing forces your brain and mouth muscles to simultaneously process and reproduce real speech patterns. Research shows it significantly improves pronunciation accuracy, intonation, rhythm, connected speech, listening comprehension, and speaking fluency — making it one of the most effective methods for IELTS Speaking preparation and real-world English communication.

Shadowing technique: read the full step-by-step guide →

Shadowing Practice: But what is quantum computing? (Grover's Algorithm) - Learn English Speaking with Video

Essence of linear algebra preview

Linear combinations, span, and basis vectors | Chapter 2, Essence of linear algebra

Euler's Formula Poem

The inscribed square problem

The Newton art puzzle

How might LLMs store facts | Deep Learning Chapter 7

Transformers, the tech behind LLMs | Deep Learning Chapter 5

Fourier series

Hilbert's Curve: Is infinite math useful?

Vectors | Chapter 1, Essence of linear algebra

Large Language Models explained briefly

But what is a neural network? | Deep learning chapter 1

Oh, wait, actually the best Wordle opener is not “crane”…

Divergence and curl: The language of Maxwell's equations, fluid flow, and more

Tie random ends: How many loops?

Crypto Agility Explained: Protect Data from Quantum Computing Threats

Nvidia CUDA in 100 Seconds

Physicist Brian Cox explains quantum physics in 22 minutes

The mystery is solved... and the answer is 40x cheaper than Claude

The Banach–Tarski Paradox

My Puzzle Robot is 200x Faster Than a Human

Gaussian Naive Bayes, Clearly Explained!!!

Traceroute: You're Probably Reading the Results Wrong

How Quantum Batteries Break Every Rule of Charging

Turing & The Halting Problem - Computerphile

Vocabulary and speaking notes for this lesson

Key vocabulary in this video

Phrasal verbs you will hear

Pronunciation to watch

How to practise with this video

Grammar in this video

What is the Shadowing Technique?