CMSC 38410-1: Quantum Computing

Course description

Spring09: Tuesday, Thursday 1:30pm-2:50pm (Ry 276)

Office hours. For the time being, just drop by when I am in.

Questions for self-study (aka "homeworks"). There will be two sets. They will not be graded, but we will do in the class all problems for which we'll have at least one explicit request. For more challenging exercises see the section Projects just below.
Assignment #1.
Assignment #2.

Projects. In order to get credit for this course, you should sign up for one of these and present it in the class, either in full or (most likely) partly. All volunteers taking this course as auditors are mostly welcome and encouraged to sign up as well. The current list of opportunities includes:
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 (qualifies for a team of two!).
3. Polynomial time algorithm that, given $\sigma$ with the promise $|\sigma - k/r|\leq \frac 1{2r^2}$, finds $r$. A solution that does not use continuous fractions (even -- in my sole judgement -- implicitly) qualifies for a credit in all other advanced courses I will be teaching (more importantly, it will be an extremely interesting research contribution in itself).
4. Implement the operator $U_a: |s> \mapsto |s a mod N>$.
5. Implement the Quantum Fourier Transform over a cyclic group.
6. Hidden Subgroup Problem for arbitrary abelian groups.
7. [2]
8. 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)$.
9. Explain where and why the proof of the result $D(F)\leq O(Q_2(F))^6$ breaks down for partial functions.
10. Complete the analysis of Ambainis's quantum walk algorithm for distinctness [7].

Further literature. [1] is an excellent survey on the Hidden Subgroup Problem, containing many interesting open problems. [2] gives the application of the HSP for dihedral groups to some lattice problems arising in cryptography. [3] is the best source I am aware of covering black-box models (both quantum and classical). [4] is also very good, but it specifically concentrates on the quantum part. For the relations between formula size and quantum query complexity see e.g. [5,6] and the literature cited therein. [8] is a comprehensive source on the classical communication complexity. Lower bounds for the quantum communication complexity of symmetric predicates are in [9]. [10] is an excellent survey on (advanced) quantum complexity theory.

References

C. Lomont, The Hidden Subgroup Problem - Review and Open Problems, 2004, available at arXiv.

O. Regev, Quantum Computation and Lattice Problems, SIAM Journal on Computing, 33(3), pp. 738-760, 2004.

H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science, 288(1):21-43, 2002.

A. Ambainis 2004. Quantum search algorithms. SIGACT News 35, 2 (Jun. 2004), 22-35.

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

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.

A. Ambainis, Quantum Walk Algorithm for Element Distinctness. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (October 17 - 19, 2004). FOCS. IEEE Computer Society, Washington, DC, 22-31.

E. Kushilevitz, N. Nisan, Communication Complexity, 1996.

A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159.

J. Watrous, Quantum Computational Complexity, 2008, available at arXiv.