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. 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 encouraged, but not required.

Your 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 must prepare your paper using LaTeX; you might use this template (illustrating a few basic commands) to get started. If necessary, you can draw quantum circuits using the Qcircuit package.

As part of this project, you will work with a partner to review drafts of
your individual papers. In addition to the paper itself, you will submit a *proposal*, a *rough draft*, and a *critique*, and will participate in a *draft review meeting* (see the schedule below). Your *proposal* should also be written in LaTeX, and should include a title, abstract, section headings, and short descriptions of the content of each section. Your *critique* should be written in the format of a referee report. It should briefly summarize the content of the paper, explain why the topic is interesting or important, address positive aspects of the paper as well as aspects that could be improved, and should list any typos and errors in the paper.

Please respect the following deadlines to facilitate the peer review process and to receive full credit. All submissions should be in pdf format, and should be e-mailed to all 3 instructors (amchilds@umd.edu, shelbyk@umd.edu, bclackey@umd.edu) for all assignments, and should be additionally e-mailed to your peer reviewer for the rough draft and critique assignments.

*October 13*: Proposal and outline of paper submitted to instructors.

[5%: based on timely completion and reasonable effort]*November 10*: Rough draft submitted to instructors and peer reviewer.

[5%: based on timely completion and reasonable effort]*November 14*: Critique of partner's draft submitted to instructors and peer reviewer.

[5%: based on timely completion and reasonable effort]*November 15-22*: Meet with partner and an instructors to discuss both partners' rough drafts.

[5%: based on timely completion and reasonable effort]*December 8*: Final draft submitted to instructors.

[80%: 40% for scientific content, 40% for clarity of exposition]

The following is a list of possible project topics, organized by subject, with a link to a representative reference for each. Though long, this list is far from exhaustive. You are welcome to choose a topic not on this list.

We have provided a brief description of each topic to give you a very rough idea what it is about, and we have listed some references to get you started. Often the choice of reference is somewhat arbitrary, so you should only treat the given references as a possible starting point. You should consult other related papers to form a more complete picture of the topic. Please do not hesitate to ask for help finding additional references on some topic.

Many of these references are links to published articles that may not be accessible from outside the university. Let us know if you have difficulty accessing any of these references.

If a topic uses mathematical concepts that go beyond the typical scope of the course, we try to make a note of it in the topic description.

- Quantum circuits
**The Solovay-Kitaev algorithm**. This algorithm provides and efficient method to approximate any unitary with gates from a specified (universal) gate set, and therefore allows conversion between universal gate sets. Uses some concepts from group theory, specifically facts regarding the Lie group SU(*d*). (Dawson and Nielsen; Trung, Van Meter, Horsman)**Exact circuit synthesis**. Characterizes when unitary operations can be implemented exactly using a specific gate set, and gives an algorithm for finding such an implementation. Uses concepts from algebraic number theory. (Giles and Selinger; Giles and Selinger)**Repeat-until-success**. A randomized method for approximate gate synthesis. Uses some algebraic number theory. (Paetznick, Svore; Bocharov, Roetteler, Svore)

