CMSC 38410-1: Quantum Computing

Course description

Autumn 15: Tuesday, Thursday 1:30pm-2:50pm (Ry 277)

Office hours. By appointment.

Homeworks

Lecture notes are available here. Any comments, corrections and suggestions are most welcome.

Literature. Most of the material pertained to this course can be found in the monographs [1-3]. References to more specific sources covering individual topics will be posted here as we go along.
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. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
16. A. Razborov, Communication Complexity, in the International Mathematical Olympiad 50th Anniversary Book.
17. A.C. Yao, Quantum circuit complexity, Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993, pp. 352 - 361.
18. 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.
19. I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
20. A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
21. A. Sherstov, The pattern matrix method for lower bounds on quantum communication, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, 85-94.
22. A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, J. Smotrovs, Separations in Query Complexity Based on Pointer Functions, 2015.
23. S. Aaronson, S. Ben-David, R. Kothari, Separations in query complexity using cheat sheets, 2015.

Progress and references.
- First week: Organizational. A crash course in computational complexity heavily biased toward quantum computing 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), or come to our specialized courses. 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], see also Wikipedia article. 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 facts and notation from linear algebra (tensor products, adjoint operators, unitary operators) can be found in any of our textbooks; I particularly recommend [1, Ch. 2.1].
- Second week: limear algebra cntd.: unitary operators, Hilbert spaces, unit vectors as pure states of a quantum system. Dirac's notation can be found in any of our textbooks; I particularly recommend [1, Ch. 2.1]. Completeness results: [2, Sec. 8.1] (exact realization) and [2, Sec. 8.2, 8.3] (approximate realization). Simulation of probabilistic computations by quantum circuits: [3, Ch. 6.1]. Deutsch algorithm: [3, Ch. 6.3]. Our exposition of Deutsch-Jozsa closely follows the one given in [3, Ch. 6.4]. Hidden Subgroup Problem. Simon's algorithm: [3, Ch. 6.5]. $BQP\subset PP$ (statement).
- Third week: $BQP\subset PP$ (proof): see [1, Ch. 4.5.5] for 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]. Normal operators: [1, Ch. 2.1.6]. Operator $U_a$, its eigenvalues and eigenvectors: [3, Ch. 7.3.3]. Eigenvalue estimation problem. Controlled operators $c-U$ and $c-U^x$: [3, Ch 7.2].
- Fourth week: Quantum Fourier Transform and its inverse [3, Ch 7.1]. Our exposition of the eigenvalue estimation includes elements of phase estimation [3, Ch. 7.1]; we did not discuss the latter problem separately. For an efficient realization of $QFT_{2^h}$ (that we left as an exercise in class), see [3, Ch. 7.3]. Discrete Logarithm: [3, Ch. 7.4]. For the Hidden Subgroup Problem in Abelian groups, I recommend [2, Ch. 13.8]; [7] is a good survey in the non-Abelian case (the application to Graph Isomorphism seems to be a part of folklore). Our exposition of the hybrid method follows [3, Chp. 9.3]. Mega-theorem about polynomial equivalence of various complexity measures for total functions can be found (in pieces) in the survey [8].
- Fifth week: The proof of mega-theorem: see e.g. Theorems 10, 11, 2, 7, 17 and 18 in [8]. You can also check out our lecture notes (although I re-arranged a few things this year). A good survey on the sensitivity vs. block sensitivity (written by former UC students) is [9], and a good survey on the approximate polynomial degree is [10]. Applications of the block sensitivity bound and the approximate degree bound: [3, Ch. 9.6.1, 9.5.1]. The breakthrough on approximate polynomial degree of the AND-OR function was achieved independently in [11] and [12]. Ambainis's adversary bound [3, Ch. 9.7].
- Sixth week: Ambainis's adversary method (cntd). Applications and a discussion on the relative strength of various methods. For the relations between quantum query complexity and classical formula size see [13,14]. The standard textbook in classical communication complexity is [15] (or check out my survey [16] at a very introductory level). The quantum communication complexity was introduced in [17]. The relation between quantum decision tree and communication complexities was observed in [18]. The decomposition theorem for quantum communication protocols also appeared in [17], and it was further refined in [19,20].
- Seventh week: The discrepancy method is the standard tool in communication complexity (not only in quantum!), see again [17, 19] for examples. Lower bound in terms of the spectral norm of the communication matrix is from [19]. Approximate trace norm was introduced in [20], and the same paper proved tight lower bounds for symmetric predicates. The proof based on generalized discrepancy was given in [21]. Our exposition of Quantum Probability follows [3, Ch. 3.5] or [2, Ch. 10]. Density matrices. Concrete examples of physically realizable operators (aka superoperators): unitary action, probabilistic quantum circuits, the depolarizing channel noise model (an excellent overview of other noise models can be found in [1, Ch. 8.3]), tracing out (= partial measurement), unitary embeddings. Towards a general definition of a superoperator.
- Eighth week: guest speaker (Professor Drucker). Direct sum and direct product theorems for classical/quantum queries (Jain-Klauck-Santha; Drucker; Lee-Roland). Sherstov's strong DPT for generalized discrepancy. Composition theorems for queries (Reichardt; Montanaro). Spalek-Szegedy's results unifying various generalizations of the Ambainis quantum adversary method. Reichardt's results showing completeness of the negative-weight adversary method for quantum query complexity lower bounds (without proofs). New separations in query complexity: [22, 23].
- Nineth week (short): 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. Tracing-out + unitary embedding: [2, Problem 11.1]. Operator-sum representation: [1, Ch. 8.2.3.]; for another account see [2, Ch. 11.1]. [1, Theorem 8.1] provides a complete proof of the most non-trivial equivalence we mentioned in class. Trace distance: [1, Ch. 9.2.1]. Superoperators do not increase trace distance: [1, Theorem 9.2]. No cloning theorem: [1, Box 12.1]. An excellent overview of various noise models (some of them quite sophisticated) can be found in [1, Ch. 8.3]. Projective measurements: [3, Ch. 3.4]. Majority voting: [1, Ch. 10.1].
- Tenth week: Three qubit bit/phase flip codes are in [1, Ch. 10.1], and the Shor code is in [1, Ch. 10.2]. Unitary equivalence for mixed states: [1, Theorem 2.6]. Unitary equivalence for operator-sum representations: [1, Theorem 8.2]. Criterium of quantum recovery (with a partial proof): [1, Theorem 10.1]. Quantum teleportation: [1, Ch. 1.3.7].