Raw transcript — Where my explanation of Grover’s algorithm failed

Source: https://www.youtube.com/watch?v=Dlsa9EBKDGI Duration: 16m 23s Captured: 2026-04-20

Full clean transcript stored at /tmp/yt-process/Dlsa9EBKDGI.txt during ingestion (3,214 words). Per copyright policy, raw transcript preserved for internal reference. Re-download via:

yt-dlp --write-auto-sub --sub-lang en --skip-download --sub-format vtt -o "%(id)s" "https://www.youtube.com/watch?v=Dlsa9EBKDGI"
python3 ~/.claude/scripts/vtt-to-text.py Dlsa9EBKDGI.en.vtt

Last week, I put up a video introducing quantum computing. And in the final section, we were stepping through something known as Grover’s algorithm. And based on the comments that I saw, I think there was a very common point of confusion that reveals I clearly could have done a better job explaining a core piece of it. Right here, I wanted to throw together a very quick supplement in the hopes of adding a bit of clarity. The premise was to have a function which is somehow triggered by a unique value out of a big bag of options. And the puzzle is basically to figure out how do you find that unique value just by applying the function on various inputs.

[00:01:00] One of the axes in that space corresponded to the value that we’re searching for. And this step of the algorithm looked like flipping along that axis, multiplying any component of a vector in that direction by -1. Now, viewers were essentially asking, “Whoa, whoa, whoa. How could you know how to do that without already knowing which axis you’re searching for?” I genuinely tried to forestall that objection, but I think I failed. So, backing up, I think the whole discussion might be clearer if we focus on a very concrete example, something like solving a sudoku. On your normal classical computer, it’s not hard to write a function that checks whether a proposed solution follows all of the Sudoku rules.

[00:02:00] The function SHA 256, for example, is what’s called a cryptographic hash function. That basically means if you want to find what input gives you a particular output, it is strongly believed that you really can’t gain much insight by looking at how the function is implemented. If someone could reverse engineer it, they would be mining all of the Bitcoin in the world and breaking numerous other cryptographic schemes. But it’s believed that the best thing you can do when you’re searching for a particular output is guess and check. So it’s not that the key value is like hiding inside the function behind some curtain. It’s more of a difficult to find emergent phenomenon of the function itself. The idea with Grover’s algorithm is that if you have this sort of verifier function for some hard problem and you translate it into the language of quantum computing, there is a method for sifting out valid solutions which requires fewer steps than simple guessing and checking.

[00:03:00] To be clear, it is not dramatically faster. It’s only a quadratic speed up. And given the overheads for making quantum computing work, this frankly has questionable utility. The first step to port over this verification function into the new context is to imagine that we’ve kind of compiled your verifier into a bunch of logic gates, things like and, or, and not. So for any proposed Sudoku solution, you would represent it all in binary. All of those bits would be processed by your web of logic gates and the output would be a one if it’s a valid Sudoku solution and a zero for all the invalid ones. Being able to assemble these logic gates does not require knowing ahead of time which input solves the puzzle. The logic gates distill the rules of the game, but not the strategy.

[00:04:00] The state vector recap. If you have a k cubit quantum computer, that gives you 2 to the k possible bit strings, and you think of each one of them as being a coordinate direction in some very high-dimensional vector space. Operations on a quantum computer don’t spit out true or false. Instead, they take in a vector and they spit out a new vector, both of which live in the same space. They flip or rotate vectors in that space.

[00:05:01] Here’s the crux of the confusion. If you have this classical verifier function, something like a sudoku checker that spits out a one or a zero, it is possible to translate it into an operation on a quantum computer that has the following behavior. If a bit string returns one for true up in the classical case, then down in the quantum case, the corresponding basis vector gets multiplied by negative 1, effectively flipping 180°. And if in the classical case, a bit string outputs zero for false, then in the quantum translation, the corresponding basis vector is unchanged.

[00:06:00] The relevant search term here is quantum compilation. Loosely speaking, every time you see an AND gate, you translate it into a quantum operation that looks kind of like an and. Every time you see a not gate, there’s a quantum analog that does something kind of like a not. The real cause of confusion originates not from a lack of low-level detail, but from how I framed the entire setup. I opened that video by having you imagine that there was some mystery number that we’re searching for. As one commenter helpfully pointed out, this made it seem like the computer kind of knows the answer ahead of time. It’s just hiding it from us.

