CMSC/MATH 38420: Mathematics of Quantum Computing

Winter 24: Tuesday, Thursday 2pm-3:20pm (Ryerson 276)

Office hours. By appointment. The easiest way is to talk right after class, and the preferred way is to ask your question on Ed -- this way more people may benefit from the discussion.

Homeworks.
- Assignment #1, due February 2
- Assignment #2, due February 16
- Assignment #3, due March 1

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 (of which we will review 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. 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. R. Raz, A. Tal, Oracle Separation of BQP and PH, Journal of the ACM, 69(4), 2022.
9. C. Lomont, The Hidden Subgroup Problem - Review and Open Problems, 2004.
10. H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey, Theoretical Computer Science, 288(1):21-43, 2002.
11. H. Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190(3): 949-955, 2019.
12. 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.
13. M. Bun and J. Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities, Information and Computation, 243, 1-25, 2015.
14. A. Sherstov, Approximating the AND-OR Tree, Theory of Computing, 9, 653-663, 2013.
15. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
16. A. Razborov, Communication Complexity, in the book An Invitation to Mathematics: from Competitions to Research, 2011.
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. 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.
22. I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
Syllabus and references.
- First week (short): 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]. 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].
- Second week: 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]. 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 and Solovay-Kitaev theorem: [2, Ch. 8.2, 8.3] or [3, Ch. 4.3, 4.4]. Simulation of probabilistic computations by quantum circuits: [3, Ch. 6.1].
- Third week: $BQP\subset PP$: see [1, Ch. 4.5.5] for a slightly weaker result. Oracle separation of $BQP$ and $PH$ (just mentioned): [8] (consult [4, Ch. 3.4] for oracle separations and [4, Ch. 5] for the polynomial hierarchy). 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 [9]. Simon's algorithm: [3, Ch. 6.5]. Grover's search algorithm: [3, Ch. 8.1].
- Fourth week: Grover's search algorithm cntd. 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. 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].
- Fifth week: Shor's algorithm cntd. Discrete Logarithm: [3, Ch. 7.4]. For the Hidden Subgroup Problem in Abelian groups, I recommend [2, Ch. 13.8]; as I mentioned, [9] is a good survey for the non-Abelian case (the application to Graph Isomorphism seems to be a part of folklore). Quantum Complexity Theory. Lower bounds for quantum search via the hybrid method; our exposition more or less follows [3, Ch. 9.3]. ``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 [10], see in particular Theorems 10, 11, 2, 7, 17 and 18.
- Sixth week: Mega-theorem cntd. The solution of the sensitivity conjecture: [11]. See [12] and the references therein for (to the best of my knowledge) the most recent refinements of the mega-theorem based on [11]. AND-OR tree function in the context of Ambainis's method: [3, Ch. 9.7]. Its approximate degree (without proof): [13, 14]. The standard textbook in classical communication complexity is [15] (see also [4], [6] or check out my survey [16] for an exposition at a highly introductory level). Deterministic communication complexity [15, Ch. 1.4] or [16, Sct. 2].
- Seventh week: The rank lower bound [15, Ch. 1.4]. Probabilistic communication complexity [15, Ch. 3]. Rabin's protocol for the equality function [15, Example 3.5]. The quantum communication complexity was introduced in [17]. The relation between quantum query and communication complexities for block-composed functions was observed in [18]. Lower bounds in the symmetric case (without proof): [19,20]. Lower bounds on the approximate rank (without proof): [21]. The decomposition theorem for quantum communication protocols appeared in [17], and it was further refined in [22, 19]. Discrepancy method [22]. 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]).
- Eighth week: Examples of superoperators cntd: one qubit noise models, 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. No-cloning theorem: [3, Theorem 10.4.1]. Superoperators do not increase trace distance: [1, Theorem 9.2]. Classical error-correction (very briefly). 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, but there are also others, see references in these articles. Projective and syndrom measurements [3, Ch. 3.4]. Three qubit bit flip code: [1, Ch. 10.1].
- Nineth week: Three qubit phase flip code: [1, Ch. 10.1]. Shor's nine-qubit code is in [1, Ch. 10.2]. Criterium of quantum recovery (single error channel), statement: [1, Theorem 10.1]. Unitary equivalence for operator-sum representations (proof in easy direction): [1, Theorem 8.2]. Criterium of quantum recovery, proof in easy direction. Discretization of the errors (correctable linear spaces for operator elements): [1, Sct. 10.3.1]. Basics of the theory of stabilizer codes: [1, Ch. 10.5]. Criterium of quantum recovery, a sketch of a proof in the interesting direction.