- Quantum algorithms
**Algorithm for decomposing Abelian groups**. Decomposing an Abelian group into cyclic subgroups is a prerequisite for applying Shor's algorithm. Uses only elementary group theory. (Cheung, Mosca; Zhang)**Algorithms for solvable groups**. This topic concerns quantum algorithms for computing the order of an element, and related problems such as group membership and equality of subgroups, for solvable groups. Nontrivial but standard techniques from group theory are employed. (Watrous; Ivanyos, Magniez, Santha)**Query complexity of the HSP**. The hidden subgroup problem is a generalization of the period-finding problem solved by Shor's algorithm. This problem can be solved with only polynomially many quantum queries (though efficient quantum algorithms remain elusive for many groups). (Ettinger, Høyer, Knill; Ettinger, Høyer)**The Kuperberg sieve**. A subexponential algorithm to solve the hidden subgroup problem for dihedral groups. Use only a little group theory. (Kuperberg; Regev)**The hidden shift problem**. In the hidden shift problem, we are given functions*f*and*g*with the promise that*f*(*x*) =*g*(*x*+*s*), and would like to find*s*. While this problem seems hard in general, for certain groups and functions solutions are known. Uses some group theory and number theory. (van Dam, Hallgren, Ip; Friedl, Ivanyos, Magniez, Santha, Sen)**Solving Pell's equation**. Generalizations of Shor's algorithm lead to efficient quantum algorithms for a variety of hard computational problems in algebraic number theory. Uses some sophisticated ideas from rings and fields. (Hallgren; Eisenträger, Hallgren, Kitaev, Song; Biasse, Song)**Algorithms for graph properties**. This topic concerns upper and lower bounds on the complexity of computing certain graph or network flow properties in terms of number of queries to the adjacency matrix of a graph. Uses some graph terminology but no advanced mathematical concepts. (Dürr, Heiligman, Høyer, Mhalla; Ambainis, Špalek; Dörn).**Quantum walk on the line**. Random walks provide a framework for analyzing and developing randomized algorithms. This topic considers a quantum analog of a random walk and studies its behavior. Concepts from quantum mechanics are used heavily. (Ambainis, Bach, Nayak, Vishwanath, Watrous)**Exponential speedup by quantum walk**. This is an example of a problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. (Childs, Cleve, Deotto, Farhi, Gutmann, Spielman)**Element distinctness**. There is a quantum walk algorithm that optimally solves the problem of finding two inputs to a black-box function that map to the same output. This idea was subsequently developed into a broad framework for solving search problems. (Ambainis; Magniez, Santha, Szegedy)**Evaluating game trees**. There is a quantum walk algorithm that uses scattering theory to optimally evaluate a balanced binary NAND tree. Subsequent work gave an optimal algorithm to evaluate any Boolean formula on a black-box input. (Farhi, Goldstone, Gutmann; Ambainis, Childs, Reichardt, Špalek, Zhang)**Span programs**. Span programs are an alternate (algebraic) model of computation that in the quantum setting is equivalent to query complexity. They can be used to design new quantum algorithms: citations here provide some examples for graph problems. (Reichardt; Belovs, Reichardt; Gavinsky, Ito; Āriņš)**Learning graphs**. Learning graphs are a heuristic for designing span programs that often give good algorithms. These citations focus on using learning graphs to design quantum algorithms for some simple graph theory problems. (Belovs; Zhu; Lee, Magniez, Santha)**Quantum oracle interrogation**. Examines how many quantum queries to a black-box function are necessary to learn the entire function. (van Dam)**Ordered search**. Quantum computers can achieve a constant-factor speedup over classical binary search for the problem of searching an ordered list (although the best possible constant remains unknown). (Farhi, Goldstone, Gutman, Sipser; Hoyer, Neerbek, Shi; Childs, Landahl, Parrilo)**Quantum adiabatic optimization**. Uses the quantum adiabatic theorem as a method for preparing ground states, thereby solving optimization problems. There has been considerable interest in this approach, although its performance remains difficult to analyze. (Farhi, Goldstone, Gutmann, Sipser)**Approximating the Jones polynomial**. The Jones polynomial is a knot invariant which is #P-hard to evaluate in general. Nevertheless, there is a quantum algorithm to additively approximate the Jones polynomial at roots of unity. Uses advanced notions from knot theory and representations of the braid group. (Aharanov, Jones, Landau; Kuperberg)**Simulating Hamiltonian dynamics**. Quantum algorithms to simulate the time evolution of quantum mechanical systems. (Berry, Ahokas, Cleve, Sanders; Berry, Childs, Cleve, Kothari, Somma)**Linear systems**. This quantum algorithm produces a quantum state proportional to the solution of a (well-conditioned) system of linear equations. Ongoing work investigates possible applications of this idea to problems in scientific computing and machine learning. (Harrow, Hassidim, Lloyd; Aaronson; Clader, Jacobs, Sprouse)**Simulating quantum field theories**. A quantum algorithm for computing the scattering behavior of a scalar field theory with a quartic interaction. Uses concepts from quantum field theory. (Jordan, Lee, Preskill; Jordan, Lee, Preskill)**Quantum approximate optimization algorithm**. Quantum algorithm to find solutions to combinatorial optimization problems, such as SAT, that satisfy many (but not necessarily all) constraints. (Farhi, Goldstone, Gutmann; Lin, Zhu)**Superquadratic quantum query separations**. Constructs total functions with large gaps between their classical and quantum query complexities, refuting a longstanding conjecture. A flurry of recent work has used related ideas to separate various complexity measures. (Aaronson, Ben-David, Kothari)**Quantum principal component analysis**. Compare two quantum algorithms for principal component analysis: one uses phase estimation, whereas the other describes how to evolve according to a Hamiltonian proportional to the density matrix of a quantum state. (Lloyd, Mohseni, Rebentrost; Daskin)- Or find another quantum algorithm that interests you at the Quantum Algorithm Zoo

