CMSC/MATH 38420: Mathematics of Quantum Computing

Winter 25: Tuesday, Thursday 2pm-3:20pm (Ryerson 277)

Office hours. By appointment. The easiest way is to talk right after class, and the preferred way is to initiate a discussion on Ed -- this way more people will benefit from it.

Homeworks.

Lecture notes from previous versions of this course (formerly known as "Quantum Computing") are available here. Use with caution -- I do it slightly differently every year, and it is not intended to be a replacement for attending lectures. Any comments, corrections and suggestions are very 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 (we will review those few things we need for our course). 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. E. Bernstein, U. Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, 26(5), 1411-1473, 1997.
6. S. Jukna, Boolean Function Complexity: Advances and Frontiers, Springer-Verlag, 2012.
7. R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, Cambridge University Press, 1997.
8. C. Lomont, The Hidden Subgroup Problem - Review and Open Problems, 2004.
9. H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey, Theoretical Computer Science, 288(1):21-43, 2002.
10. H. Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190(3): 949-955, 2019.
11. S. Aaronson, S. Ben-David, R. Kothari, S. Rao and A. Tal, Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem, Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, June 2021, pp. 1330 - 1342.
12. M. Bun and J. Thaler, Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities , Information and Computation, 243, 1-25, 2015.
13. A. Sherstov, Approximating the AND-OR Tree, Theory of Computing, 9, 653-663, 2013.
14. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
15. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, 2011.
16. A.C. Yao, Quantum circuit complexity, Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993, pp. 352 - 361.
17. 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.
18. I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
19. A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
20. 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.
21. J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65(4): 612-625, 2002.
Syllabus 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 the subject more generally, see the excellent textbook [4] or come to my course in the Spring quarter. Quantum Turing Machines were introduced in [5]. For a comprehensive treatment of circuit (non-uniform) complexity I particularly recommend [6]. Reversible circuits: [3, Ch. 1.5] or [2, Ch, 7]; simulation of classical computations with reversible ones (aka Garbage Removal Lemma): [3, Fig. 1.6] or [2, Lemma 7.2]. 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. [7]. Basic facts and notation from linear algebra (Hilbert spaces, tensor products, unit vectors as pure states of a quantum system, adjoint and unitary operators etc.) can be found in any of the three textbooks; I particularly recommend [1, Ch. 2.1].
- Second week: Examples of unitary one-qubit gates (other than permutations): Pauli matrices and Hadamard gate. Dirac's notation. Completeness result for exact realization (without proof): [2, Ch. 8.1]. Universal/complete bases and Solovay-Kitaev theorem (without proof): [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 discussed later in the course, for now see the Wikipedia article or [8]. Simon's algorithm: [3, Ch. 6.5]. $BQP\subset PP$: see [1, Ch. 4.5.5] for a slightly weaker result.
- Third week: $BQP\subset PP$ cntd. Grover's search algorithm: [3, Ch. 8.1]. Number-theoretical preliminaries for Shor's algorithm: [2, Ch. 13.3 + Appendix A] or [1, Appendix 4]. Normal operators: [1, Ch. 2.1.6]. Operator $U_a$: [3, Ch. 7.3.3].
- Fourth week: Shor's algorithm cntd. Eigenvalue estimation problem. 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]; [8] is a good survey for the non-Abelian case (the application to Graph Isomorphism seems to be a part of folklore). As I mentioned, not much seems to have been done on HSP since that. Quantum Complexity Theory. 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 [9], see in particular Theorems 10, 11, 2, 7, 17 and 18.
- Sixth week: ``Mega-theorem'' cntd. The solution of the sensitivity conjecture (without proof): [10]. See [11] and the references therein for (to the best of my knowledge) the most recent refinements of the mega-theorem based on [10]. AND-OR tree function in the context of Ambainis's adversary method: [3, Ch. 9.7]. Its approximate degree (without proof): [12, 13]. The standard textbook in classical communication complexity is [14] (see also [4], [6] or check out my survey [15] for an exposition at a highly introductory level). Deterministic communication complexity [14, Ch. 1.4] or [15, Sct. 2]. The rank lower bound [14, Ch. 1.4]. Probabilistic communication complexity [14, Ch. 3]. Rabin's protocol for the equality function [14, Example 3.5]. The quantum communication complexity was introduced in [16]. The relation between quantum query and communication complexities for block-composed functions was observed in [17]. The decomposition theorem for quantum communication protocols appeared in [16], and it was further refined in [18, 19].
- Seventh week: Discrepancy method [18], and its generalization based on approximate trace norm [19]. Lower bounds for Disjointness and other block-composed problems based on symmetric functions (without proof): [19, 20]. Lower bound for the sign-rank (without proof): [21]. Our exposition of Quantum Probability follows, more or less, [3, Ch. 3.5] or [2, Ch. 10]. Density matrices. Bloch sphere and Bloch vectors: [1, Exerc. 2.72, Ch. 4.2] or [3, Ch. 3.1, 4.2.1]. Concrete examples of physically realizable operators (aka superoperators): unitary action, probabilistic quantum circuits, one qubit noise models (an excellent overview of those, including beautiful illustrations on the Bloch sphere, can be found in [1, Ch. 8.3]), tracing out, projective measurements, unitary embeddings. Three equivalent definitions of a superoperator. The axiomatic one is in [1, Ch. 8.2.4] (note that they consider a slightly more general version 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]. Equivalence of the first and the third definition: [1, Theorem 8.1], we only proved the easy direction.
- Eighth week: No-cloning theorem: [3, Theorem 10.4.1]. Superoperators do not increase trace distance: [1, Theorem 9.2]. Classical error-correction (very briefly). Projective and syndrom measurements [3, Ch. 3.4]. Three qubit bit and phase flip codes: [1, Ch. 10.1]. Shor's nine-qubit code: [1, Ch. 10.2]. Criterium of quantum recovery (single error channel), statement: [1, Theorem 10.1]. Discretization of errors (without proof): [1, Theorem 10.2]. Preliminaries for the proof of [1, Theorem 10.1]. Unitary equivalence for ensembles of pure states: [1, Theorem 2.6]. Unitary equivalence for operator-sum representations: [1, Theorem 8.2].
- Ninth week: Polar Decomposition Theorem: any textbook in linear algebra or [1, Theorem 2.3]. Criterium of quantum recovery, proof. Basics of the theory of stabilizer codes: [1, Ch. 10.5]. The five qubit code, as well as a few other important examples of stabilizer codes, can be found in [1, Ch. 10.5.6]. Classical and quantum interactive proof systems: *very* informal overview. For the development I mentioned at the very end, you can read the Quanta Magazine article (and the literature cited therein). (We wrapped our course on quite a high note!)