Instructor: David Gosset (dgosset@uwaterloo.ca)
TA: Andrew Jena (ajjena@uwaterloo.ca)

Office Hours: To be determined.

Announcements: Classes are held Tuesdays and Thursdays 2:00-3:20pm in QNC 1201.

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
• Limits of classical simulation of quantum computers

Resources

QIC 710: Introduction to Quantum Information Processing, course taught by R. Cleve. 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).

[DW] Ronald de Wolf's lecture notes on Quantum computing Link

[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).

Lectures from last offering (S21) can be found here:S21 online course materials 

Evaluation
The final course grade will be determined by three assignments (20% each) and a final project (40%).  The written up solutions to the assignments should include an acknowledgment of any sources (research papers, textbooks, etc) consulted.

Tue May 9:  Review of the quantum circuit model [AMC Ch 1+2][NC CH 4]. Basic quantum subroutines: amplitude amplification [BHMT 2000]


Thu May 11: Basic quantum subroutines continued: amplitude amplification cont'd [BHMT 2000], quantum Fourier transform [NC CH 5], phase estimation [NC CH 5]

Tue May 16: Basic quantum subroutines continued: phase estimation [NC CH5], amplitude estimation [BHMT 2000]. The QFT over an abelian group. [AMC Ch 4][Kitaev 95, Section 5]

Thu May 18: The QFT over an abelian group. [AMC Ch 4][Kitaev 95, Section 5] The abelian hidden subgroup problem [AMC CH 6] [NC CH5]

Tue May 23: The abelian hidden subgroup problem continued [AMC CH 6] [NC CH5]

Thu May 25 Quantum algorithms for order finding and discrete log [AMC CH 9][NC CH 5]

Tue May 30 Quantum algorithms for order finding and discrete log. Classical hardness of Simon's problem. [AMC CH 9][NC CH 5][Simon 97]

Thu June 1  Nonabelian hidden subgroup problem. Query complexity of HSP. [AMC CH 10][Ettinger Hoyer Knill 04] Pretty good measurement [Barnum Knill 2000][Harrow Winter 2006][Montanaro 19]

Tue June 6  Nonabelian HSP continued. Continuous time quantum walk [AMC CH 16]

Thu June 8 Glued trees traversal problem. Discrete time quantum walk part 1 [AMC CH 16][AMC CH 17][Szegedy 04][MNRS]

Tue June 13 Detecting marked items by discrete time quantum walk [AMC CH 17][Szegedy 04][MNRS][AGJK 19]

Thu June 15 Quantum walk examples. Ambainis' algorithm for element distinctness. [AMC CH 18,19][Ambainis 03][Aaronson, Shi ]

Tue June 20 Query complexity. The polynomial method. [AMC CH 20][KLM CH 9.5][Beals et al 1998]

Thu June 22  Polynomial method continued (see above references)

Tue June 27 Adversary method. [AMC CH 22][KLM CH 9][Ambainis 2000]

Thu June 29 Hamiltonian simulation. Linear systems algorithm. [AMC CH 25] [Lloyd 1996][Harrow Hassidim Lloyd 2008][Low Chuang 2016]

Tue July 4  Guest lecture (Andrew Jena)

Thu July 6  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 11 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 14][Bremner Montanaro Shepherd 15]

Thu July 13 Stockmeyer's approximate counting algorithm.  [Stockmeyer 83][Sipser 83]

Tue July 18 Problem solving session (Assignment 3) 

Thu July 20, 21, 25, 26, 27 Project presentations

Course project

The course project will consist of a written report of at most 8 pages, along with a 15 minute presentation. The written report should be submitted no later than August 1, 2023. The presentations will take place during the last few classes in late July and early August. 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, https://arxiv.org/abs/2105.02859

Quadratic speedup for finding marked vertices by quantum walk: https://arxiv.org/abs/1903.07493

Classical shadows of quantum states: https://arxiv.org/abs/2002.08953, https://arxiv.org/abs/2103.07510

Oracle separation for sign-problem free adiabatic quantum computation: https://arxiv.org/abs/2005.03791

Classical simulation of random 2D constant-depth circuits: https://arxiv.org/abs/2001.00021

Quantum speedups for graph properties: https://arxiv.org/abs/2006.12760

Delegation of quantum computation: https://arxiv.org/pdf/1711.09585.pdf

Quantum machine learning algorithms: many papers...