- The confusion
- | Introduction and Confusion About Grover's Algorithm
- | Classical Verifier Functions and Examples
- Example: Sudokus
The sudoku grid at has 11,447 solutions so this is already a good example of a function with multiple correct inputs.
Trivia: I wanted to try my hand at the example sudoku at , so I entered it into a grid on a website and asked it to check. It turns out that puzzle has 11447 solutions, so it cannot be solved logically. Oh well.
Don't try to reverse-engineer SHA-256, kids - you'll just make a hash of it.
- | Utility and Speedup of Grover's Algorithm
"Its not like the key value is hiding inside the function behind some curtain, its more of a difficult to find EMERGENT PHENONMENON of the function of itself". THIS, i believe is the primary source of the confusion. Its not necessarily the inputs or the outputs of the function: its the behavior of the function itself that is of interest. I believe this is the fundamental point that you need to elaborate on, and when you develop your exemples you need to tie it back to the behavior of the function itself.
- | Compiling Classical Functions into Quantum Logic
. This is a minor correction on terminology. When you take a function and turn it into logic gates in classical computing that's called synthesis, not compilation. I understand that using the correct term in the video won't help the average viewer understand the core point of the video any better, but maybe It could be adjacently useful for someone early into studying CompE.
- | Quantum State Vector Manipulation
- | Grover's algorithm leverages the translation of classical verifier functions into quantum operations that manipulate vector states, enabling the search for solutions without knowing them beforehand, thus bridging classical verification and quantum computation.
I think I had my confusion resolved within ~ min. I failed to grasp, that the quantum algorithm manipulates the probability distribution of the current 'state' and is programmed for a specific case (like a sudoku solver). Now I can just accept the mentioned operations (multiplication by -1, or flipping around some vector) exist and be happy with the explanation. I also wonder if I could have just reviewed the first video, but the opportunty to that experiment is now lost to me 😆Thanks!
- | Clarifying the Quantum Operation and Addressing Confusion
A quantum leap?
At about @-ish you're talking about whether it was too much of a leap - it wasn't, I'd come to that conclusion from what you said, but it still felt pretty magical I think mainly because you skimmed over it quite quickly. It was almost like sleight-of-hand in that I got the idea but it did leave me with a slight dissatisfaction/unsureness about whether I'd extrapolated correctly what you were driving at. This clarification was exactly what was needed, and honestly I can't say it doesn't work better as an addendum rather than being a diversion in the main video!
@@kindlin Well, he did sort of explain how it would be translations of the logic gates into operations on the state vector (which would be rotating it, flipping it in certain ways etc.), but that () going into more detail wouldn't actually give better clarity, which was the point of this video. So basically he said that's too into the weeds for this video 😉
Hey, I really respect you as an educator, I think you generally do great work, but I think you do yourself and your audience a disservice at when you imply a large language model like Claude can help explain a topic like this. You've done videos on how LLMs work- surely you know their output has no real relationship to the truth. They're great at producing probable sequences, but they're much more likely to produce plausible or almost-correct misinformation than any actual answers. Offering it for a complicated topic your audience may already be confused about is disappointing to say the least!
in Video
Also as a side-note, the Brooklyn Nine-Nine reference at was totally unexpected but I absolutely love it!! Instantly recognised it - name one law :) pretty cool to see that you (probably) like it too.
For me, the biggest revelation of this video was . In order to translate it to a quantum computer, you DO need to know the contents; it isn't just a "quantum wrapper" around a normal function. This is what I would have thought was the case, but, as you identified, the combination of the "black box" phrasing and showing that the function clearly knows the search value made it seem like this couldn't be the case. Then you would find the answer in the process of translating the function to quantum. Perhaps an example such as "can make platonic solid n-gon with pentagons" is a good example since it clearly doesn't "know" it's own answer, would theoretically be difficult to check, but it's also pretty clearly just 12.
that to return true we flip the ENTIRE input vector (every "bitstring's" vector), but then it feels like suddenly to return true we only flip the vector at a certain bitstring. This is almost certainly my misunderstanding of the difference between the k dimensional representation or whatever and the vector of a specific qubit, but it really is confusing me. Like in a classical sense it feels like I would need some huge number of "bitstring" positions to represent every sudoku position to even begin to use the verification function, how could a quantum computer even set up that environment to work under? Does it require a huge number of qubits to work? If each qubit could only represent
"Which specific key input does this is a difficult to find and emergent property of those logic gates"
- Linearity
i like that the "half of the reason for making this video" comes at the halfway timestamp
- | Quantum Superposition and Linearity
hate to break it to you but that is a misunderstanding of quantum superposition grant! It doesn't correspond to north and east. Mahesh Shenoy posted a video targeting this misconception.
that velocity analogy was helpful to understand superposition
When you can't even say my nameHas the memory gone? Are you feeling numb?Go and call my nameI can't play this game, so I ask again...
The state vector component magnitudes can be a complex number as well?? Yikes.. Just as I thought I was maybe starting to understand it just a little bit.. 😅
I think the confusion must come from the fact that we don't know the actual vector, only the measured result which comes from the probabilities. And the trouble is |1011⟩ gives the same probability as -|1011⟩ (it's squared right?) but even then, we only get one sample result when we measure it. So the function itself doesn't get us much.
this is the kind of explanation I was hoping for in the main video when i was confused about the same thing. "i know quantum computing is an entirely different beast than classical, so what logic gates do we have to work with and what do they do?" just as a baseline understanding to show that translating an arbitrary classical function into a quantum one is possible. The sudoku case is a great example as its easy to understand what the check function does, and the key value that gets its axis flipped by the quantum check function is not because it is "the sudoku solution we are looking for" but instead because its is "a valid sudoku solution"
- | Linearity in Complex Quantum Functions
At the term "solution" is a little overloaded. The mention of "every possible solution" means incorrect solutions also. A few seconds later "solution" is used to mean just the correct solution.
I think the part that confuses me the most is at . In classical computing it feels like this would be like generating every possible configuration (the shear size of the possible configurations here is what really breaks this for me), asking the function if it's valid (idc whether or not it's parallel, it just happens), and then returning some array of booleans where one of them is true, but due to some arbitrary physical limitation (quantum computing) it takes us a little bit to "retrieve" that solution from the result array. It feels as if the algorithm requires that the blackbox return some sort of state other than true false (I know I'm beating a dead horse sorry). Like I thought I understood from 2 bitstrings max (it has the 0 and 1 axis) then wouldn't we need tons of them to represent all possible states of a sudoku board in the input (very high dimensional) vector of the verification function? I really would love to understand this, and I think it comes from just a misunderstanding of the physical implementation of that input vector for the verification function.
As you see in , the quantum gate somehow flips a value (which is a fair function), but (a) why is it statistically very likely in every run the same vector index, (b) how does Z behave when the number of dimensions is low / in the RSA prime size and keeps its statistic significance on the vector index, and (c) why does the flipping happens in exactly the qubit that is statistically very likely to be of (cryptography) relevance here?
phase (I think this is where the "in parallel" analogies stem from ( in Video 2)). It's not so much a question or confusion around Grover's Algorithm. But that first step that causes us to need Grover's Algorithm is the confusing magic that is just too much. I know you said you didn't want to show how the gates works because showing classical gates wouldn't help you understand a calculator (2), but I think THAT is the crux of it for most people... even though your video clearly clarifies that it's about Grover's Algorithm with the parenthetical title. For me I think I do want to study up on quantum compilation, so thank you for calling that out.
Does the part at tell us that at the end it's just : "quantum computing does all thing in parralel but we need O(sqrt(N)) to decode the result" or is there something big I missed ?
That is an excellent point about whether quantum computing can be considered parallel or not. I think the most important part about it is what usefulness we can get from it that we can't get from other forms of computation. However, since we never actually get more than one input out despite the amount of "parallelization" we can get depending on the design of the machine, it depends on how we want to say we got the result.For instance, performing an operation on a superposition of North and East may not matter whether we do it on both directions at the same time or on the superposition itself, what matters is whether we need to pay attention to something happening to a specific direction, as in the case of quantum computing. If you need to know which cardinal direction you are closest to facing at the end of a bunch of turns, it may be more useful to think of each cardinal direction being operated on separately rather than as a single angle, for instance.Of course, it all depends on the problems, the framing, the operation, and the interpretation of results. I still like to think of Grover's algorithm as being a parallel operation on many elements of a vector with the same operation, even though one can only get a "scalar" result. At least that is how it makes sense to me.
This analogy really cleared things up for me. Choosing this basis for the state space certainly makes it look like the function "knows" which direction is the answer, but the function exists independent of what basis we chose.
I found the hiker explanation at very helpful! (Also it is comforting to know that even 3b1b, best at explaining there is, sometimes is unsure whether he's over- or under-explaining :)
I still don't get it, but I feel that the vector composition part at maybe helps a bit. What if instead of talking about a bunch of 3D vectors combining, it was illustrated as a bunch of 2D vectors, all added head to tail. Maybe each little vector is like a each state, and then the vector as a whole is what you get added up, and then the algorithm will change those and we can see how the vector as a whole changes. I'm just not sure what the analogy would be. Maybe it would be like rotating all but one vector? But then we can still subtract the two vectors to get the true answer. Maybe it's more like all of the vectors are random, except the one true one? So you can find the most likely average vector? But then I don't understand how that would pertain the iterating it.
- | Understanding the linearity of quantum operations helps clarify that Grover's algorithm, while theoretically powerful, offers limited practical speedup for extremely large problems, tempering expectations about quantum computing's impact.
so - if i understand it correctly, the key is simply the only one to respond properly or respond at all to you trying to flip it
I'd say Yes, because as someone else said, each section holds a unique piece of information that do not affect each other , but also because in every practical term of the process, specially in the context of this algorithm, it is applying the check algorith to all parts of the vector in the same function and command. I think for me personally the confusion came from the statement "not just running parallel" with an emphasis on "not", when the algorith relied on a check that was effectively just "running parallel" what needed emphasis was the "just", nevertheless, the rest of the explanations made sense in the context of assuming the shorter leaps in logic to be true, it was the major leap of assuming there was a function that was both impossible outside quantum and was not effectively just running parallel checks on all parts of the vector. Which just to clarify, to me and many others, that is what is happening because it is applying the function to each part of the vector at the same time as even with the linearity, it's not the same effect for all like in the cardinal directions example (even if it technically is because of rotating around an axis in this case, as with many others it will not be simply one rotation), I do understand the danger of the generalization of parallel computing, but I believe it would be more understandable for most if it is stated that there are more required steps BESIDES the parallel computing rather than saying there is no parallel computing.
- | Grover's Algorithm Basics
At about was the place where it all cleared up for meWe dont make, but already have the initial function that flips one value out of many (the quantum equivalent of sha256 for example)and then we apply to the result out new functionthats pretty much where i got confused in previous video
Great job on adding clarity! does a great job of explaining the conditions under which Grover's Algorithm applies, but your summary at
I think the root issue is that the point at was not emphasized enough, and the way it's visualized implies we know what the vector looks like. If it was a vector with all values "blurred" until we get the final output, that might have made it more clear that we can't see the vector the way the video portrays it
aah, so the operator that we're applying onto the state is the quantum translation of the original verifier. This is what was missing for me! This is fundamental to understand the whole idea. Thank you for explaining better.
that clicked for me
so how is the well chosen set of inputs chosen, and what is that other operation? Does it entirely depend on the original problem and the verifier? If so, how are they used to find the input set and the 2nd operation?
I think the animation in is clear
Instead, we need to do the full M steps of Grover's algorithm to slowly increase the likelihood of reading outcome |k> when we take a measurement of the latest vector output by the "circuit" after each of the M steps (the vector shown as "wires" between boxes at in the first quantum video, let's call those M vectors the "result" vectors, since the video doesn't give them a name). We keep doing more and more steps until we maximize the probability of measuring a "result" vector as outcome |k> (and M steps is the right number of steps for this). The fact that we have to do this M times is why it's not an O(1) algorithm. The fact that we have to do this M times is why it's partially misleading to say we're "testing all the outcomes in parallel" (since WE can't just connect a multitester lead to check the probability of an individual outcome of any given "result" vector) though I still think it's CRITICAL FOR TEACHING to say that the quantum computer is trying all the outcomes "in parallel" so people can have a sense of what's going on and why there would ever be any speedup.
sir you're under-explaining things and over-explaining things at the same time, it's quantum computing DUHH
- | Geometric Interpretation of Grover's Algorithm
this was the only part that was a little confusing from the last video for me, thank you
undermines the explanation, because one of the operations necessarily confines the state vector to the 'critical planes' which contain valid solutions.
at In fact, the fact that the vector is confined to a plane is a consequence of the fact that there is only 1 "right" solution we are looking for, which effectively create a single "cutting plane" for the algorithm. But if there were 2 solutions, it would not be a plane anymore, but a volume for instance.... (if my understanding is right).
- | Practical Limitations and Realistic Expectations
- Is this useful?
There are applications where you can narrow the search space such that the square-root speedup becomes practically relevant. E.g., if you are trying to crack an 8-character password based on its hash value, the difference is between O(2^64) and O(2^32), which under a few reasonable assumptions is years vs. minutes. Hence the trend toward using long passphrases instead of short passwords.
[] Even if other algorithms don't break cryptography, at least the Shor's Algorithm will.
-- the brown Pi shitting on the quantum computing hot shuff is a nice touch :)
