Introduction to quantum information processing (CMSC 858K, Fall 2017): Course project

Guidelines

Topics

• 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 non-Abelian HSPs 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, Boneh, Zhandry)
  • 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)

Web Accessibility