This lecture will focus on two major (families of) quantum algorithms: period finding (a.k.a. Hidden Subgroup Problem HSP) and Grover’s search. Under period finding, we will study Simon’s algorithm, phase estimation, and the notable quantum factoring algorithm due to Shor/Kitaev. Examples of impact on cryptography (e.g., breaks of cryptosystems, superposition attacks and quantum rewinding) will be discussed too.
Suggested reading: Watrous qc notes 6, 8, 12; Childs note Chapter 5, 9, 18.
Copyright. All Rights Reserved.