CMSC/MATH 38410: Quantum Computing

Winter 22: Tuesday, Thursday 2pm-3:20pm (Ry 276)

Office hours. By appointment (say, stay after class) or ask your question on Ed -- this way everyone benefits from the discussion.

Homeworks

Lecture notes from previous offerings of this course are available here. Use with care -- I do it a bit differently every year. 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], for way more advanced stuff see Scott Aaronson's Barbados lectures. [4] is a standard textbook in computational complexity (of which we will use only a tiny bit). 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. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
5. S. Jukna, Boolean Function Complexity: Advances and Frontiers, Springer-Verlag, 2012.
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. H. Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190(3): 949-955, 2019.
10. S. Aaronson, S. Ben-David, R. Kothari, S. Rao and A. Tal, Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem, 2020.
11. M. Bun and J. Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities, Information and Computation, 243, 1-25, 2015.
12. A. Sherstov, Approximating the AND-OR Tree, Theory of Computing, 9, 653-663, 2013.
13. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
14. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, 2011.
15. A.C. Yao, Quantum circuit complexity, Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993, pp. 352 - 361.
16. 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.
17. I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
18. A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
19. J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65(4), 612-625, 2002.
20. R. Bhatia, Matrix analysis, Springer-Verlag, 2012.
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.
Progress and references.
- First week: 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]. If you are interested in more details, see the excellent textbook [4]. For a comprehensive treatment of circuit complexity I particularly recommend [5]. 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 computation: [2, Ch. 4.3] (for an in-depth treatment see [4, Ch. 1.7]). For doubly stochastic matrices, Birkhoff-von Neumann theorem and much more see e.g. [6]. Basic facts and notation from linear algebra (Hilbert spaces, tensor products, unit vectors as pure states of a quantum system etc.) can be found in any of the three textbooks; I particularly recommend [1, Ch. 2.1].
- Second week: Basic facts and notation cntd. (adjoint and unitary operators). Examples of unitary one-qubit gates (other than permutations): Pauli matrices and Hadamard gate. Dirac's notation. Completeness result for exact realization: [2, Ch. 8.1]. Universal/complete bases: [2, Ch. 8.2, 8.3] or [3, Ch. 4.3, 4.4]. 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]. The Hidden Subgroup Problem will be thoroughly discussed later in the course, for now see [7] (and do drop me a word if you know of more recent developments). Simon's algorithm: [3, Ch. 6.5].
- Third week: Grover's search algorithm: [3, Ch. 8.1]. Shor's algorithm. The reduction of factoring to order-finding goes back to Miller (1975). Our exposition is close to [2, Ch. 13.3] but the best shot at sometimes tedious technical details is [1, Appendix 4]. In particular, the continuous fraction result that we skipped is [1, Theorem A4.16]. Normal operators: [1, Ch. 2.1.6]. Operator $U_a$, its eigenvalues and eigenvectors: [3, Ch. 7.3.3]. Eigenvalue estimation problem.
- Fourth week: Controlled operators $c-U$ (sometimes called $\Lambda^1(U)$) and $c-U^x$: [3, Ch 7.2]. Quantum Fourier Transform $QFT_m$ over cyclic groups and its inverse [3, Ch 7.1]. For an efficient realization of $QFT_{2^h}$ 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]; as I mentioned, [7] is still a good survey for the non-Abelian case (the application to Graph Isomorphism seems to be a part of folklore). Lower bounds for quantum search via the hybrid method; our exposition more or less follows [3, Ch. 9.3].
- Fifth week: Hybrid method cntd. Mega-theorem about polynomial equivalence of various complexity measures for total functions, along with references, can be found (in bits and pieces) in the survey [8], see in particular Theorems 10, 11, 2, 7, 17 and 18. The solution of the sensitivity conjecture: [9]. See [10] and the references therein for (apparently) the most recent refinements of the mega-theorem, based on [9].
- Sixth week: Mega-theorem cntd. Approximate degree of AND-OR tree (without proof): [11, 12]. The standard textbook in classical communication complexity is [13] (see also [4], [5] or check out my survey [14] for an exposition at a highly introductory level). Deterministic communication complexity [13, Ch. 1.4] or [14, Sct. 2]. The rank lower bound [13, Ch. 1.4]. Probabilistic communication complexity [13, Ch. 3]. Rabin's protocol for the equality function [13, Example 3.5]. The quantum communication complexity was introduced in [15]. The relation between quantum query and communication complexities for block-composed functions was observed in [16]. The decomposition theorem for quantum communication protocols also appeared in [15], and it was further refined in [17,18].
- Seventh week: The decomposition theorem cntd. Discrepancy method. The lower bound in terms of the spectral norm of the communication matrix is from [17]. The same lower bound works for the (classical) unbounded-error case, without proof: [19]. For the trace norm (as well as many others) see [20]. Approximate trace norm was introduced in [18], and the same paper proved tight lower bounds for block-composed versions of symmetric predicates. A simpler 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, one qubit noise models (an excellent overview of those can be found in [1, Ch. 8.3]), tracing out, projective measurements, unitary embeddings. The axiomatic definition of superoperators is in [1, Ch. 8.2.4] (note that they consider a slightly more general version when the trace is allowed to decrease).
- Eighth week: the definition of superoperators cntd. Tracing-out + unitary embedding: [2, Problem 11.1]. Operator-sum representation: [1, Ch. 8.2.3.]; for another account see [2, Ch. 11.1]. Superoperators do not increase trace distance: [1, Theorem 9.2]. No-cloning theorem: [3, Theorem 10.4.1]. Classical error-correction (concept). For the best transmission rate $R$ in terms of the relative error $\delta$, there are many bounds, both upper and lower. The most prominent ones still seem to be Gilbert-Varshamov bound and Hamming bound. Projective and syndrom measurements [3, Ch. 3.4]. Three qubit bit/phase flip codes are in [1, Ch. 10.1], and the Shor code is in [1, Ch. 10.2].
- Ninth week: Criterium of quantum recovery (single error channel): [1, Theorem 10.1]. Discretization of the errors (correctable linear spaces for operator elements): [1, Sct. 10.3.1]. Unitary equivalence for mixed states: [1, Theorem 2.6]. Unitary equivalence for operator-sum representations: [1, Theorem 8.2]. Stabilizer codes (basics): [1, Ch. 10.5].