Lectures:    Tue-Thu    1:30—2:50  pm,    Room:    QNC 1201

Instructor:    Ashwin Nayak

Office hours:    Tue  3:00—5:00 pm,    and by appointment

Announcements

Mar. 8: There will be no lectures on Mar. 21 or 23. Make-up lectures will be held on Wed., Mar. 15 and 29, both from 3:00—4:20  pm (Room QNC 4104).

Mar. 10: The project presentations will be on Wednesday, April 12, 10:30 am—2 pm, in QNC 1201.

Outline

Through this course, we will study quantum algorithms in greater depth. Our emphasis will be on general techniques for quantum algorithm design and the underlying mathematical tools. We will also investigate what makes certain problems hard, even for quantum computers. Tentative list of topics:

1. •Fourier sampling
   

2. •Quantum walk
   

3. •Span programs and learning graphs
   

4. •Adversary bound
   

5. •Quantum Merlin Arthur games
   

Prerequisites for the course include an introductory course in quantum information processing. Familiarity with theoretical computer science will be helpful, but may be substituted by sufficient enthusiasm for the subject. Evaluation will be based on three assignments and a project. The assignments are intended to supplement the lectures and help the students get a more complete appreciation of the topics covered. The project consists of reading one or more recent articles related to the course, making a presentation to the class, and writing a report.

Lectures

1. •Discrete quantum walk: Grover algorithm, and its view as a quantum analogue of a random walk search algorithm; spectral analysis of a product of two reflections (Jordan Lemma); Markov chain search; classical hitting time; properties of reversible ergodic Markov chains; discrete time quantum analogue of Markov chains, and their spectral properties; search algorithm based on quantum walk; optimal algorithm for Element Distinctness.
   

2. •Span programs and learning graphs: quantum query algorithms; span programs; OR function and simple properties; recursive search algorithm for AND-OR function; span programs for composition of functions, AND-OR function and the balanced NAND tree; OR of arbitrary functions, span programs for read once formulae over {NOT, OR}; query algorithm from a span program; learning graphs and their complexity; learning graph for Element Distinctness; efficient algorithm from a learning graph.
   

3. •Adversary bound: significance of query lower bounds; the general adversary bound; application to OR and AND-OR functions; proof of the connection to query complexity.
   

4. •Fourier sampling: basics of group representation theory, examples; quantum Fourier transform over a group, examples; Hidden Subgroup Problem, Simon 2-to-1 collision problem, Period Finding, Discrete Logarithms, Graph Automorphism; Fourier sampling algorithm, analysis for abelian groups, examples; complexity of QFT and HSP for abelian groups; HSP for normal subgroups, remarks on weak vs. strong Fourier sampling.
   

5. •Quantum Merlin Arthur games: Group Non-Membership, its complexity; the complexity class QMA; QMA protocol for GNM; Error-reduction for QMA; Local Hamiltonian Problem (LHP), QMA protocol for LHP; QMA-hardness of LHP with O(log n) locality, its significance.
   

References    [ pdf ]

Resources

1. •Introduction to Quantum Information Processing, course taught by Richard Cleve    [ link ]
   

2. •Quantum Algorithms, course taught by Andrew Childs    [ link ]
   

Assignments

Collaboration between classmates on the assignments is allowed, and encouraged if you are stuck. You are also welcome to approach me for help. However, you are likely to learn more if you think about the assigned problems independently before you initiate a collaboration or seek help. You may consult other sources such as the internet, or research articles, only as a last resort. You are expected to write solutions on your own, and name collaborators and any other sources consulted.

1. •Out Jan. 23, due Mon., Feb. 6:    [ pdf ]
   

2. •Out Feb. 13, due Mon., Feb. 27:    [ pdf ]
   

3. •Out Mar. 13, due Mon., Mar. 27:    [ pdf ]
   

Projects

The project consists of reading one or more recent articles related to the course, making a presentation to the class, and writing a report. The presentations will be on Wednesday, April 12. The report is due on Thursday, April 13, in PDF format, by email to the instructor.

Suggested papers for projects:    [ pdf ]

Please prepare the presentation in the style of a 25-minute conference talk. Place the result presented in context. In particular, define the problem, describe the motivation behind it, the prior work, state the main result and explain its significance. Finally, present what in your opinion is the main technical or conceptual contribution that enables the result.

In the report (5-10 pages), cover the same topics, but in the style of a tutorial or lecture. Distill the simplest non-trivial case of the result, and present it in as complete a manner as you can. Illustrate your proofs and explanations with examples where appropriate.

Last updated March 10, 2017