CMSC 384101: Quantum Computing
Course description
Spring09: Tuesday, Thursday 1:30pm2:50pm (Ry 276)

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

Questions for selfstudy (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:
 Every permutation of the Boolean cube can be realized as an (exponentially long in general)
superposition of permutations acting on two (or 100) bits.
 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!).

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

Implement the operator $U_a: s> \mapsto s a mod N>$.

Implement the Quantum Fourier Transform over a cyclic group.

Hidden Subgroup Problem for arbitrary abelian groups.

[2]

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)$.

Explain where and why the proof of the result $D(F)\leq O(Q_2(F))^6$ breaks down for
partial functions.

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
blackbox 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. 738760, 2004.

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

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

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. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (October 17  19, 2004). FOCS. IEEE Computer Society, Washington, DC, 2231.

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

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

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