Phase Estimation & Factoring | Understanding Quantum Information & Computation: Lesson 07

This lesson discusses the phase estimation problem and a quantum algorithm to solve it. By applying this algorithm to a number-theoretic problem known as the order-finding problem, we obtain Shor’s algorithm, which is an efficient quantum algorithm for the integer factorization problem. Along the way, we’ll encounter the quantum Fourier transform and see how it can be efficiently implemented.
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
0:58 - Overview
2:40 - Spectral theorem
5:43 - Phase estimation problem
11:53 - Warm-up: using phase kickback
17:24 - Iterating the unitary operation
19:39 - Two control qubits
26:43 - Two-qubit phase estimation
32:25 - Quantum Fourier transform
35:44 - Circuits for the QFT
41:41 - Phase estimation procedure
48:29 - The order-finding problem
53:25 - Order-finding by phase-estimation
55:07 - Eigenvectors and eigenvalues
59:20 - A convenient eigenvector
1:02:04 - A random eigenvector
1:05:37 - Implementation
1:10:55 - Factoring through order-finding
1:14:48 - Conclusion
#ibmquantum #learnquantum #qiskit

[@LydellAaron]

This is a gem, combining so many connected topics.

[@yonidemulder]

This is by far the best video I've seen explaining the quantum part of Shor's algorithm. Thank you so much for sharing!

[@genmen]

Thank you! Much anticipated lesson

[@howtovariable6481]

Can u clarify how did we obtain phi-0 or 1 and so on , and determine that |1> is a supposition of all phi 0 to r-1

[@fgfgdfgfgf]

He is amazing

[@ethanrajkumar6203]

Excellent Video! I was just wondering for |\psi> can it be in the computational basis as well because it's an orthonormal basis?

[@asmaa.ali6]

Hello, at 25:10 , are the four bases found to be orthonormal by chance ? or they must be? or the algorithm is set as it for making this condition ? Thank you so much

[@que_93]

Could you please create a playlist, and provide a link for it?

[@qiskit]

ua-cam.com/play/PLOFEBzvs-VvqKKMXX4vbi4EB1uaErFMSO.html&si=DGM47YvuNDqRLyLd

[@suleymanemirylmaz7868]

While measuring the 0 and 1 states at 16:30 , I couldn't figure out how we found the cos^2 and sin^2 states. For example, for state 0 I found (1+2cos(2πx))/4

[@John.Watrous]

One way to do it without it getting too messy is to use cos(x) = (exp(ix)+exp(-ix))/2 and sin(x)=(exp(ix)-exp(-ix))/(2i), and then let the absolute values make your life easier. For example, abs((1 + exp(2 i x))/2)^2 = abs(exp(ix)(exp(ix) + exp(-ix))/2)^2 = abs((exp(ix) + exp(-ix))/2)^2 = cos(x)^2.

[@suleymanemirylmaz7868]

@@John.Watrous Thank you very much. I completely understand now.

[@nadavben-ami9020]

Is there expected time for the next lesson to be uploaded?
Thanks!

[@ebrahimraja2855]

I'd also like to know this. It seems units 3 and units 4 of the course are yet to be released?

[@asmaa.ali6]

Hello, at 1:00:40 , sorry for this trivial question but how (2^m/y + 1/2) gives an integer?

[@John.Watrous]

2^m/y + 1/2 might not be an integer but here we're taking the floor of this quantity. See en.wikipedia.org/wiki/Floor_and_ceiling_functions for how the floor is defined and denoted.

[@asmaa.ali6]

Hello, I am sorry but i can't figure out how we got P_y=4/\pi^2 at 45:51 . thank you so much .

[@ArthurParzygnat]

Hi @asmaa.ali6, after working this out myself, let me try to explain (sorry if this explanation is complicated---I did quite a bit of work to reach this and I'm not sure if this is the simplest solution). If we assume that the closest approximation to theta is y/2^m, then this means that the (conditional) probability of y given theta is smallest when theta = y/2^m + 1/2^(m+1) or theta = y/2^m - 1/2^(m+1). The meaning of this last expression is that the worst-case theta lies directly between the highest peaks (which happens exactly 1/2^(m+1) away from any of the highest peaks because that's exactly the halfway distance between these peaks). Although John Watrous did not write p_y as a conditional probability, we should really think of it as such and write it as p(y|theta) because it depends on theta (that's what is plotted). Now, since the worst-case theta is what I wrote above, this means p(y|theta) is greater than or equal to p(y| y/2^m + 1/2^(m+1)). I calculated this probability for various values of m. When m=3, I got 0.410533. When m=4, I got 0.406589. When m=5, I got 0.40561. As you notice, these numbers seem to be tending (monotonically) towards some value. One can therefore compute the limit of this probability as m tends to infinity. One can do this using the realization that when we compute such a limit, we are effectively calculating an integral, which can be evaluated exactly and gives the result 4/pi^2.

[@user-po5fg7eq7v]

I enjoyed the video, but I have a few comments. I don't like the fact that you interrupt the explanation of how order finding can be implemented, by fragments where you explain precision needed and complexity. I think it would be better to first go through the algorithm and then come back and analyze precision and complexity.

[@John.Watrous]

That's cool, to each their own. I'm a complexity theorist so these issues are front and center for me, and I just explain it the way I think about it.