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]. If you are interested in more details, see the excellent textbook [4] or register for one of our specialized courses like this. 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 computations: [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]. The same applies to Dirac's notation. Mathematics and physics of Pauli matrices are extensively discussed in the Wikipedia article.

Second week: Hadamard gate. Completeness result for exact reealization: [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]. Hidden Subgroup Problem will be thoroughly discussed later in the course, for now see [7] (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. Grover's search algorithm, an overview: [3, Ch. 8.1].

Third week: guest lecturer (Prof. Fred Chong)

Fourth 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] but the best shot at tedious technical details (like "(-1) is rare" lemma and the continuous fraction algorithm) is [1, Appendix 4]. 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].

Fifth 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]; as I already said, [7] 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, along with references, can be found (in bits and pieces) in the survey [8], see in particular Theorems 10, 11, 2, 7, 17 and 18.

Sixth week: Mega-theorem cntd. Approximate degree of AND-OR tree (without proof): [9,10]. The paper [11] exploits 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 solution of the sensitivity conjecture: [12]. The standard textbook in classical communication complexity is [13] (see also [4-5] or check out my survey [14] for an exposition at a highly introductory level). Deterministic communication complexity and the rank lower bound [13, Ch. 1.4].

Seventh week: probabilistic communication complexity, Public coins vs. private coins [13, Ch. 3.3]. Rabin's protocol for the equality function [13, Example 3.5]. The quantum communication complexity was introduced in [15]. The relation between quantum decision tree and communication complexities was observed in [16]. The decomposition theorem for quantum communication protocols also appeared in [15], and it was further refined in [17,18]. Lower bound in terms of the spectral norm of the communication matrix is from [17]. Lower bounds for block-composed functions with the outer function symmetric (sketch) [18,19]. For trace norm (as well as many others) see [20].

Eighth week: 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 [19]. 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, 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 most non-trivial equivalence we sketched 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]. Measurements with the outcome recorded on a separate quantum worksheet are called measuring operators in [2, Ch. 12].

Ninth week: Unitary equivalence for mixed states: [1, Theorem 2.6]. Unitary equivalence for operator-sum representations: [1, Theorem 8.2]. Classical error-correction (concept). 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 [1, Theorem 10.1] and the additional fact about linearity of errors is [1, Theorem 10.2].

Tenth week (short): Stabilizer codes [1, Ch. 10.5]. About QMA (including the protocol for group non-membership): [21].