Lectures:    Tue-Thu    1:00—2:20  pm  (from Sep. 17),    Room:    QNC 1201

Instructor:    Ashwin Nayak

Office hours:    Thu  2:30—4:00 pm,    and by appointment

Announcements

Make-up lectures will be held on Fri, Nov. 22, Nov. 29, 11 am —12:20 pm, in QNC 1201.

Project deadlines: inform instructor of topic and papers by Friday, Nov. 22, first draft of pages due Friday Dec. 6, presentation on Tuesday, Dec. 10, final version of pages due Friday, Dec. 13.

Outline

In this course, we will get a taste of some of the exciting developments in quantum information and computation in the past few years. A couple of prominent themes among these are: applications of semi-definite optimization, and the use of ideas from quantum in classical computation. Most of the course will be devoted to these two themes. Tentative topics include:

1. •Semi-definite programming and one-shot information theory
   

2. •The adversary bound, span programs and quantum algorithms
   

3. •Parallel algorithms for semi-definite programs and quantum interactive proofs
   

4. •de Finetti-type theorems and polynomial optimization
   

5. •Quantum communication, extended linear programming formulations, information complexity
   

6. •Area law and algorithms for gapped one-dimensional Hamiltonians
   

If time permits, we will explore key developments not necessarily related to these themes.

Prerequisites

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. The lectures will provide the context and background necessary to understand the central components of the results. Students are expected to have enough maturity (mathematical or otherwise) to fill in details through further reading, the assignments, and a project.

Evaluation

Evaluation will be based on three (simple) 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 developing a report in the form of an appropriate collection of Wikipedia pages.

Lectures

1. •SDP basics, examples in QI:    Semi-definite program, dual program, weak and strong duality, Slater condition; state identification problem; conditional min-entropy, its significance, and operational meaning. References: these for SDP basics,  [König, Renner, Schaffner 09]
   

2. •Weak coin flipping: impossibility of classical protocols, Spekkens-Rudolph protocol, Mochon protocol, SDP formulation of cheating probabilities, bounding bias through weak duality. References: [Spekkens, Rudolph 02], [Mochon 05]
   

3. •Adversary bound and span programs: quantum query algorithms, proof of the adversary bound; examples: OR, AND-OR; the bound as an SDP, strong duality; span programs examples: OR, complementation, composition, AND-OR, NAND tree; quantum algorithm from span programs. References: [Høyer, Lee, Špalek 07], [Reichardt 10]
   

4. •Quantum interactive proofs: Quantum Circuit Distinguishability, QIP(3) protocol for it, QIP definition, SDP formulation of maximum acceptance probability, QIP in EXP, Alternative formulation for QIP(3) as a min-max problem, multiplicative weights update (MWU) method, Matrix MWU algorithm, algorithm for QIP(3). References: [ Jain, Ji, Upadhyay, Watrous 11], [ Wu 10]
   

5. •Locally decodable codes: definition, Hadamard code, characterization of LDCs, construction of quantum random access code from a 2-query binary LDC, exponential lower bound. References: [ Kerenidis and de Wolf 04], [ Drucker and de Wolf 11]
   

6. •Probabilistic polynomial time: definition of PP, canonical example, closure under complementation and intersection, PostBQP and its closure properties, power: NP in PostBQP, PostBQP in PP, PP in PostBQP. References: [Aaronson 05], [ wikipedia page by David Pritchard ]
   

7. •Area law in 1D: local Hamiltonian problem (LHP), its complexity, 1D case, matrix product states (MPS), basic properties, characterization in terms of tensor rank, efficient computation of energy w.r.t. a k-body Hamiltonian, area law for 1D gapped systems, existence of efficient MPS approximation, 1D gapped LHP in NP, approximate ground state projector, its construction, implications for area law and MPS approximation. References and notes: [ Hastings 07 ], [ Arad, Kitaev, Landau, Vazirani 13 ]
   

References

Here is a bibliography of the original works mentioned above:    [ bib ]    [ pdf ]

Additional reference materials will be posted here as the course progresses.

Assignments

I encourage collaboration between classmates on the assignments. However, I would like you write solutions on your own, and name your collaborators on the submission.

1. •Out Oct. 4, due Fri., Oct. 18:    [ pdf ]
   

2. •Out Oct. 25, due Fri., Nov. 8:    [ pdf ]
   

3. •Out Nov. 15, due Fri., Nov. 29:    [ pdf ]
   

Project

Here is a partial list of papers on which you may base your course project:    [ bib ]    [ pdf ]    (Feel free to suggest others related to the two themes of the course.) These papers are in addition to the bibliography for the lectures above.

The project consists of a 20-minute in class presentation and a project report in the form of wikipedia pages on the same topic.

The class presentation should define the problem being solved, explain its significance, describe the main result and related work, and the key techniques behind the solution. For your presentation, please pick at least one paper that has not been covered in class.

The project report should be aimed at a broader, but mathematically savvy audience. Tutorials on format and style are available on wikipedia, as also those on creating and editing pages. Samples of pages students have created before are available here. You can access the tutorials by creating a wikipedia account, and linking to the course.

Here is the link to the wikipedia course page:    [ link ]    The student projects may be accessed through this page.

Last updated December 31, 2013