Assignment #1, due May 9.

1. M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.
2. A. Kitaev, A. Shen, M. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics, Vol. 47, American Mathematical Society, 2002.
3. P. Kaye, R. Laflamme, M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007.
4. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
5. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
6. R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, Cambridge University Press, 1997.
7. C. Lomont, The Hidden Subgroup Problem - Review and Open Problems, 2004.
8. H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science, 288(1):21-43, 2002.
9. P. Hatamii, R. Kulkarni and D. Pankratov. Variations on the Sensitivity Conjecture, Theory of Computing Library, Graduate Surveys Number 4 (2011) pp. 1-27.
10. Y. Shi. Approximate polynomial degree of Boolean functions and its applications. Proceedings of the 4th International Congress of Chinese Mathematicians, 2007.
11. M. Bun and J. Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities, 2013.
12. A. Sherstov, Approximating the AND-OR Tree, 2013.
13. S. Laplante, T. Lee, M. Szegedy. The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity, 15(2): 163-196 (2006).
14. A. Ambainis, A. M. Childs, B. Reichardt, R. Spalek, S. Zhang. Any AND-OR Formula of Size N can be Evaluated in time N1/2+o(1) on a Quantum Computer. FOCS 2007: 363-372.
15. A. Ambainis, Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing, 37(1): 210-239 (2007).
16. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
17. A. Razborov, Communication Complexity, in the International Mathematical Olympiad 50th Anniversary Book.
18. A.C. Yao, Quantum circuit complexity, Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993, pp. 352 - 361.
19. H. Buhrman, R. Cleve and A. Wigderson, Quantum vs. classical communication and computation, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, May 1998, pp. 63 - 68.
20. S. Aaronson and A. Ambainis, Quantum Search of Spatial Regions, Theory of Computing, 1:47-79, 2005.
21. I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
22. A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
23. A. Sherstov, The pattern matrix method for lower bounds on quantum communication, 2008.

