CMSC/MATH 38410: Quantum Computing

Winter 21: Tuesday, Thursday 9:40am-11am

Office hours. By appointment -- send me e-mail.

Homeworks

Lecture notes from previous offerings of this course 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], 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. R. Raz, A,Tal, Oracle separation of BQP and PH, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pages 13-23.
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. M. Bun and J. Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities, Information and Computation, 243, 1-25, 2015.
11. A. Sherstov Approximating the AND-OR Tree, Theory of Computing, 9, 653-663, 2013.
12. A. Ambainis, K. Baladis, A. Belovs, T. Lee, M. Santha, J. Smotrovs, Separations in Query Complexity Based on Pointer Functions, Journal of the ACM, 64(5), 2017.
13. H. Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190(3): 949-955, 2019.
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. 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. 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.
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. R. Bhatia, Matrix analysis, Sprinegr-Verlag, 2012.
23. S. Aaronson, G. Kuperberg, Quantum versus Classical Proofs and Advice, Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, 2007, 115-128.
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]. Rudimentary facts and notation from linear algebra (tensor products, Hilbert spaces, adjoint operators, unitary operators, unit vectors as pure states of a quantum system etc.) can be found in any of our textbooks; I particularly recommend [1, Ch. 2.1]. Mathematics and physics of Pauli matrices are extensively discussed in the Wikipedia article. 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]. Oracle separation results in complexity theory: [4, Ch. 3.4]. Oracle separation of BQP from PH (and hence BPP): [7]. Deutsch algorithm: [3, Ch. 6.3]. Our exposition of Deutsch-Jozsa closely follows the one given in [3, Ch. 6.4]. 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 any more recent developments). Simon's algorithm: [3, Ch. 6.5]. $BQP\subset PP$: see [1, Ch. 4.5.5] for a slightly weaker result.
- 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 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$ (aka $\Lambda^1(U)$) and $c-U^x$: [3, Ch 7.2]. Quantum Fourier Transform $QFT_m$ and its inverse [3, Ch 7.1]. For an efficient realization of $QFT_{2^h}$ see [3, Ch. 7.3].
- Fourth week: Discrete Logarithm: [3, Ch. 7.4]. For the Hidden Subgroup Problem in Abelian groups, I recommend [2, Ch. 13.8]; as I said before, [8] 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 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 [9], see in particular Theorems 10, 11, 2, 7, 17 and 18.
- Fifth week: Mega-theorem cntd. Approximate degree of AND-OR tree (without proof): [10,11]. The paper [12] exploits pointer functions technique for solving more open problems in the area; in particular it gives strong separations between the opposite sides of the spectrum in our mega-theorem. The solution of the sensitivity conjecture: [13]. The standard textbook in classical communication complexity is [14] (see also [4], [5] 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].
- Sixth week: 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 decomposition theorem for quantum communication protocols also appeared in [16], and it was further refined in [17,18]. The lower bound in terms of the spectral norm of the communication matrix is from [17]. The same lower bound for the (classical) unbounded-error case, without proof: [19]. The relation between quantum decision tree and communication complexities for block-composed functions was observed in [20]. Lower bounds for block-composed functions with the outer function symmetric (statement): [18,21].
- Seventh week: For trace norm (as well as many others): [22]. Approximate trace norm was introduced in [18], and the same paper proved tight lower bounds for 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 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 detailed proof of the equivalence of two definitions we sketched in class. Trace distance: [1, Ch. 9.2.1]. Superoperators do not increase trace distance: [1, Theorem 9.2].
- Eighth week: Classical error-correction (concept). 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]. This Wikipedia article provides a very good overview of those aspects of quantum error-correction we have touched in our course. Criterium of quantum recovery [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 cntd. Discretization of the errors: [1, Sct. 10.3.1]. Stabilizer codes [1, Ch. 10.5]. Quantum Merlin-Arthur: [23].