- Misconceptions
The video starts with a "mystery function f(n)", and it really looks like a black box algorithm setting. ()
12 is my favorite number. i am somehow flattered that it's the one that is highlighted.
@ , 42 is always the answer to the universe. THanks for this great video otherwise.
I'm glad to know the answer at was 42. It verifies that Hitchhiker's Guide to the Galaxy was a quantum computing primer!
For a list of N elements, it takes (N+1)/2 attempts on average, not N/2.
as stated at ? If we have N numbers from 0 to N-1 and one of them is the key, the expected value of the number of required guesses is then essentially the same as the average position of the key in the sequence of N numbers, which is (1+2+3+....+N)/N = N(N+1)/(2N) = (N+1)/2. Did I miss something? Thanks again.
Because of this very setup, one can ”improve” almost any algorithm that can be checked in linear time by simply checking all the possible inputs. Bruteforcing a password for example is an O(n) operation.
going with the video, as far as I know this depends wildly on the setup you can getwith lowest being around O(1) when you have N qbit device and you can chug entire superspoition through that function and if it can bring one probability to a 100 and rest to 0 it would only need one cycle to preform whole operation but if that probability is just high like 50% of being right and 50% of beign wrong, maybe dependable on N etc. this will elongateand at the other side if the functon isn't very "quantable" or you have very small qbit register or whatever it can go as high as O(n)
omg this is soooooo satisfying to watch and understand-ish
About the misconceptions on the speed of quantum computers () :
It’s so weird to me that not only people guess this answer, but that it’s the most common guess.
well its probably also that when one answer is O(1) it sounds like a trick question so „it has to be that“ in the minds of people
quantum computers can't have exponential speedup, because they are turing complete and can be represented by a turing machine (albeit a ridiculously fast and large one). And if a turing machine can achieve exponential speedup, that would basically mean NP=P which is unproven and highly unlikely to be true.
On the topic of why people might guess O(log(n)) (at ): I think you're thinking too much with your math brain, not your CS brain. O(log(n)) is divide-and-conquer style solutions, where you can divide your "problem-space" into smaller and smaller chunks. For this problem, if the quantum chip could say yes or no on if the True value was contained in a set, you could take half of the remaining numbers for each step resulting in O(log(n)). Nearly all sublineair solutions are basically some version of this.
This actually is no longer correct! As of November 2024 a new variation on Grover’s Algorithm has been created known as the partial oracle Grover’s algorithm that *does* give an exponential speed up, with the caveat of only working sometimes (and other times slowing back down to a polynomial speed up) But for the question of “best possible time complexity” O(log(n)) is actually correct
I was able to guess the right answer because I knew square root can be found in probabiloties from your video with min of 2 dice rolls)
The factors of the big number are just first few digits of pi and e
i loved when you said that Shor‘s is the most famous example, while it’s actually the *only* relevant problem we know that is exponentially sped up
I got it right!
, well ceil(pi/4) is just a fancy name for 1 😛😛😛, didn't you mean something like ceil(pi*sqrt(n)/4)?
- The state vector
At , it’s interesting that this kind of broke my internal ordering/deviated from what I would have been inclined to do.
Love how "01000011" is actually 67 and 'C'. Such attention to detail!
"[...] teaching computer science without discussing hardware."Fun fact: In German, the term for computer science is "Informatik", which is like mathematics but for information. This word tells you that you can do CS without a machine, it is just about information processing. We just so happen to have machines that are scaringly good at processing information.
I planned to watch missed Asianometry episodes, but then, bam! This came in! I'm now at and already i love this video :D
"if you kept reading out from memory over and over, you would just keep seeing that same value" I'm afraid that might be incorrect, or at least somewhat misleading. In a quantum system, if you repeatedly measure a register that's in superposition (re-initialized each time to the same state), you'll observe outcomes according to the probability distribution defined by the amplitudes — not always the same value. Perhaps what you meant is: if the system has already been measured and thus collapsed into a definite state, then repeated readings would indeed return the same value — but that's a different scenario :)
“think of it as some super high dimensional space” yeah man i got what you are trying to say, continue
^k notion of dimensions at ) if that's ever a future idea of a video (especially in ER = EPR for describing how the Einstein Rosen bridge gets "longer" as the entangled black holes evaporate).
I love how you throw out in the vector demonstration around “instead k^2 dimensions instead of 3 dimensions” yeah super easy to comprehend, thanks
if you square any real number (positive or negative) you'll always get a positive number
Take ''Alot of people don't know what the state vector represents'' re why we square the magnitude of each component of the vector.- The sum of all possible state vectors equals zero, and a plot of this results in a unit n-sphere. The sum of square equals the square of the radius of the sphere (in this case 1²=1). But how do I know it's a unit nsphere? Cause the state vector consists of probability components. And the cumulative probability of any Universal set must equal 1.
just guessing but is state vector, wave function, because we square that to get the probability, right?
- Qubits
- "After all, something is going to happen"
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.
, it would have been extremely helpful for my quantum computing course. Howeevr, I need to correct you in . It's not just a unit circle, its something called a Bloch Sphere, which in itself is what we call a CP^1 or a complex projective space of dimension 1. Its because of this that we take |x|^2 instead of simply x^2, and that's because the coefficient of |0> and |1> can also be complex, with the restriction that |x|^2+|y|^2=1
“Added *bit* of *complex*ity” 😂
As someone who took introductory quantum mechanics course the first aha moment is at showing what a qubit REALLY is
TODO continue from
Nice Schrödinger's Cat reference at
- The vibe of quantum algorithms
I found this bit where the circuit is drawn just gorgeous
-bit CLA, seeing one pop up at gave me a sensible chuckle
I bet that circuit does something interesting. Waiting to hear from people that know.
Example: a coin (deterministic) + Quantum vector = would be to have a 50/50 probability it would land either "heads" or "tails?"
@ Minor pedagogical point - applying a Hadamard gate twice would actually take a |0> state to a (negative) |1> and not back to |0>. I find it useful to think of the Hadamard transformation as half of a bit flip. Leading directly to the intuition that two Hadamards simply flips the bit.
I have a suggestion for ur visuals as ur visuals are the best of the best but to touch the elite line u can put the anime style in this, particularly on
in this
- Grover’s Algorithm
Question here: At , why do you flip the sign of only the secret key? if it is supposed to be unknown???
but how do i know beforehand what is the secret key value im looking for? How would this work in practice if say i try to force a password?
perhaps it’s on my brain a whole lot lately, but every time you talk about using this algorithm as a search, my brain adds to the list of applications “finding the most probable next word in a sequence of words”
Nice video as always, but the logic gates circuit for the function at is just bad. You only need 3 2-input and gates & 2 not gates to verify a 0101 (5). Boolean algebra.
- Why is that: "Grover knew that given any ensemble of logic gates like this, you can translate it into a system of quantum gates, so that if in the classical case the function takes in some binary input and returns a one, for true, then in the quantum case, the effect of all of these gates is to flip the sign of that state; the state associated with the same bitstring."
But at , we have to translate the function to a quantum equivalent, that instead of verifying if the answer is correct, flips the sign of the correct coordinate. The "you can translate it" is not about a theoretical possibility here, you really have to (very carefully) translate the classical verification algorithm into the quantum "secret axis flipping" algorithm.
Great video as always! The only part that’s still unclear to me is how the system of quantum gates at is able to invert the amplitude of the key item. More specifically, how is it possible for this to happen in so few steps that the overall complexity remains proportional to √N? This is something many textbook explanations don’t really clarify, and I was really hoping for a more precise understanding of this part of Grover’s Algorithm from the video.
it reminds me of Cook-Levin theorem
I feel like the real magic is happening with the quantum gates (), and I really don't understand it. So to take all the input values then run them through the quantum gate, with the goal of reversing the logical value of the key, would take N time, right? And why couldn't the process just end once a value has been flipped? Everything else just seems like a cool algorithm to find a needle in a haystack, but what I want to know is how they take a haystack and turn the key straw into a needle in seemingly constant time.
I think tries to answer my question, but the operation does not feel "useless" it feels like: if we can flip the sign of the key component, then we are already done because we already know the key direction.
mentions that the quantum gate "simply" flips the key value. Wouldn't it have to process a N dimensional vector every time ? Isn't the difference between the quantum gates doing something very different here(parallelism?) that enables much of the speed gain?
I think you may misunderstand me (or I'm just not understanding). We only know the key direction because a value was flipped (turned negative). In order for the state vector to be originally flipped, the value corresponding to the solution for the given problem, the states needed to be passed through the quantum gate (). Once the specified state vector was given a negative value, then the probability shifting occurs. I don't understand how first process occurs, in what seems to be constant time.
why does he use the term "state vector" at then? Does me mean to say that a specific component of that state vector is flipped?
Something I don't really understand, if you need flipping the sign of the value at the position corresponding to the solution of the problem, then shouldn't that require that you know the solution already? I've probably missed something that tells about that, but just quickly asking it here.
Always love your videos. One thing a layperson like me might hold onto is, how does the Algorithm "know" which one is the secret key? And therefore even start to run that process show in
Another great video, I just didn't get one thing - you say quantum computer can put the key value on one axis and "average" all the other values into the other axis - but isn't the whole thing about not knowing what is the key value in the first place? If we don't know where to go, does it mean we just try every direction? And how do we know we went into the correct answer direction and not some random one?
How do we find equibalance of the non-key states ?
This reminded me of your lecture about AI embedding spaces, how with the growth of number of dimensions, you are guaranteed to find more and more perpendicular vectors.
Please explain this, i am ultra confused - : if we don't know key value how can we perform flipping it's sign or any other reflection operation regarding it's position.
*focuses in learning
Great explanation! Admittedly, I’m still a bit confused by how you “flip about the x-axis” (or flip the sign of the key value) when the x-axis seems to be defined by “not the key.” It seems the key needs to be known to flip the sign associated with the key value (flip the sign for the component associated with the key value?
when flipping the state vector around the "equal balance direction", how do you avoid also transforming the key vector?
- yes, indeed... "In general, if you can clearly describe and access one of these state vectors, it's also perfectly possible to reflect around it."
b does seem to imply this at , but I'm not sure this is what he meant.
if we can access the vector then it's possible to reflect around it but how we have the access to vector aligning the x axis
I doubt that's it, but just in case you're talking about applying a fast-exponentiation-like approach for the part by rotating the vector by 2theta, 4theta, 8theta and so on and so forth (choosing a recently obtained vector as an axis instead of |b> each time). That approach doesn't work because you cannot duplicate quantum states (no cloning theorem). Basically, if you want to use a quantum state twice you have to build two copies from scratch and that defeats the point.
This was extremely helpful to me, confirming the vague notion I had about what quantum computing is about while also providing intuition about what a quantum algorithm is.However, I am still confused at , where you "first flip around the x direction and then flip around this off-diagonal direction" these seem to be unlike each other. The x direction stands for the orthogonal to the (unique solution) y direction, so it is in fact the hyperplane of all directions that are not y. But the other direction is given by just your single initial-state vector. so flipping around it is not well defined, in any case not as a geometric reflection. So it looks like you are trying to compose a reflection with something that is not a reflection in order to obtain a rotation, and that does not seem to work (except in dimension 2).
After the first reflections, why can’t you then reflect around the new higher vector you created, to get to the top faster?
so its just a computer
This video is great. you could use classical computers to calculate the root of N but it is a bit expensive.
I started to understand at around
Until you finally mentioned at ish that... you can just check it, since the premise was that the answer is quickly verifiable.
- Support pitch
- Complex values
complex numbers elegant application
- Why square root?
The fascinating thing about the section is that I took the square visualisation of the beginning and basically immediately understood why it is squared thanks to Pythagoras. Because even if we consider parallelism, picturing it with a square or cube or whatever, leads us to consider "going along" all the edges at the same time. Which, in the simplest case of the square, means that we, well, have to put all of the possible outcomes into a square. Which we, of course, can't do without taking the square root.
ofc its pythagoras its always pythagoras
Hey I recognize this!!That's the Cover Art for Richard Hamming's The Art of doing Science and Engineering!
Wow, that created an optical illusion that glitched my mind HARD
"Panoply of additional directions" Beautifully put
why is the shortcut squareroot sized when the vector doesnt move the whole way (just an approximation of pi over 4)? Wouldnt that mean that the shortcut the vector takes is ALMOST squareroot sized? (Kinda like the almost pi endzone in your last video)
- Connection to block collisions
finally, *the* one Brown
- Additional resources
flashbang alert
Q 1 – Early stop at sixty degrees• Chance of measuring the correct item: 75%.• Grover iterations used: roughly 0.52 times the square root of the database size N, which is about 2/3 of the work in Grover's original algorithm.• Why: each Grover step rotates the state by a tiny fixed angle; stopping when the total turn reaches 60 degrees means you have not yet maximised the success amplitude, but you have saved time.
interesting so the function we're optimizing here is essentially
