Grover's Algorithm | Understanding Quantum Information & Computation - Lesson 08

This lesson is about Grover’s algorithm, which is a quantum algorithm for so-called unstructured search problems that offers a quadratic improvement over classical algorithms — meaning that Grover’s algorithm requires a number of operations on the order of the square-root of the number of operations required to solve unstructured search classically.

0:00 — Introduction
1:28 — Overview
3:11 — Unstructured search
6:43 — Algorithms for search
10:10 — Phase query gates
12:50 — Algorithm description
16:05 — Solutions and non-solutions
18:22 — Analysis: basic idea
19:20 — Action of the Grover operation
24:16 — Rotation by an angle
27:57 — Geometric picture
31:54 — Setting the target
37:13 — Unique search
42:49 — Multiple solutions
44:43 — Number of queries
45:54 — Unknown number of solutions
51:13 — Concluding remarks

#ibmquantum #learnquantum #qiskit

[genmen]

Well done! Probably the best presentation of the Grover algorithm I have encountered thus far.

[giorgiguliashvili]

That's great explanation. I also appreciate him taking time to discuss usability and potential concerns. As a software engineer, I have some intuition about how things can be used, and when I don't get usage ideas or have some concerns, I'm never sure of if my concerns are real, or if I just don't understand the algorithm well enough.

[hamzak.]

My guy looks a little less sleepy in this one. Truely a legend!

[Jackalpai]

This video is by far easier to understand than the CMU recorded lecture. Thank you!

[昱衡]

I really appreciate your lessons, they helped a lot.

[pawisaw]

The video was truly helpful. Thank you for your work! Really!

[KartikreddyKatam]

Hi, I am trying to complete the Exercise at 12:02, but every iteration of math that I try after putting a control qubit in superposition to perform the Zf gate as the Uf gate inside it, I can't isolate the f(x) function in the phase down to XOR the minus state work qubit. I would really appreciate someone explaining how to accomplish this or pointing me in the right direction. Thank you!

[izikarasu]

Excellent very clear explanation, thanks a lot! In the case when s is say 4, once we find the 1st solution, how do we find the other 3 ?

[John]

At 23:14, about G|A1>=.... "- 2 sqrt(|A_0|/N)" at the 4th row should be "- 2 sqrt(|A_1|/N)" ?

[zpf-eu]

hello. this algorithm and how you present it is so interesting. I want to make sure about meaning of iteration here. It means that we reapply the output to the G operator. but with rerunning the algorithm (from the start) we expect to get the same result. I mean suppose we have 2 qubits (i.e. N=4) and we have just circuit of G operator so with every rerun of the algorithm, it shall give us the same result but if we iterate it (rentering the output to another G operator) the output differs. am I right? Thank you so much!

[sheidalv]

Fantastic content! By the way, any plans to cover Quantum Machine Learning (QMM) in future videos? 🚀Feeling a bit down that the course is over. Hoping for another exciting course soon! 🙌

[howtovariable]

Hey, I had a doubt
How does Grover's algorithm tell us no solution as defined in the formal definition of the problem.