CMSC 384101: Quantum Computing
Course description
Winter 18: Tuesday, Thursday 9:30am10: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 [13], 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, SpringerVerlag, 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):2143, 2002.

P. Hatamii, R. Kulkarni and D. Pankratov. Variations on the Sensitivity Conjecture, Theory of Computing Library, Graduate Surveys Number 4 (2011) pp. 127.

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 MarkovBernstein Inequalities, 2013.

A. Sherstov, Approximating the ANDOR 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 145159.

A. Sherstov,
The pattern matrix method for lower bounds on quantum communication, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, 8594.

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 2Query 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.13.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 indepth treatment see [4,5]). For doubly stochastic matrices,
Birkhoffvon 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 DeutschJozsa 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 orderfinding 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 $cU$ and $cU^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 nonAbelian 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]. Megatheorem 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 megatheorem: see e.g. Theorems 10, 11, 2, 7, 17 and 18 in [9]. You can also check out our lecture notes (although I rearranged 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 ANDOR 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
superquadratic separation between the opposite sides of the spectrum in our megatheorem. The standard textbook in classical communication complexity is [15] (see also [46] 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 blockcomposed 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. Tracingout + unitary embedding: [2, Problem 11.1]. Operatorsum 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 nontrivial 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 errorcorrection (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 subquadraticsize De Morgan formulas (without proof) [24,25].
Using quantum infotheoretic limitations to prove classical results. Lower bounds on the number of qubits
required in "quantum randomaccess codes" [26] and their application to prove exponential lower bounds on
length of 2query (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.

Nineth 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 operatorsum representations: [1, Theorem 8.2]. Criterium of quantum recovery [1, Theorem 10.1].