Semi-definite programs in Quantum Information
Semi-definite programs in Quantum Information
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.Semi-definite program, dual program, weak and strong duality, Slater condition, complementary slackness, state distinguishability problem, Holevo and Yuen-Kennedy-Lax conditions [ pdf ]
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.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.Quantum query complexity, adversary bound, SDP formulation, span programs, their equivalence via SDP duality, algorithm from span programs [ pdf ]
References
1.John Watrous. Lecture 20 of CS 798 Advanced Research Topics, Theory of Quantum Information. University of Waterloo, Fall 2008. [ pdf ]
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.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.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.Ben Reichardt. Quantum query complexity. Invited tutorial, Workshop on Quantum Information Processing, Singapore, January 9, 2011. [ pdf ]
Homework [ pdf ]