- Lower bounds on quantum query complexity
**Quantum adversary method**. Lower bound method based on a measure of progress that can be made with each query, generalizing the search lower bound presented in class. More recent work shows that (an extension of) this method can always give optimal bounds due to a duality with span programs (see above). Uses semidefinite programming. (Ambainis)**Polynomial method**. Uses a connection between quantum query algorithms and polynomials to establish lower bounds on query complexity. (Beals, Buhrman, Cleve, Mosca, de Wolf)**Quantum lower bound for the collision problem**. Applies the polynomial method to the problem of determining whether a function is 1-to-1 or 2-to-1. (Aaronson, Shi)**Quantum query complexity of symmetric functions**. Quantum algorithms cannot give a large advantage for problems with certain symmetries. (Aaronson, Ambainis)**Quantum query complexity of state conversion**. State conversion is the problem of using an oracle to convert one quantum state to another that depends on the oracle. This framework provides a more general perspective on the quantum adversary method. Uses semidefinite programming. (Lee, Mittal, Reichardt, Spalek, Szegedy)

- Quantum computational complexity
**QMA-completeness of the local Hamiltonian problem**. A quantum analog of the Cook-Levin theorem (SAT is NP-complete). Can also be seen as characterizing the difficulty of finding ground states of quantum systems. (Kempe, Kitaev, Regev)**Strong error reduction for QMA**. Method for reducing the error in a QMA proof system. (Marriott, Watrous)**Quantum proofs for group non-membership**. Studies the relative power of classical and quantum proofs. (Watrous)**Quantum satisfiability**. Shows that a quantum analog of 2-SAT can be solved efficiently classically, and gives evidence for the hardness of quantum*k*-SAT with larger*k*. (Bravyi; Gosset, Nagaj)**Quantum communication complexity**. Given an input shared between two parties, how much information must they exchange to compute some desired function (de Wolf)**Quantum computation with postselection**. Studies the computational power of forcing a measurement to have a desired outcome. Gives an example of a classical problem for which quantum ideas give a simpler proof. (Aaronson)**QIP = PSPACE**. Characterizes the power of quantum interactive proofs (equivalent to classical interactive proofs, or equivalently, polynomial-space computations). (Jain, Ji, Upadhyay, Watrous)

