11-860 — Advanced Topics: Quantum Computing Lab — Spring Semester 2020

February 10 & 12 / Week 4

Amplitude Amplification and Grovers

Before Class

Read Chapters 6 & 10 in the Octopus Book

Summary

First we will learn about Amplitude Amplification - One of the first of the quantum primitives. While not amazingly useful by themselves, they help to make the building blochs of more impressive algorithms.

We will then dive into quantum search and Grover’s algorithm. Grover’s algorithm is provably better than any classical implementation, showing a quadratic speedup.

Notes

unit index