Quantum Information Science II, Part 3 - Advanced quantum algorithms and information theory

• Quantum algorithms - lecture overview
• Models of quantum algorithms
• Pros and cons of different models of quantum algorithms
• Overview of known quantum algorithms
• The Abelian quantum Fourier transform
• Abelian groups: isomorphism to products of cyclic groups
• Abelian groups: decomposition into group of characters
• The QFT over an Abelian group - definition
• Why Fourier transform?
• A quick application of Fourier transform: quantum phase estimation
• Using the QFT: quantum algorithms for groups - lecture overview
• The QFT over the cyclic group of N elements
• Realizing the QFT over Z_N using quantum phase estimation I
• Reversible classical computation of x * y / N
• Realizing the QFT over Z_N using quantum phase estimation II
• QFT caveat - the requirement for controlled-U to some power
• Efficient algorithm for Fourier transform over any decomposable Abelian group
• The hidden subgroup problem - definition
• Lower bound on the complexity of the hidden subgroup problem
• Simon's quantum algorithm - briefly
• Quantum algorithms for the hidden subgroup problem - lecture overview
• The Abelian hidden subgroup problem - statement and claim
• The Abelian hidden subgroup problem - proof of algorithm complexity
• The discrete logarithm problem - relationship to HSP
• The discrete logarithm problem - statement and reduction to HSP