- Quantum cryptography
**Private quantum channels**. Quantum analog of the one-time pad: a method for sending quantum states securely using a shared, private classical key. Uses quantum information theory, but no cryptographic knowledge is needed. (Ambainis, Mosca, Tapp, de Wolf; Bouda, Ziman; Ambainis, Bouda, Winter)**Quantum secret sharing**. Method for splitting a quantum state into parts such that only a sufficiently large subset of the parties can reconstruct the state. (Cleve, Gottesman, Lo; Hillery, Bužek, Berthiaume; Gottesman)**Quantum data hiding**. These are protocols that embed information in a two-party quantum state such that Alice and Bob working on their parts independently can learn nothing about the information. (Terhal, DiVincenzo, Leung; DiVincenzo, Leung, Terhal; DiVincenzo, Hayden, Terhal)**Quantum key distribution**. Establishes unconditional security of key distribution using a quantum channel. Uses concepts from quantum error-correcting codes. (Shor, Preskill; Mayers)**Quantum digital signatures**. A quantum digital signature is a cryptographic protocol to authenticate a (classical) message using quantum states in such a way that forgery or repudiation violate a physical law. Some familiarity with cryptographic concepts is needed. (Gottesman, Chuang; Amiri, Wallden, Kent, Andersson; Amiri, Andersson)**Quantum money**. Quantum money is a cryptographic protocol similar to a digital signature: a "bank" produces quantum states that are easily validated using a key, but forging such states without the corresponding secret violates a physical law. Some familiarity with cryptographic concepts is needed. (Aaronson; Aaronson, Christiano; Pena, Faugère, Perret)**Blind quantum computation**. In blind quantum computation, Alice (the client) has limited quantum capabilities and so delegates a quantum computation to Bob (the server) in such a way that Bob learns nothing about the underlying computation. Protocols are formulated using the measurement-based model of quantum computing (see below). (Broadbent, Fitzsimons, Kashefi; Hayashi, Morimae; Herder)**Quantum Merkle puzzles**. This is a re-envisioning of one of the earliest public key cryptosystems, updating it for a world with quantum computers. Uses concepts from quantum query complexity. (Brassard, Høyer, Kalach, Kaplan, Laplante, Salvail)**Device-independent QKD**. Shows how to perform secure quantum key distribution with untrusted devices. (Vazirani, Vidick; Miller, Shi)**Quantum-secure message authentication codes**. Constructs message authentication codes that are secure against quantum computers. A working knowledge of cryptography is useful. (Boneh, Zhandry; Velema)**Quantum cryptanalysis of symmetric ciphers**. Application of basic quantum algorithms such as period finding and amplitude amplification to the cryptanalysis of block ciphers and their authentication modes. Heavy use of cryptography. (Kaplan, Leurent, Leverrier, Naya-Plasencia; Kaplan, Leurent, Leverrier, Naya-Plasencia)

