CMSC 38410-1: Quantum Computing

Course description

Winter11: Tuesday, Thursday 1:30pm-2:50pm (Ry 251)

Office hours. By appointment.

Lecture notes are available here. Any comments, corrections and suggestions are most welcome.

Projects. In order to get a letter grade for this course, you should learn something interesting that was only marginally touched in the class and prepare a short oral presentation on March 9. You can either choose from the list below (that will be expanded if needed) or, if you have your own suggestion, discuss it with me.
1. Every permutation of the Boolean cube can be realized as an (exponentially long in general) superposition of permutations acting on two (or 100) bits.
2. Every unitary transformation can be realized as an (exponentially long in general) superposition of unitary transformations acting on two qubits.
3. Polynomial time algorithm that, given $\sigma$ with the promise $|\sigma - k/r|\leq \frac 1{2r^2}$, finds $r$.
4. Implement the Quantum Fourier Transform over a cyclic group.
5. Hidden Subgroup Problem for arbitrary abelian groups.
6. Hidden Subgroup Problem for dihedral group and connections to cryptography.
7. Every polynomial $p(x)$ with $p(0)\in [0,1/3]$, $p(1)\in [2/3,1]$ and $p(x)\in [0,1]\ (x=2,\ldots,N)$ must have degree $\Omega(\sqrt N)$.
Literature. Most of the material pertained to this course can be found in the monographs [1-3]. References to more specific sources covering individual topics will be also 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. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
5. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
6. R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, Cambridge University Press, 1997.
7. C. Lomont, The Hidden Subgroup Problem - Review and Open Problems, 2004.
8. O. Regev, Quantum Computation and Lattice Problems, SIAM Journal on Computing, 33(3), pp. 738-760, 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. Y. Shi. Approximate polynomial degree of Boolean functions and its applications. Proceedings of the 4th International Congress of Chinese Mathematicians, 2007.
11. S. Laplante, T. Lee, M. Szegedy. The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity, 15(2): 163-196 (2006).
12. A. Ambainis, A. M. Childs, B. Reichardt, R. Spalek, S. Zhang. Any AND-OR Formula of Size N can be Evaluated in time N1/2+o(1) on a Quantum Computer. FOCS 2007: 363-372.
13. E. Kushilevitz and N.Nisan, Communication Complexity, Cambridge University Press, 1997.
14. A. Razborov, Communication Complexity, to appear in the International Mathematical Olympiad 50th Anniversary Book.
15. A.C. Yao, Quantum circuit complexity, Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993, pp. 352 - 361.
16. 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.
17. S. Aaronson and A. Ambainis, Quantum Search of Spatial Regions, Theory of Computing, 1:47-79, 2005.
18. I. Kremer, Quantum communication, Master's thesis, Hebrew University, Jerusalem 1995.
19. A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.
20. A. Sherstov, The pattern matrix method for lower bounds on quantum communication, 2008.

Progress and references.

First week (short): A crash course in computational complexity that should be sufficient for our purposes can be found in [2, Part 1] or [1, Ch. 3.1-3.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].

Second week: Matrix form of circuit computations: [3, Ch. 1.4]. Probabilistic computations: [2, Ch. 4.3] (as always, for an in-depth treatment see [4,5]). For doubly stochastic matrices, Birkhoff-von 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]. Universality of quantum computation (non-constructive version): [2, Thm. 8.1]. 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].

Third week: Our exposition of Deutsch-Jozsa 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]. [1, Ch. 4.5.5] proves that $BQP\subspace $PSPACE$; the proof is virtually the same as the one we did for $PP$. Grover's search algorithm: [3, Ch. 8.1]. The reduction of factoring to order-finding goes back to Miller (1975); our exposition is close to [2, Ch. 13.3].

Fourth week: Continued fractions: [3, Thm. 7.1.7]. Our exposition of Shor's factoring algorithm more or less follows [3, Ch. 7.2- 7.3], except that we significantly changed the order of the content. Analytical analysis of the error is 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 non-Abelian case.

Fifth week (short): The connection between the HSP for the dihedral group and lattice problems is from [8]. Quantum Probability: [3, Ch. 3.5] or [2, Ch. 10]. An excellent overview of various noise models can be found in [1, Ch. 8.3]. The official definition of physically realizable superoperators is in [1, Ch. 8.2.4] or [2, Ch, 11.1] (specifically, see Problem 11.5 there).

Sixth week: Trace distance: [1, Ch. 9.2.1] (and the fact that it is non-decreasing under superoperators is [1, Thm. 9.2]). Our exposition of the hybrid method followed [3, Chp. 9.3] (although, as in other cases, we somewhat re-arranged the material). The proof of our meta-theorem about polynomial equivalence of various complexity measures for total functions is scattered (almost everywhere densely) in [9] (Theorems 10, 11, 2 and 7 so far).

Seventh week (long): The meta-theorem cntd. ([9, Theorems 17 and 18]). A good survey on the approximate polynomial degree is [10]. Ambainis's adversary method: [3, Ch. 9.7 and A5]. For the relations between quantum query complexity and classical formula size see [11,12]. The standard textbook in classical communication complexity is [13] (or check out my popular survey [14]). The quantum communication complexity was introduced in [15]. The relation between quantum decision tree and communication complexities was observed in [16], and the improvement of the upper bound for DISJOINTNESS is in [17].

Eighth week (long): The decomposition theorem for quantum communication protocols also appeared in [15], and it was further refined in [18,19]. The discrepancy method is the standard tool in communication complexity (not only in quantum), see again [15, 18] for examples. Lower bound in terms of the spectral norm of the communication matrix is from [18]. Approximate trace norm was introduced in [19], and the same paper proved tight lower bounds for symmetric predicates. Another proof was given in [20]. Rudimentary things we did in quantum error-correction are well covered in any of our textbooks; [1] is the closest to the account I gave in class. An excellent overview of various noise models can be found in [1, Ch. 8.3]. Operator-sum representation is in [1, Ch. 8.2.3]. Three qubit bit/phase flip codes are in [1, Ch. 10.1], and the Shor code is in [1, Ch. 10.2].

Tenth week: Quantum error-correction conditions: [1, Theorem 10.1], and unitary transformation of operation elements is [1, Theorem 8.2] (these theorems are proved there in both directions). We did not have time to do general stabilizer codes properly, but I highly recommend to read about them e.g. in [1, Ch. 10.5]. Projects: Hidden Subgroup Problem for Arbitrary Abelian Subgroups (Orlova); Einselection, Envariance and Models of Decoherence (Reinglod); Physical Meaning of Off-Diagonal Elements in Density Matrices (Pelzer).