Lesson 38 Quantum Computing, Deutsch's Problem
Вставка
- Опубліковано 10 лют 2025
- Intro to Quantum Computing. The first real quantum algorithm invented by David Deutsch is described. Basic one and two q-bit quantum gates are utilized to discover if a one bit function is constant or balanced in a single evaluation. Pre class slides by Steve Spicklemire
As many others have said, this is by FAR the best and clearest explanation of Deutsch's problem - thank you!
Love how clear and understandable this explanation is, thank you
This is the best way of explaining a topic about Quantum Computing I've seen so far.
The best explanation..!!
I'm watching the video in 2019 Dec..!!
The best video for understanding the Deutsch's Problem. Thank you!!
I went through a couple of video explaining Deutsch's algorithm. This video is the best.
Thank you!
Hi Steve, I reached here while searching for a good lecture on Deutsch's problem. Your lecture is lucid and is "The Best".
Sudhakaran Karunakaran thank you! You’re very kind.
Excellent and comprehensive presentation !
Great video! Really helpful explanation, Now that I understand what is happening in this algorithm I can understand how it is written with fancier notation in my textbook.
Wow! Thank you :-) I'm an Old fart... 69 yo. Many years ago, I was a 4th GL Programmer/analyst. I don't know squat about Quantum (anything)... lol However, recently, I have been delving into the realm of Quantum Computing. It took me some time to wrap my head around the idea, but this video is where the lights came on... I really appreciate it :-) Thanks
Thank you for the very clear explanation! hope to see more videos about Grover algorithm, Shor algorithm, quantum fourier transform, quantum walk. Could you share a pointer if you have recorded these, I could not find them.
Thanks for an amazing explanation.. Can't imagine how quantum computing is going to be used in the future.
Thank you so much. This made things a lot easier. Great explanation.
This is really a wonderful explanation. Thank you very much.
Sir your explanation helps me lot 🙂
Best explaination ever!!!
VERY GOOD EXPLANATION...Regards - Reddy
BEST EXPLANATION !
Glad it was helpful!
thank you very much it was a very clear explanation of the whole concept
Thank you for the great explanation! Does it mean the initial qubits for this circuit have to be 1s?
Yes, that's exactly right.
@@sspickle Thanks 👍
the best explanation
Hi Steve, first of all that's for the videos, just get confused while reading JP's lecturenotes and you clear it up, great job! But I am wondering, on this slide 14:52 shouldn't the lower output of the F-CNOT gate be |y "XOR" f(x)>, since the former's value determine whether the latter get flipped or not.
You have the right idea. But XOR is symmetric. It doesn't matter what order it's in. Try it on all possible inputs to see.
great lecture, but at 21:27 isn't an sqrt(2) missing from the denominator?
Yes, I guess I didn't carry it through. Unfortunately I can't really change the video easily. It doesn't really change the outcome, but it's a good point.
@@sspickle it's a splendid video, you are a great teacher, keep on the good work, greetings from Hungary :)
This is so clear! Thank you! Can you do videos on Deutsch-Jozsa, Shor's and Grover's algorithms?
I'll add those to my list. ;-)
finally an explanation how quantum computing works! Thank you. The way I get it - the quantum computer indeed does all the calculations the normal computer would do - or even more (it evaluates the function 4 times instead of 2), BUT it does it via evaluating "super-positioned" variables. In that way it does ALL 4 calacuations of the function in "one run", as you said it. Now the thing is that in case of 2 qbits that's not a big deal (4 evaluations at once), but on 10 qubits we get 2^10 evaluations at once and on 100 qubits we get 2^100 evaulations at once. I feel I finally get it :) Please correct me if I'm worng or I miss something critical. Thank you
Yes, indeed, this is the basic idea.
Your voice reminds me of the voice of Heath Ledger's Joker in some parts.
Excellent video also!
Excellent. One of my favorite topics. ;-)
Thank you still watching it in 2020 oct
Great!
Hey Great video!!
Just had a doubt hope you can clear it ASAP as i have an exam xD.
at 18:31 when the term is |0 1> and we have applied the f Cnot gate then why is the output |0 f~(0> . In CNot gate we flip the 2nd bit if the control bit is 0. So it should'nt it be |0 f~(1)>
The inversion happens when the control bit is 1, not zero. If the control bit is zero, the output is simply the output of the function.
One of the best explanation!! Can you explain this for Deutsch jozsa algorithm
I suppose I should, but no time right now. Sorry! It's a pretty straightforward generalization.
Question1: The function f is assumed to be unknown to the user as a whole but they can query it (evaluate f(x) for any given x), right?
Question2: The problem assumes that there already exists a quantum circuit that implements f, since it goes into the f-CNOT gate, right?
Correct on both counts. Note that the problem is highly contrived and of virtually zero direct practical value. The main point is that this was a clear, and simple, demonstration that a quantum computer could, in principle, compute something using fewer evaluations than a classical computer could.
@@sspickle Excellent. Thanks a lot for taking the time to respond and for the helpful comment.
Also would this input |0> ⊗|0> to the f-CNOT gate be the same as |00> ?
Sure, these are just different notations for the same state.
If we use the result of f(1)-f(0) to do this, we can also get the conclusion by one operation. Is this right?
The trouble is that classically f(0) is one operation, and f(1) is another operation, so that's two operations, yes? Or maybe you mean something else?
Where do I learn the requisites for this? Logic circuits is clear, but I get blocked in all Deutsch's Problem explanations in what I don't know these notation/algebra (SQRT(2), spins, etc)
You can view earlier lessons in this course that deal with many of these concepts!
@@sspickle a bit disappointed with this answer...
@@ribamarsantarosa4465 hmm. Not sure how else to answer. The pre-req for this class is generally called “Modern Physics”. You could search for material from that class?
@@sspickle I guess I found the wikipedia page "quantum logic gate". I'm maybe also requiring too much from you, because I'm trying to learn as a CS knowing too little about Quantum physics. Nevertheless, I guess however, it'd possible to explain everything under a probabilistic and combinatorics point of view (instead of the physics), because that's what matters (for CS) at the end.... Tnx
@@ribamarsantarosa4465 Ah, very good. If you don't care about the underlying physics of a quantum computer, then this content may not be very helpful.
is he saying phase or face at the start? the captions say phase but I think it's suppose to be face?
"phase". The point is that you can multiply psi by exp(+i phi) without changing anything that's physically significant (anything that changes an actual physical outcome prediction, say).
Nice explanation! Thanks a lot! :)
Glad you liked it. ;-)
Great! Glad you found it useful. ;-)
It was very useful to me, Thank you.
Here's something that's not connecting for me. In your diagram of the FCNOT gate, it shows qubit X being projected along unchanged, whereas qubit Y becomes (Y XOR F(X)). But you assert that after the gate, qubit X will be different depending on whether F(X) is balanced or constant, and qubit Y will be the same regardless of F(X). Why is the dependency somehow reversed?
If you look at the slide 20:43 you can see that in each element of the superposition, |x> passes through unchanged, but the overall phase of each term in the superposition depends on f(x). When you apply Hadamard to the superposition, what comes out depends on the relative phase of all the terms and this brings in f(x). Make sense?
when you say f(0) = f(1)~ does this translate to f(0) does not equal f(1)?
Yes, the output of f(0) and f(1) are opposite. This is the "balanced" condition.
Nice video!
Can you clarify your use of the tilda's over the functions? I do not understand when/why you use them.
Sure, sorry. It's the opposite of f, so if f(0) is true, the "tilda" f(0) would be false.
Yes, I understood that. What I don't understand is your pattern for using them. My understanding of a CNOT gate is that it looks to the 1st bit-if the bit is a 1, if flips the 2nd bit, if not, it leaves it alone. However, your ~f is used on the second bit once when the first bit is 0 and once when the first bit is 1. I don't understand what criteria you look to when deciding to use a ~f.
OK, I see your confusion. Go back to 14:16. It's not a C-NOT it's modified to evaluate f(x) within the gate itself.
Yes I think my confusion is over what exactly the f(x) oracle is doing. I tried looking around for a matrix for of such a function to better understand but was unable to find one. I don't really understand what it's action is (whether on one qubit or two, since I have seen examples of both.)
The point is f(x) is unknown. It's one of four possible functions. If you select one of the four, then you can create a matrix. For example if f(x)=x, then the f-CNOT becomes just plain old CNOT and the output qbit is the XOR of x and y. On the other hand, If f(x)=1, then the output qbit becomes NOT(y) and so on. Does that help?
This type Algorithm has it an Name other then like Hadamar programing?
Thanks for the great explanation! However, it is still unclear to me why XORing f with 1 yields the inverse of f.
I would be very grateful if someone could clarify :)
If I understand your question, that's just the nature of the XOR operator. en.wikipedia.org/wiki/XOR_gate Maybe I don't understand your question?
Thanks a lot.
is there a playlist for this lecture?
Yes! bit.ly/QM1Slides and bit.ly/QM2Slides
Muchas gracias!
De nada. ;-)
I didn't understand much, but this kinda explained, that it's not that simple, as a lot of videos trying to depict it... )) I get the idea though.
Thank you!
Very long winded, but informative.
2020?