CS 259Q — Quantum Computing Projects — Fall 2012
How it works: (1) choose a topic, either from the list below, or from something else
that interests you (in the latter case, check with Luca that the topic and the papers
that you want to read are appropriate); (2) understand the papers on the topic; (3) write
a short report; (4) schedule, and deliver, a 30-minute presentation during finals week.
The report should contain a summary of the results and motivations, and details about
one of the key proofs in the paper.
Lower bounds
There is a quantum algorithm that finds collisions in a length-decreasing
function with n input bits in time exp(n/3), and there is an exponential lower bound.
-
A. Ambainis
Quantum lower bounds by quantum arguments
Journal of Computer and System Sciences, 64(4):750-767, June 2002.
- Scott Aaronson, Yaoyun Shi
Quantum lower bounds for the collision and the element distinctness problems.
J. ACM 51(4): 595-605 (2004)
Adiabatic algorithms
- Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev: Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. SIAM J. Comput. 37(1): 166-194 (2007)
- Wim van Dam, Michele Mosca, Umesh V. Vazirani: How Powerful is Adiabatic Quantum Computation?. FOCS 2001: 279-287
Graph isomorphism
- Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen: Limitations of quantum coset states for graph isomorphism. J. ACM 57(6): 34 (2010)
- Cristopher Moore, Alexander Russell, Piotr Sniady: On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism. SIAM J. Comput. 39(6): 2377-2396 (2010)
Quantum cryptography
(Mark cannot pick this project!)
- Dan Boneh, Mark Zhandry: Quantum-Secure Message Authentication Codes. Electronic Colloquium on Computational Complexity (ECCC) 19: 136 (2012)
- Lectures 5,7,8 and 14 here gives some background on pseudorandom functions and MACs
Quantum money
- Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan A. Kelner, Andrew Lutomirski: Quantum money. Commun. ACM 55(8): 84-92 (2012)
- Scott Aaronson, Paul Christiano: Quantum money from hidden subspaces. STOC 2012: 41-60