Module 07 of 10

Quantum Algorithms

Lessons

About This Module

You can now build and run circuits, so the next question is what they are good for. This module covers the landmark quantum algorithms: the cases where a quantum computer provably needs fewer steps than any classical method.

It starts with quantum query algorithms (Deutsch, Deutsch-Jozsa, Bernstein-Vazirani and Simon), which show clearly where the quantum advantage comes from. Next comes phase estimation and Shor's algorithm, built on the quantum Fourier transform, which factors integers efficiently. It then covers Grover's algorithm for unstructured search and its quadratic speedup, and closes with a visual walkthrough of the intuition behind it.

Watch the lessons in order, then continue on to Variational & Hybrid Algorithms.

Lessons

4 videos
01

Quantum Query Algorithms

John Watrous introduces the query model and walks through Deutsch's algorithm, the Deutsch-Jozsa algorithm, Bernstein-Vazirani, and Simon's algorithm, including phase kickback and why these problems favor quantum computers.

02

Phase Estimation and Factoring

How phase estimation approximates the eigenvalue of a unitary using the quantum Fourier transform, and how that leads to order-finding and Shor's algorithm for integer factorization.

03

Grover's Algorithm

The unstructured search problem and how Grover's algorithm solves it with a quadratic speedup: phase query gates, the geometric picture, and choosing the number of iterations.

04

But What Is Quantum Computing? (Grover's Algorithm)

3Blue1Brown builds up qubits and state vectors as math, then shows step by step how Grover's search finds the answer in about the square root of the usual number of steps.