- Quantum information theory and error correction
**Quantum random access codes**. One can encode classical bits into fewer qubits so that any chosen bit of the original string can be recovered with reasonable probability. (Ambainis, Nayak, Ta-Shma, Vazirani; Nayak)**Remote state preparation**. A resource theory approach to a variant of quantum teleportation where the sender knows the state to be sent. Asymptotically, a known qubit can be communicated with only one classical bit (and one bit of entanglement). (Bennett, Hayden, Leung, Shor, Winter)**Coherent classical communication**. A resource theory that generalizes dense coding and teleportation, leading to a universal picture of quantum protocols. (Harrow; Devetak, Harrow, Winter)**Entanglement-assisted classical communication with quantum channels**. Illustrates how prior entanglement can both increase the classical capacity of a quantum channel and simplify its analysis. (Bennett, Shor, Smolin, Thapliyal; Bennett, Shor, Smolin, Thapliyal; Holevo)**Private classical capacity of a quantum channel**. Explores the relationship between the capacity of a noisy quantum channel to send private classical information versus coherent quantum information. (Schumacher, Westmoreland; Devetak)**Superactivation of quantum capacity**. Surprisingly, there are zero-capacity channels that, when used together, have nonzero capacity. Recently it was observed that the number of times a channel must be used to produce positive capacity can be arbitrarily large. (Smith, Yard; Cubitt, Elkouss, Matthews, Ozols, Pérez-García, Strelchuk)**Superadditivity of the classical capacity of quantum channels**. Refutes a longstanding conjecture that entangled inputs do not increase the capacity of quantum channels to send classical information. (Hastings)**Topological/toric/surface codes**. Qubits can be protected by encoding them into nontrivial homology classes of a surface. Some familiarity with advanced algebra is helpful. (Freedman and Meyer; Bravyi and Kitaev; Fowler et al.)**Magic state distillation**. Certain gates can act efficiently on encoded qubits via "gate teleportation." This consumes a special "magic state" that can be accurately constructed by distilling noisy versions of the state. (Bravyi, Kitaev; Reichardt; Campbell, Browne; Meier, Eastin, Knill)**Universal computation by gauge-fixing**. Universal gate sets can be obtained by using syndrome measurement to switch between related codes. (Kribs, Laflamme, Poulin; Paetznick and Reichardt; Jones, Brooks, Harrington)**The threshold theorem**. Shows that arbitrarily long quantum computation can be performed on a noisy device with reasonable overhead, provided the noise level is below some threshold. No advanced concepts are required, but some aspects of the proof involve considerable case analysis. (Aharonov and Ben-Or; Knill, Laflamme, Zurek; Steane)**Decoherence-free subspaces and subsystems**. Certain error models such as collective decoherence allow for quantum information to be stored and manipulated in an error-free subspace. Some advanced physics and elements of representation theory are touched up in this topic. (Lidar and Whaley; Kempe, Bacon, Lidar, Whaley; Lidar)

- Alternative models of quantum computation
**Adiabatic quantum computation**. Motivated by the adiabatic optimization algorithm (see above), universal adiabatic computation is performed by constructing a Hamiltonian with an easily-prepared ground state, and slowly evolving to a Hamiltonian whose ground state encodes the desired computation. This is computationally equivalent to the circuit model. (Aharonov, van Dam, Kempe, Landau, Lloyd, Regev)**Measurement-based quantum computing**. This "one-way" quantum computer relies on building a large array of entangled qubits. Computations are performed by making adaptive one-qubit measurements on the array. (Raussendorf, Browne, Briegel; Broadbent, Kashefi)**Topological quantum computing**. Realizes quantum computing as braiding an fusion of quasi-particles with exotic statistics (anyons). Uses Lie groups, braid groups, some nontrivial representation theory (particularly for braid groups), and topological quantum field theory. (Kitaev; Freedman, Larsen, Wang)**Computation by quantum walk**. Shows that universal quantum computation can be encoded into transmission coefficients of a quantum walk scattered by a graph (see "Evaluating game trees" above). (Childs; Childs, Gosset, Webb)**Boson sampling**. The behavior of non-interacting bosons lead to distributions that can be easy to sample using quantum effects, but classically hard (given some computational assumptions). Second reference is the extended version of the first. Uses notions from complexity theory. (Aaronson, Arkhipov; Aaronson, Arkhipov)**One clean qubit model**. Investigates an experimentally-motivated model in which one has access to a single pure qubit and many qubits in the maximally mixed state. The second reference makes use of knot theory. (Knill, Laflamme; Shor, Jordan)

- Quantum tomography (Characterizing unknown quantum states and operations)
**Quantum process tomography**. General method for characterizing quantum processes. (Chuang, Nielsen)**Randomized benchmarking**. Method for characterizing errors in a gate set when state preparation and measurement errors are unknown. (Magesan, Gambetta, Emerson)**Quantum state tomography using de Finetti results**. Achieves accurate characterization of quantum states using random permutations of the set of states to be characterized. (Christandl, Renner)**Adaptive quantum state tomography**. Devises an adaptive protocol that improves the performance of state tomography. (Mahler, Rozema, Darabi, Ferrie, Blume-Kohout, Steinberg)