Quantum Phase Estimation & Factoring | Lesson 07

This is part of the Understanding Quantum Information & Computation series. Watch the full playlist here: https://www.youtube.com/playlist?list=PLOFEBzvs-VvqKKMXX4vbi4EB1uaErFMSO

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: https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms

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