Semester:
Offered:
Instructor: David Gosset (dgosset@uwaterloo.ca)
Office Hours: Tue 10-12 QNC 3318
Announcements:
The lecture on May 14 will take place from 10:30-11:50 in QNC 1201.
There will be no lecture on May 16.
The lectures on May 28th and May 30th will take place in WIN 1501.
There will be no lectures on June 4 or June 6.
Assignment 1 (see below) is due on Thursday, June 13th by email to the instructor.
Outline
We will discuss commonly used techniques for quantum algorithm design and some of the significant quantum algorithms developed to date. We will also cover aspects of quantum computing theory which are closely related to quantum algorithms. A tentative list of topics is as follows:
- Basic quantum subroutines
- Quantum algorithms for Hidden Subgroup Problems
- Quantum walk algorithms
- Quantum query complexity
- Quantum algorithms for Hamiltonian dynamics
- Quantum algorithm for linear systems of equations
- Limits of classical simulation of quantum computers
Resources
QIC 710: Introduction to Quantum Information Processing, course taught by J. Yard. Link
[AMC] Andrew Childs' lecture notes on quantum algorithms. Link
[NC] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information, Cambridge University Press (2000).
[KSV] A.Y Kitaev, A.H. Shen, M.N. Vyalyi. Classical and Quantum Computation, American Mathematical Society (2002).
[KLM] P. Kaye, R. Laflamme, and M.Mosca. An Introduction to Quantum Computing. Oxford University Press (2007).
Evaluation
The final course grade will be determined by three assignments (20% each) and a final project (40%). The assignments are to be completed in groups of at most 4 students. The written up solutions for each group should include an acknowledgment of any sources (research papers, textbooks, etc) consulted.
Lectures:
(References below refer to either the resources above, or original papers in which case external links are given)
Tue May 7: Review of the quantum circuit model [AMC Ch 1+2][NC CH 4]. Basic quantum subroutines: amplitude amplification [BHMT 2000]
Thu May 9: Basic quantum subroutines continued: quantum Fourier transform [NC CH 5], phase estimation [NC CH 5], amplitude estimation [BHMT 2000]
Tue May 14: The QFT over an abelian group. [AMC Ch 4][Kitaev 95, Section 5]
Tue May 21: The abelian hidden subgroup problem [AMC CH 6] [NC CH5]
Thu May 23: Quantum algorithms for order finding and discrete log [AMC CH 9][NC CH 5]
Tue May 28: Nonabelian HSP and query complexity of HSP [AMC CH 10]
Thu May 30: Continuous-time quantum walk [AMC CH 16]
Tue June 11: Discrete-time QW; quantizing a Markov chain [AMC CH 17] [Szegedy 2004]
Thu Jun 13: Quantum walk search. Ambainis' algorithm for element distintness. [AMC CH 17][Ambainis 2003]
Tue Jun 18: Query complexity. The polynomial method. [AMC CH 20][KLM CH 9.5][Beals et al. 1998]
Thu Jun 20: Polynomial method continued. (see above references)
Tue June 25: Adversary method. [AMC CH 22][KLM CH 9][Ambainis 2000]
Thu June 27: Hamiltonian simulation. Adiabatic quantum computing.[AMC CH 25, 27] [Lloyd 96] [Notes]
Tue July 2: Feynman-Kitaev circuit-to-Hamiltonian mapping. Universality of adiabatic QC. [KSV CH 14].[Notes]
Thu July 4: Quantum linear systems algorithm. [Harrow, Hassidim, Lloyd 08] [Childs, Kothari, Somma 15]
Hardness of exact sampling from the output probability distribution of quantum circuits. Complexity of postselected quantum and classical computation. [Terhal Divincenzo 02] [Fenner Green Homer Zhang 03] [Bremner Jozsa Shepherd '10] [Aaronson 04]
Tue July 9: Begin discussion on hardness of approximately sampling from the output probability distribution of IQP circuits. Aside: hardness of approximating output probabilities of quantum and classical circuits to a given relative error. Statement of Stockmeyer's approximate counting algorithm. [Stockmeyer '83][Goldberg Guo 2014] [Bremner Montanaro Shepherd 2015]
Thu July 11: Proof of Stockmeyer's approximate counting algorithm.[Sipser '83] [Stockmeyer '83]
Tue July 16: Proof of hardness of approximately sampling output probability of IQP circuits, assuming average case hardness of IQP output probability estimation (and non-collapse of PH). [Bremner Montanaro Shepherd 2015]
Thu July 18: Classical hardness of approximately sampling from the output of constant-depth quantum circuits.
Tue July 23: Advantage of constant-depth quantum circuits over constant-depth classical circuits [Bravyi Gosset Koenig '17]
Thu July 25: Project presentations.
Tue July 30: Project presentations.
Course project
The course project will be completed in groups of at most 3, and will consist of a written report of at most 8 pages, along with a 20 minute presentation. The written report should be emailed to the instructor no later than July 29, 2019. The presentations will take place during the last two classes on July 25th and 30th. The purpose of the project is for you to learn some additional topic in quantum algorithms (broadly construed) beyond what has been covered during the course. For example, this could take the form of reading one or more research papers and explaining them in your presentation and report. Some possibilities for project topics are listed below, but of course you may also choose a topic which is not in this list:
Quantum algorithms for formula evaluation: https://arxiv.org/abs/0710.2630
Dihedral hidden subgroup algorithms: https://arxiv.org/abs/quant-ph/0302112
Boson sampling: https://arxiv.org/abs/1011.3245
Linear systems algorithm with exponentially improved dependence on precision: https://arxiv.org/abs/1511.02306
Quantum singular value transformation: https://arxiv.org/abs/1806.01838
Quadratic speedup for finding marked vertices by quantum walk: https://arxiv.org/abs/1903.07493
Quantum machine learning algorithms: many papers...