For the course project, you will work in a team of 2–3 students to learn about a topic of your choice from the quantum information literature and record a video presentation. Your goal should be to understand a new concept in quantum information by reading original sources, and then to communicate this concept clearly, at a level appropriate for students in CMSC 657. If you would like to do some original research as part of your project, this is very much encouraged, but it is not required.
By early October, you should select a team and write a project proposal that includes a one-paragraph summary of your topic, a timeline for exploring that topic, and a list of selected references. This should show that you have thought about your topic and have a clear picture of what you would like to learn about it. Before writing your proposal, you are encouraged to discuss possible topics with the course staff during office hours.
You should write a progress report in early November, showing that you have begun to explore the topic and have thought about how to present it. The progress report should include a refined version of your proposal (i.e., an updated summary, timeline, and references), followed by a draft outline of your plan for the presentation. This report should be no more than three pages in length.
Your final video presentation should be at most 20 minutes long. The details of the format are up to you. The most straightforward approach could be a voice-over-slides presentation, but you can include video of the presenters, animations, or other elements as you see fit. In addition, you should submit a report with a short abstract describing your topic, an overview of what you think went well in your project and what might have been improved, a description of what each team member contributed, and a final list of references. This report should also be at most three pages in length.
All video presentations will be made available to students in the course via Canvas after the project deadline. Outstanding presentations may be invited for posting on the QuICS YouTube channel, with the permission of all team members.
- Wednesday, October 11: Proposal (5% for timely completion and a clear plan)
- Wednesday, November 8: Progress report (5% for timely completion and evidence of progress)
- Wednesday, December 6: Final presentation (90%)
The proposal, progress report, and final project report should be submitted via Gradescope. The final video presentation should be uploaded at a link that will be provided closer to the deadline.
The final presentation grade will be based on the following criteria:
- Motivation: Did the presentation place its topic in context and explain why it is interesting?
- Clarity: Did the presentation provide a clear explanation of its topic?
- Visual communication: Did the slides or other visual elements communicate effectively?
- Appropriateness for target audience: Was the presentation suitable for CMSC 657 students from various backgrounds, without relying on specialized knowledge? Did it present material that went beyond the course? Did it include some technical detail?
- Pacing: Was the pace of the presentation neither too slow nor too fast?
- Teamwork: Did all group members contribute significantly?
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.
If your topic is related to material that is covered in the course, you should ensure that you explore aspects that go beyond the course content. This may require a discussion with the instructor, especially if the topic is being covered later in the course.
- 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.