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

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.
Additional materials for this course, including written text, Qiskit implementations, and slides in pdf format, can be found on IBM Quantum Learning by following this link: learning.quantum.ibm.com/cour...
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.

[@anishnair937]

the goat is back

[@giorgiguliashvili2706]

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.

[@Jackalpai]

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

[@Ethan_here230]

Which lec are u talking about?

[@AAAE2013]

Thanks for your effort!

[@izikarasu5896]

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 ?

[@user-ns4wz3dl7z]

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! 🙌

[@karun3339]

when's the next unit coming?

[@user-er3sg5xm2w]

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!

[@John.Watrous]

Have you tried putting the control qubit into a |+> state?

[@user-er3sg5xm2w]

Yes, I tried the plus state and minus state, but was left with the value of f(x) still stuck in the phase. Should I just be rechecking my math?
@@John.Watrous

[@John.Watrous]

Not necessarily, thinking about the |+> and |-> states is just part of it, and you saying that f(x) is "stuck in the phase" sounds like you may be OK. My next leading question is, how might you get it out of the phase? Think about phase estimation for some inspiration.@@user-er3sg5xm2w

[@John40066]

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

[@John.Watrous]

Yes, that's a typo - the subscript 0 should be a 1. Everything else (including the final expression) is OK. Good catch!

[@rabbit719]

Are there unit three vidoes?

[@qiskit]

soon.

[@rabbit719]

@@qiskit thanks for all the series!!