CMSC 38410-1: Quantum Computing
Course description
Winter 18: Tuesday, Thursday 9:30am-10:50am (Kent 103)
-
Office hours. By appointment -- drop me a word.
-
Homeworks
-
Lecture notes 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], and you can find (much) more
advanced material in Scott Aaronson's Barbados lectures. References to more specific sources covering individual topics will be posted here as we go along.
-
M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.
-
A. Kitaev, A. Shen, M. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics, Vol. 47, American Mathematical Society, 2002.
-
P. Kaye, R. Laflamme, M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007.
-
M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
-
S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
-
S. Jukna, Boolean Function Complexity: Advances and Frontiers, Springer-Verlag, 2012.
-
R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, Cambridge University Press, 1997.
-
F. Wang, The Hidden Subgroup Problem, 2010.
-
H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey.
Theoretical Computer Science, 288(1):21-43, 2002.
-
P. Hatamii, R. Kulkarni and D. Pankratov. Variations on the Sensitivity Conjecture, Theory of Computing Library, Graduate Surveys Number 4 (2011) pp. 1-27.
-
Y. Shi. Approximate polynomial degree of Boolean functions and its applications. Proceedings of the 4th International Congress of Chinese Mathematicians, 2007.
-
M. Bun and J. Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities, 2013.
-
A. Sherstov, Approximating the AND-OR Tree, 2013.
-
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.
-
E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
-
A. Razborov, Communication Complexity, in the International Mathematical Olympiad 50th Anniversary Book.
-
A.C. Yao, Quantum circuit complexity, Proceedings of the 34th Annual IEEE
Symposium on Foundations of Computer Science, November 1993, pp. 352 - 361.
-
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.
-
I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
-
A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
-
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.
-
A. Drucker and R. de Wolf,
Quantum Proofs for Classical Theorems, TOC Graduate Surveys, 2011.
-
A. Drucker and R. de Wolf,
Uniform Approximation by (Quantum) Polynomials, QIC, 2011.
-
B. Reichardt, Reflections for quantum query algorithms, SODA 2011.
-
A. Tal, Formula Lower Bounds via the Quantum Method, STOC 2017.
-
A. Nayak, Optimal lower bounds for quantum automata and random access codes, FOCS 1999.
-
I. Kerenidis and R de Wolf, Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument, STOC 2003 / JCSS 2004.
-
Progress and references.
-
First week: Organizational. 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]. For more details see excellent textbooks [4] (undergraduate level) and [5] (a little bit advanced), or come to our specialized courses like this. For an extensive 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 computations: [2, Ch. 4.3] (for an in-depth treatment see [4,5]). For doubly stochastic matrices,
Birkhoff-von Neumann theorem and much more see e.g. [7]. 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]. The same applies to Dirak's notation.
-
Second week: Completeness results: [2, Sec. 8.1] (exact realization) and [2, Sec. 8.2, 8.3] (approximate realization). 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]. Hidden Subgroup Problem (will be thoroughly discussed later in the course). Simon's algorithm: [3, Ch. 6.5]. $BQP\subset PP$: see [1, Ch. 4.5.5] for a slightly weaker result. Grover's search algorithm: [3, Ch. 8.1].
-
Third week: Grover's search algorithm cntd. The reduction of factoring to order-finding goes back to Miller (1975); our exposition is close to [2, Ch. 13.3].
Continued fractions: [3, Thm. 7.1.7]. 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$ 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: Shor's algorithm cntd. 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 in the non-Abelian case (the application
to Graph Isomorphism seems to be a part of folklore). To the best of my knowledge, this Zoo of Quantum Algorithms is a comprehensive list, including more
minor algorithms we do not do in this course. Our exposition of the hybrid method follows [3, Ch. 9.3]. Mega-theorem about polynomial equivalence of
various complexity measures for total functions can be found (in bits and pieces) in the survey [9].
- Fifth week: The proof of mega-theorem: see e.g. Theorems 10, 11, 2, 7, 17 and 18 in [9]. You can also check out our lecture notes (although I re-arranged a few things this year).
A good survey on the sensitivity vs. block sensitivity (written by former UC students) is [10], and a good survey on the approximate polynomial degree is [11]. Applications of the block sensitivity bound and the approximate degree bound: [3, Ch. 9.6.1, 9.5.1]. The
breakthrough on approximate polynomial degree of the AND-OR function was achieved independently in [12] and [13]. The paper [14] exploits relatively recent pointer functions technique for solving more open problems in the area; in particular it gives a
super-quadratic separation between the opposite sides of the spectrum in our mega-theorem. The standard textbook in classical communication complexity is [15] (see also [4-6] or check out my survey [16] for an exposition at a
very introductory level).
-
Sixth week: Classical communication complexity cntd. The quantum communication complexity was introduced in [17]. The relation between quantum decision tree and communication complexities was observed in [18]. The decomposition theorem for quantum communication protocols also appeared in [17], and it was further refined in [19,20]. Lower bound in terms of the spectral norm of the communication matrix is from [19].
Lower bounds for block-composed functions with the outer function symmetric (statement) [20,21].
- Seventh week: Approximate trace norm was introduced in [20], and the same paper proved tight
lower bounds for symmetric predicates. The 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, the depolarizing channel noise model (an excellent overview of other noise models can be found
in [1, Ch. 8.3]), tracing out (= partial measurement), 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
complete proof of the most non-trivial equivalence we mentioned in class. Trace distance: [1, Ch.
9.2.1]. Superoperators do not increase trace distance: [1, Theorem 9.2]. Projective measurements: [3,
Ch. 3.4]. An excellent overview of various noise models (some of them quite sophisticated) can be
found in [1, Ch. 8.3]. Classical error-correction (concept).
-
Eighth week: guest lecturers. Drucker: quantum proofs for classical theorems: [22]. Using quantum
algorithms to construct polynomials. Jackson's theorem and the approach via quantum estimation [23]; nontrivial
approximating polynomials for functions with sub-quadratic-size De Morgan formulas (without proof) [24,25].
Using quantum info-theoretic limitations to prove classical results. Lower bounds on the number of qubits
required in "quantum random-access codes" [26] and their application to prove exponential lower bounds on
length of 2-query (classical) Locally Decodable Codes [27]. Chong: Quantum Computing is Getting Real:
Architecture, PL, and OS roles in Closing the Gap between Quantum Algorithms and Machines.
- Ninth week: Three qubit bit/phase flip codes are in [1, Ch. 10.1], and the Shor code is in [1, Ch.
10.2]. Unitary equivalence for mixed states: [1, Theorem 2.6]. Unitary equivalence for operator-sum
representations: [1, Theorem 8.2]. Criterium of quantum recovery [1, Theorem 10.1].