[00:07:00] What I wanted to foreshadow is how with Grover’s algorithm, the only way you use the new quantum function is by trying it out on inputs as opposed to maybe like reverse engineering it. So in that sense, it’s treated as a black box. But to be clear, in order to translate the classical verifier into the quantum version, you absolutely need to get into the guts of the function. The Sudoku example is much better and a cryptographic hash like Sha 256 would be much better still. In these contexts, there is one value that will trigger the function and we don’t know what it is. But the computer also doesn’t know what it is. It’s not like the key value is just hiding in the source code.

[00:08:00] The other potential source of confusion is that I didn’t appropriately emphasize the idea of linearity. This is a central enough feature of quantum computing and quantum mechanics that half of my reason for making this whole follow-up video is as an excuse to talk about it. Most vectors don’t look like a pure basis direction. They look like some weighted sum of all the different basis vectors. The more common convention among physicists is to write general vectors as an explicit weighted sum of all the basis directions, each one represented with a ket. When the state vector for a computer looks like this, you say that it’s in superposition.

[00:09:00] When you read out from the computer, all you see is one of the bit strings at random. And the probability of seeing it is equal to the square of the magnitude of the component of the state vector associated with that value. When I say that operations in quantum computers are linear, what I mean is that if you pass in one of these weighted sums of the different basis directions, that is to say a superposition, then the output looks like the same weighted sum but of the transformed versions of each vector. The Z-gate example: leaves zero direction unchanged, multiplies the vertical one direction by -1.

[00:10:02] If you pass in a superposition of those two, what you do is look at what the Z-gate does to each part separately and then add those together again with the same components. The Z-gate is simple enough that just by looking at the definition, you can clearly see which direction gets flipped. But for more complicated functions, the definition alone might not so easily reveal how it behaves. Take a look back at the Sudoku verification function and its translation onto a quantum computer and then say that the state of your computer is a combination of all the basis vectors, a superposition of every possible bit string in this context representing every possible solution to the sudoku.

[00:11:01] When you do this, it’s very tempting to look at it and say that the function is acting on every possible basis vector at once in parallel. That might be true, but I invite you to reflect on whether that’s necessarily a fair way to summarize it. As an analogy, if a hiker is walking northeast and you tell him to rotate 90°, that rotation is a linear operation. The final direction is the same as what you would get by rotating the north vector 90°, rotating the east vector 90°, and adding the two results. But that doesn’t mean that you have to perform two separate rotations in parallel in order to move the hiker. The linearity is a property of the transformation. It’s not necessarily a set of instructions on how to do it.

[00:12:00] The effect of the quantum translation for our verifier looks like adding together what its effect would be on all of the basis vectors. But I will leave it to your interpretation whether this means that it is necessarily acting on all 2 to the k possible bit strings at once. The starting point of Grover’s algorithm is to assume that you’re given a function that flips one component of a vector like this, though you don’t know which one. The puzzle is to somehow figure out which direction is getting flipped, where all you’re allowed to do is apply this function to some well-chosen set of inputs.

[00:13:00] When we visualized the algorithm, we chose to view everything on a certain two-dimensional slice of the enormous n-dimensional vector space where all these state vectors live. And this slice by definition included the axis associated with that mystery value we’re searching for. In case that left anyone with the impression that part of the algorithm was to choose that slice, let me be very clear. It’s not. The algorithm is just doing what it’s going to do. It interleaves two operations that go back and forth. It doesn’t have a care in the world how you and I choose to visualize it. The fact that the state vector stays confined to this particular plane, that’s a happy emergent property of the algorithm.

[00:14:01] One very final thing that I do think deserves some added reflection is how Grover’s algorithm, while very thought-provoking, is maybe just not really useful. Take the Sudoku example. The number of possible solutions will depend on how many of those 81 squares start off blank. But let’s call it something like 9 ^ 60. Even if you had a fully functioning quantum computer sitting on your desk right now, using Grover’s algorithm, this would still take around 9 to the 30 steps, which is a much smaller number, but it’s still enormous.

[00:15:00] If you take something like Sha 256, inverting it by brute force takes 2 to the 256 steps on a classical computer. Using Grover’s algorithm, that becomes 2 to the 128, at least up to that pi/4s constant that we saw last video. So even in some sci-fi future where quantum computers are as far along as today’s classical computers, that is still an infeasibly large number of steps. The way some people write about quantum computing, it makes it sound like the moment they arrive, everything is going to change and all of cryptography will break. And it’s true that there are specific problems that have exponential speedups, and especially with RSA, some of those are relevant to cryptography, but that’s not true in general. This quadratic speedup is much more representative of what you get for most problems.

[00:16:00] One of my hopes with this whole project is that you now have enough background to maybe see through some of the hyperbole that certain outlets are so fond of.