CMSC/MATH 38420: Mathematics of Quantum Computing

Winter 23: Tuesday, Thursday 9:30am-10:50am (Crerar 011)

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

Lecture notes from previous offerings of this course (formerly known as "Quantum Computing") are available here. Use with care -- I do it slightly 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. 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. R. Raz, A. Tal, Oracle Separation of BQP and PH, Journal of the ACM, 69(4), 2022.
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. 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. R. Bhatia, Matrix analysis, Springer-Verlag, 2012.
22. 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.
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 more details, see the excellent textbook [4]. Quantum Turing Machines were introduced in [5]. For a comprehensive treatment of circuit complexity I particularly recommend [6]. 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. [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.
- Second week: 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 [8] (and do drop me a word if you know of more recent developments). Simon's algorithm: [3, Ch. 6.5]. $BQP\subset PP$: see [1, Ch. 4.5.5] for a slightly weaker result. Oracle separation of $BPP$ and $BQP$: [5]; oracle separation of $BQP$ and $PH$: [9] (consult [4, Ch. 3.4] for oracle separations and [4, Ch. 5] for the polynomial hierarchy).
- 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. Controlled operators $c-U$ (sometimes called $\Lambda^1(U)$) and $c-U^x$: [3, Ch 7.2].
- Fourth week: Shor's algorithm cntd. 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, [8] still seems to be 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].
- 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 [10], see in particular Theorems 10, 11, 2, 7, 17 and 18. The solution of the sensitivity conjecture: [11]. See [12] and the references therein for (apparently) the most recent refinements of the mega-theorem, based on [11]. Approximate degree of AND-OR tree (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).
- Sixth week: Deterministic communication complexity [15, Ch. 1.4] or [16, Sct. 2]. 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]. The decomposition theorem for quantum communication protocols also appeared in [17], and it was further refined in [19,20]. Discrepancy method. The lower bound in terms of the spectral norm of the communication matrix is from [19].
- Seventh week: Generalized discrepancy method. For the trace norm (as well as many others) see [21]. Approximate trace norm was introduced in [19], 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 [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]), tracing out, projective measurements, unitary embeddings. Three equivalent definitions. 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].
- Eighth week: 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]. Criterium of quantum recovery (single error channel): [1, Theorem 10.1]. Unitary equivalence for mixed states: [1, Theorem 2.6]. Unitary equivalence for operator-sum representations: [1, Theorem 8.2].
- Ninth week: Criterium of quantum recovery (single error channel), proof. 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].