For the course project, you should write an expository paper on a topic of your choice from the quantum information literature. Your goal should be to understand a new concept in quantum information by reading original sources, and then to communicate this concept clearly and concisely. You should aim to cover a topic from your own perspective, not just to summarize a single paper. Your target audience should be your fellow students in the course. If you would like to do some original research as part of your project, this is very much encouraged, but not required.
In early October, you should write a project proposal that includes a one-paragraph summary of your topic, a timeline for exploring it, and a list of selected references. This should show that you have thought about your topic and have a clear picture of what you plan to cover in your paper. Before writing your proposal, you are encouraged to discuss possible topics with the course staff during office hours.
You should also write a project progress report in early November. This should include a refined version of your proposal (including an updated timeline), followed by a partial draft of material you plan to include in the final paper, showing that you have made progress in exploring the topic. This report should be no more than five pages in length (not counting references).
Your final paper should be at most ten pages in length (not counting references), using at least 11-point fonts and at least 1-inch margins. You should prepare your paper using LaTeX; you might use this template (illustrating a few basic commands) to get started.
The following is a list of possible project topics. This list is far from complete, and is only intended as a starting point for you to explore your options. Some of these topics are broad, so you may want to focus on one particular aspect. You should feel free to choose a topic that is not on this list.
- Quantum circuits
- The Solovay-Kitaev theorem. Provides an efficient method to approximate any unitary operation with gates from a specified (universal) gate set, enabling efficient conversion between universal gate sets.
- Clifford+T circuit synthesis. This gate set (which is natural and commonly used for fault tolerance) allows circuits to be synthesized even more efficiently.
- Quantum algorithms
- The hidden subgroup problem. This framework generalizes the main idea behind Shor's algorithm. It been extensively studied but still contains many open questions.
- Quantum walk. Quantum analogs of Markov processes provide powerful tools for designing quantum algorithms.
- Formula evaluation. Quantum computers can evaluate Boolean formulas faster than is possible classically, generalizing Grover's quadratic speedup for computing the OR function.
- Quantum adiabatic optimization. The quantum adiabatic theorem can be used to prepare ground states and thereby solve optimization problems, though the advantage of this approach over classical optimization remaions unclear.
- Simulating Hamiltonian dynamics. The possibility of simulating quantum systems with quantum processors provided the original motivation for the idea of quantum computers and remains arguably their most compelling potential application.
- High-dimensional linear algebra. By encoding a high-dimensional vector as a quantum state, a quantum computer can quickly produce an encoding of the solution of a system of linear (or differential) equations.
- Or find another quantum algorithm that interests you at the Quantum Algorithm Zoo.
- Lower bounds on quantum query complexity
- Quantum adversary method. The adversary method lower bounds quantum query complexity by bounding a measure of progress that can be made with each query, generalizing the search lower bound presented in class.
- Polynomial method. A connection between quantum query algorithms and polynomials can be used to establish lower bounds on query complexity.
- Quantum computational complexity
- Quantum computational advantage. How can we verify that a device is capable of performing classically hard computations?
- Quantum interactive proofs. An interactive discussion with a prover can offer much more computational power than if the prover simply provides a proof. A celebrated result shows that quantum abilities provide the same power as in the classical case.
- Quantum satisfiability. While the local Hamiltonian problem provides one quantum analog of SAT, a variant of the problem that requires a solution to be in the ground space of every local term provides another analog with different complexity.
- Quantum communication complexity. Given an input shared between two parties, how much information must they exchange to compute some desired function?
- Quantum computation with postselection. What is the computational power of forcing a measurement to produce a given outcome?
- Quantum error correction and fault tolerance
- Threshold theorem. This result shows that arbitrarily long quantum computation can be performed on a noisy device with reasonable overhead, provided the noise level is below some threshold. We will only discuss this result briefly in class; the full proof is quite involved.
- Topological error correction/surface codes. Certain error correcting codes can encode quantum information in topological excitations called anyons, whose logical states can be manipulated via braiding operations. The instantiation of this idea in the so-called surface code is a leading candidate for fault tolerance in practice.
- Magic state distillation. Certain quantum gates can be performed by consuming a special "magic state" that can be accurately constructed by distilling noisy versions of the state. This distillation process is a key ingredient of some of the most efficient known approaches to fault tolerance.
- Quantum low-density parity check codes. Quantum LDPC codes have the potential to perform fault-tolerant computation with less overhead than the surface code, and have recently been extensively investigated.
- Quantum information theory
- Remote state preparation. How do the resources required to perform teleportation change when the state to be sent is known?
- Entanglement-assisted classical communication with quantum channels. The availability of prior entanglement can both increase the classical capacity of a quantum channel and simplify its analysis.
- Superadditivity of the classical capacity of quantum channels. Entangled input states can increase the capacity of quantum channels to send classical information.
- Superactivation of quantum capacity. Surprisingly, there are channels with no capacity to send quantum information that, when used together, have nonzero capacity.
- Quantum cryptography
- Device-independent QKD. A shared secret key can be established between parties who have never met, even in a situation where those parties' devices are untrusted.
- Merkle puzzles. An early approach to public-key cryptography shows how to agree on a shared secret with polynomial advantage against an adversary. How does this change when the honest parties and/or the adversary can perform quantum computation?
- Quantum money. Quantum money is a cryptographic primitive in which a bank produces quantum states that are easily validated using a key, but that are intractable to forge.
- Delegated quantum computation. How can a client with limited quantum abilities delegate a computation to an untrusted quantum server? This task varies depending on the abilities of the client and the desired properties of the protocol.
- Quantum homomorphic encryption. Homomorphic encryption allows parites to perform computations on encrypted data without having to decrypt it.