• First week: A crash course in computational complexity that should be sufficient for our purposes can be found in [2, Part 1] or [1, Ch. 3.1-3.2]. For more detailed treatment see excellent textbooks [4] (undergraduate level) and [5] (a little bit advanced). Reversible circuits: [3, Ch. 1.5] or [2, Ch, 7]; simulation of any classical computation with a reversible one (aka Garbage Removal Lemma): [3, Fig. 1.6] or [2, Lemma 7.2]. The physics of Landauer's principle is discussed in [1, Ch. 3.2.5]. Matrix form of circuit computations: [3, Ch. 1.4]. Probabilistic computations: [2, Ch. 4.3] (as always, for an in-depth treatment see [4,5]). For doubly stochastic matrices, Birkhoff-von Neumann theorem (and much more) see e.g. [6]. Rudimentary notation from linear algebra, including Dirac's notation can be found in any of our textbooks; I particularly recommend [1, Ch. 2.1].
• Second week: Universal (aka complete) bases: [2, Ch, 8.2] or [1, Ch. 4.5]. Equivalence of universal bases: [2, Cor. 8.5.1]. Discussion of probabilistic vs. quantum: [3, Ch. 6.1]. Deutsch algorithm: [3, Ch. 6.3]. Our exposition of Deutsch-Jozsa and Simon's algorithms closely follows the one given in [3, Ch. 6.3] and [3, Ch. 6.4]. We will thoroughly discuss the Hidden Subgroup Problem later, but if you are already curious, you can check out [7]. $BQP\subspace PP$.
• Third week: $BQP\subset PP$ cntd.; see [1, Ch. 4.5.5] for a proof of a slightly weaker result. Grover's search algorithm: [3, Ch. 8.1]. The reduction of factoring to order-finding goes back to Miller (1975); our exposition is close to [2, Ch. 13.3]. Continued fractions: [3, Thm. 7.1.7]. Eigenvalue estimation problem and construction of the operator $c-U^x$ (we finally decided to call it Shor-U) [3, Ch 7.2 ]. Quantum Fourier Transform and its inverse [3, Ch 7.1].
• Fourth week: Shor's factoring algorithm cntd. Our exposition of the eigenvalue estimation includes elements of phase estimation [3, Ch. 7.1]; we did not discuss the latter problem separately. And the exposition in [3, Ch. 7.3] also includes an efficient realization of $QFT_{2^h}$ that we left as an exercise in class. Finally, the analytical expression for the error can be found in [3, Ch. 7.1.1]. Discrete Logarithm: [3, Ch. 7.4] (note, however, that we did not use the fancy notation with $\widetilde$). For the Hidden Subgroup Problem in Abelian groups, I recommend [2, Ch. 13.8], and [7] is a good survey on the non-Abelian case. Our exposition of the hybrid method follows [3, Chp. 9.3] (although, as in many other cases, we somewhat re-arranged the material). Mega-theorem about polynomial equivalence of various complexity measures for total functions.
• Fifth week: The proof of mega-theorem cntd. It can be found e.g. (in pieces) in the survey [8]: see theorems 10, 11, 2, 7, 17 and 18 there. A good survey on the sensitivity vs. block sensitivity is [9], and a good survey on the approximate polynomial degree is [10]. The recent breakthrough (approximate polynomial degree of the tribes function) was achieved independently in [11] and [12]. Ambainis's adversary method (we only did a sketch without proof): [3, Ch. 9.7 and A5]. For the relations between quantum query complexity and classical formula size see [13,14]. Ambainis's quantum walk (sketch): [15].
• Sixth week: Ambainis's quantum walk cntd. The standard textbook in classical communication complexity is [16] (or check out my survey [17] at a very introductory level). The quantum communication complexity was introduced in [18]. The relation between quantum decision tree and communication complexities was observed in [19], and the improvement of the upper bound for DISJOINTNESS is in [20]. The decomposition theorem for quantum communication protocols also appeared in [18], and it was further refined in [21,22]. The discrepancy method is the standard tool in communication complexity (not only in quantum!), see again [18, 21] for examples. Lower bound in terms of the spectral norm of the communication matrix is from [21].
• Seventh week: Approximate trace norm was introduced in [22], and the same paper proved tight lower bounds for symmetric predicates. The proof based on generalized discrepancy was given in [23]. Quantum Probability: [3, Ch. 3.5] or [2, Ch. 10]. An excellent overview of various noise models (some of them are quite sophisticated) can be found in [1, Ch. 8.3]. The axiomatic definition of physically realizable operators (aka superoperatotrs) is in [1, Ch. 8.2.4]; note that they consider a slightly more general case when the trace is allowed to decrease. Operator-sum representation: [1, Ch. 8.2.3.]. For another account see [2, Ch, 11.1]; in particular, [2, Problems 11.1, 11.2] are precisely the two parts of our theorem on different characterizations of superoperators. [1, Theorem 8.1] provides a complete proof of the part that we sketched in class.
• Eighth week: Trace distance [1, Ch. 9.2.1]. Superoperators do not increase trace distance [1, Theorem 9.2]. No cloning theorem: [1, Box 12.1]. Three qubit bit/phase flip codes are in [1, Ch. 10.1], and the Shor code is in [1, Ch. 10.2]. General theory of quantum error-correction: [1, Ch. 10.3]; again, in class we considered only the trace-preserving case. Unitary equivalence for mixed states: [1, Theorem 2.6]. Unitary equivalence for operator-sum representations: [1, Theorem 8.2]. Criterium of quantum recovery: [1, Theorem 10.1].
• Ninth week: Criterium of quantum recovery cntd. Stabilizer codes [1, Ch. 10.5]. Error-correction conditions for stabilizer codes [1, Theorem 10.8]. Quantum teleportation [1, Ch. 1.3.7]. Superdense coding [1, Ch. 2.3]. What we did not have time to do and left for another course: Shannon and von Neumann entropies [1, Ch. 11].
• Tenth week (short): projects. Charles Forgy: "A Summary of Current Implementation of Adiabatic Quantum Computing" and Young Kun Ko: "Extended Formulations".