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.

Adiabatic algorithms

Graph isomorphism

Quantum cryptography

(Mark cannot pick this project!)

Quantum money