These are four lectures (six hours) given by Ashwin Nayak as part of QIC 890/891 Selected Advanced Topics in Quantum Information, Institute for Quantum Computing, University of Waterloo, Spring 2011.

Lectures

1. 1.Semi-definite program, dual program, weak and strong duality, Slater condition, complementary slackness, state distinguishability problem, Holevo and Yuen-Kennedy-Lax conditions    [ pdf ]
   

2. 2.Alternative forms of SDP, quantum interactive proofs, circuit distinguishability, SDP formulation of maximum acceptance probability, QIP is contained in EXP, polynomial-time algorithm for approximating SDPs    [ pdf ]
   

3. 3.XOR non-local games, parallel repetition, sum of two games, Tsirelson characterization, SDP formulation of best quantum strategy, the bias of sum of two games    [ pdf ]
   

4. 4.Quantum query complexity, adversary bound, SDP formulation, span programs, their equivalence via SDP duality, algorithm from span programs    [ pdf ]
   

References

1. 1.John Watrous. Lecture 20 of CS 798 Advanced Research Topics, Theory of Quantum Information. University of Waterloo, Fall 2008.   [ pdf ]
   

2. 2.L. Lovasz. Semidefinite programs and combinatorial optimization. Recent Advances in Algorithms and Combinatorics (ed. B.A. Reed, C.L. Linhares-Sales), CMS Books Math./Ouvrages Math. SMC 11, Springer, New York (2003), 137–194.   [ pdf ]
   

3. 3.A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 608–617, 2000.   [ pdf ]
   

4. 4.Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. Computational Complexity, 17:282–299 (2008).   [ pdf ]
   

5. 5.Ben Reichardt. Quantum query complexity. Invited tutorial, Workshop on Quantum Information Processing, Singapore, January 9, 2011.   [ pdf ]
   

Homework        [ pdf ]