
Office hours. By appointment.

Homeworks
Assignment #1, due May 9.
Assignment #2, due May 23.
Assignment #3, due June 5.

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]. 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.

R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, Cambridge University Press, 1997.

C. Lomont, The Hidden Subgroup Problem  Review and Open Problems, 2004.

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.

S. Laplante, T. Lee, M. Szegedy. The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity, 15(2): 163196 (2006).

A. Ambainis, A. M. Childs, B. Reichardt, R. Spalek, S. Zhang. Any ANDOR Formula of Size N can be Evaluated in time N1/2+o(1) on a Quantum Computer. FOCS 2007: 363372.

A. Ambainis, Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing, 37(1): 210239 (2007).

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.

S. Aaronson and A. Ambainis, Quantum Search of Spatial Regions, Theory of Computing, 1:4779, 2005.

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, 2008.

Progress and references.

First week: A crash course in computational complexity that should be sufficient for our purposes can be found in [2, Part 1] or [1, Ch. 3.13.2]. For more detailed treatment see excellent textbooks [4] (undergraduate level) and [5] (a little bit advanced). 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]. Matrix form of circuit computations: [3, Ch. 1.4]. Probabilistic computations: [2, Ch. 4.3] (as always, for an indepth treatment see [4,5]). For doubly stochastic matrices,
Birkhoffvon Neumann theorem (and much more) see e.g. [6]. Rudimentary notation from linear algebra, including Dirac's notation can be found in any of our textbooks; I particularly recommend [1, Ch. 2.1].

Second week: Universal (aka complete) bases: [2, Ch, 8.2] or [1, Ch. 4.5]. Equivalence of universal bases: [2, Cor. 8.5.1]. Discussion of probabilistic vs. quantum: [3, Ch. 6.1].
Deutsch algorithm: [3, Ch. 6.3]. Our exposition of DeutschJozsa and Simon's algorithms closely follows the one given in [3, Ch. 6.3] and [3, Ch. 6.4]. We will thoroughly discuss
the Hidden Subgroup Problem later, but if you are already curious, you can check out [7]. $BQP\subspace PP$.

Third week: $BQP\subset PP$ cntd.; see [1, Ch. 4.5.5] for a proof of a slightly weaker result. Grover's search algorithm: [3, Ch. 8.1]. 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]. Eigenvalue estimation problem and construction of the operator $cU^x$ (we finally decided to call it ShorU) [3, Ch 7.2 ]. Quantum Fourier Transform and its inverse [3, Ch 7.1].

Fourth week: Shor's factoring algorithm cntd. Our exposition of the eigenvalue estimation includes elements of phase estimation [3, Ch. 7.1]; we did not discuss the latter problem separately. And the exposition in [3, Ch. 7.3] also includes an efficient realization of $QFT_{2^h}$ that we left as an exercise in class. Finally, the analytical expression for the error can be found in [3, Ch. 7.1.1]. Discrete Logarithm: [3, Ch. 7.4] (note, however, that we did not use the fancy notation with $\widetilde$). For the Hidden Subgroup Problem in Abelian groups, I recommend [2, Ch. 13.8], and [7] is a good survey on the nonAbelian case. Our exposition of the hybrid method follows [3, Chp. 9.3] (although, as in many other cases, we somewhat rearranged the material). Megatheorem about polynomial equivalence of various complexity measures for total functions.

Fifth week: The proof of megatheorem cntd. It can be found e.g. (in pieces) in the survey [8]: see theorems 10, 11, 2, 7, 17 and 18 there. A good survey on the sensitivity vs. block sensitivity is [9], and a good survey on the approximate polynomial degree is [10]. The recent breakthrough (approximate polynomial degree of the tribes function) was achieved independently in [11] and [12]. Ambainis's adversary method (we only did a sketch without proof): [3, Ch. 9.7 and A5]. For the relations between quantum query complexity and classical formula size see [13,14]. Ambainis's quantum walk (sketch): [15].

Sixth week: Ambainis's quantum walk cntd. The standard textbook in classical communication complexity is [16] (or check out my survey [17] at a very introductory level). The quantum communication complexity was introduced in [18]. The relation between quantum decision tree and communication complexities was observed in [19], and the improvement of the upper bound for DISJOINTNESS is in [20]. The decomposition theorem for quantum communication protocols also appeared in [18], and it was further refined in [21,22]. The discrepancy method is the standard tool in communication complexity (not only in quantum!), see again [18, 21] for examples. Lower bound in terms of the spectral norm of the communication matrix is from [21].

Seventh week: Approximate trace norm was introduced in [22], and the same paper proved tight lower bounds for symmetric predicates. The proof based on generalized discrepancy was given in [23]. Quantum Probability: [3, Ch. 3.5] or [2, Ch. 10]. An excellent overview of various noise models (some of them are quite sophisticated) can be found in [1, Ch. 8.3]. The axiomatic definition of physically realizable operators (aka superoperatotrs) is in [1, Ch. 8.2.4]; note that they consider a slightly more general case when the trace is allowed to decrease. Operatorsum representation: [1, Ch. 8.2.3.]. For another account see [2, Ch, 11.1]; in particular, [2, Problems 11.1, 11.2] are precisely the two parts of our theorem on different characterizations of superoperators. [1, Theorem 8.1] provides a complete proof of the part that we sketched in class.

Eighth week: Trace distance [1, Ch. 9.2.1]. Superoperators do not increase trace distance [1, Theorem 9.2]. No cloning theorem: [1, Box 12.1]. Three qubit bit/phase flip codes are in [1, Ch. 10.1], and the Shor code is in [1, Ch. 10.2]. General theory of quantum errorcorrection: [1, Ch. 10.3]; again, in class we considered only the tracepreserving case. 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].

Ninth week: Criterium of quantum recovery cntd. Stabilizer codes [1, Ch. 10.5]. Errorcorrection conditions for stabilizer codes [1, Theorem 10.8]. Quantum teleportation [1, Ch. 1.3.7]. Superdense coding [1, Ch. 2.3]. What we did not have time to do and left for another course: Shannon and von Neumann entropies [1, Ch. 11].

Tenth week (short): projects. Charles Forgy: "A Summary of Current Implementation of Adiabatic Quantum Computing" and Young Kun Ko: "Extended Formulations".