Instructors: David Gosset (dgosset@uwaterloo.ca)
                     Junqiao Lin (j224lin@uwaterloo.ca)

Discussion board: There is a slack which can be used for general Q&A about the course and discussion with classmates and instructors. Slack invite link

Office Hours: To be determined.

Announcements: Classes are held Tuesdays and Thursdays 1:00-2:20pm Waterloo time. The zoom link is 
https://us02web.zoom.us/j/81228948813
(password:"quantum")

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

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

Evaluation
The final course grade will be determined by three assignments (20% each) and a final project (40%). You are permitted to work in groups of two for the assignments and final project. However, you must choose a different partner for each assessment.  The written up solutions to the assignments should include an acknowledgment of any sources (research papers, textbooks, etc) consulted.

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

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

Tue May 18 video : 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 20 video 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 25 video The abelian hidden subgroup problem continued [AMC CH 6] [NC CH5]

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

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

Thu June 3 video 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 8  video Nonabelian HSP continued. Continuous time quantum walk [AMC CH 16]

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

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

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

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

Thu June 24 video Polynomial method continued (see above references)

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

Tue July 6 video Hamiltonian simulation. Linear systems algorithm. [AMC CH 25] [Lloyd 1996][Harrow Hassidim Lloyd 2008][Low Chuang 2016]

Thu July 8  video Lecturer: Junqiao Lin. Classical Cook Levin theorem. BQP and QMA.  [KSV]

Tue July 13  video Lecturer: Junqiao Lin. QMA completeness of 5-local Hamiltonian problem. [KSV CH 14] (note QMA is called "BQNP" in [KSV])

Fri July 16 video 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 20 video 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 14][Bremner Montanaro Shepherd 15]

Thu July 22 video Continue discussion on hardness of approximately sampling from the output probability distribution of IQP circuits. Begin discussion of Stockmeyer's approximate counting algorithm. [Stockmeyer 83][Goldberg Guo 14][Bremner Montanaro Shepherd 15]

Tue July 27 video Stockmeyer's approximate counting algorithm.  [Stockmeyer 83][Sipser 83]

Course project

The course project will be completed in groups of at most 2, and 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 12, 2021. The presentations will take place during the last two classes on August 3rd and 5th. 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...