2-3 people group projects. You may choose to do a literature review project or (more exciting) original research. For literature review, you’d read a few papers around a topic, understand the connection of this topic to the general field of quantum computing as well as the of various works under this topic. The final outcome would be a survey paper including interesting open problems. For research project, identify clearly a problem (e.g., designing/improving an algorithm for a specific task) and let your creativity guide you while maintaining reasonable precision! You are not requried to completely solve a problem (big congrats if you do!).
- Proposal: 1-2 pages consisting of 1) the topic, background, context, motivation; 2) brief summary of the relevant works and core papers to be studied; and 3) a goal you intend to achieve and a plan.
- Mid-term report: ~5 pages. After more reading and group discussion, your mid-term report should have a polished and expanded version of your proposal. You also need to demonstrate the progress you’ve made since the proposal.
- Oral presentation: Each group will have about 20mins to present your project, demonstrating both breath and depth: you should aim for a clear introdution of your topic with sufficient background and motivation that would interest the audience; and then you may choose to explain 1-2 techincal ideas in a little detail. Every group member needs to participate, and your group will be graded by other fellow students. You may give your the presentaion on board or with slides.
- Final report: ~10 pages. This should resemble a real research paper: a short abstract; 2) an introduction that motivates the topic/problem and gives an overview of the entire paper; 3) details including proper preliminary materials (e.g., notations & defintions), explaning some main technical results; and finally 4) further discussion and open questions.
- Report format: single-column, single-space (between lines) format on letter-size paper. LaTeX and BibTeX are highly recommended. Here is a simple [TeX PDF] template. You may follow a suitable 2017 ACM Article Template (e.g., ACM Small format). Many LaTeX and MS word templates are availabe there.
- Week 1 & 2: forming groups.
- Week 3 & 4: meeting and discussing project ideas.
- April 27: proposal due.
- May 18: mid-term report due.
- Week 10: in-class presentations.
- June 15: final report due.
- General survey [CvD10] Quantum algorithms for algebraic problems by Andrew M. Childs, Wim van Dam.
- Non-abelian Hidden subgroup probelm A tough case for HSP, but connected with many interesting problems, e.g., graph isomorphism, and (unique) shortest vector problem critical in lattice-based crypto.
- (Generalized) hidden shift problem
- High dimensional continuous abelian HSP. nice generalization and
new formalization of HSP on continuous groups with applications in
sovling basic number theoretic problems and breaking some lattice crypto.
- [EHKS14] A Quantum Algorithm for Computing the Unit Group of an Arbitrary Degree Number Field by Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev and Fang Song.
- [BS16] Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields by J. Biasse and F. Song.
- Quantum random walk. An extension of classical random walk to
the quantum setting. It has become a framework for quantum
algorithm design that usually achieves polynomial speedup.
- Survey papers
- [HK16] Efficient quantum walk on the grid with multiple marked elements by Peter Hoyer, Mojtaba Komeili.
- Continuous-time quantum walk. [C08] Universal computation by quantum walk by A. M. Childs.
Quantum simulation related algorithms
Original motivation of quantum computers. They are already meaningful and possible on a “small” quantum computer with say 50 clean qubits. Thesre algorithms have wide applications such as machine learning.
- [HHL09] Quantum algorithm for solving linear systems of equations by Aram W. Harrow, Avinatan Hassidim, Seth Lloyd.
- [CKS16] Quantum linear systems algorithm with exponentially improved dependence on precision by Andrew M. Childs, Robin Kothari, and Rolando D. Somma.
- [BCK15] Hamiltonian simulation with nearly optimal dependence on all parameters by Dominic W. Berry, Andrew M. Childs, and Robin Kothari.
- Application in quantum machine learning. ML, of course… but be critical about what you see.
- Quantum supremacy. Recent advances in physical implementation
has brought up the hot topic on demonstrating: on a small
(special-purpose) quantum device, is there a clear quantum speedup for
some task, motivated by the goal of overturning the Extended
Church-Turing Thesis as confidently as possible.
- [AC16] Complexity-Theoretic Foundations of Quantum Supremacy Experiments by S. Aaronson and L. Chen.
Quantum Information Theory
- Broad survey on Quantum entanglement [HHHH08] Quantum entanglement by R. Horodecki, P. Horodecki, M. Horodecki, K. Horodecki.
- Quantum error correcting. We only scratch the surface of QECC in class. Project idea: a summary of the genearl error correcting theory and the stablizer formalism, and discussing a particular code (e.g. surface code).
- Thoery of quantum fault-tolerant computing. Fault-tolerance is critical for physical implementation of a quantum computer. Project idea: a gerenal overview and explaining some of the key compenents in detail would be suitable for a course project.
- Quantum Shannon theory. It deals with communicating information via noisy channel. Many surprsing and distinct features in the quantum generaliztion.
- Quantum information and black holes.
Quantum Computational Complexity
There is a large body of research that explores abstractly the power and the limits of quantum computing.
- General survey [W09] Quantum Computational Complexity by J. Watrous.
- Quantum interactive proofs
- Non-local games. Introduced for the purpose of testing quantum theory, it turns out to be far more influential and connets to many areas such as interactive proofs, operator theory, cryptography, etc.
- Hamiltonian Complexity How difficult is it to determin the ground energy of a physical system?
Quantum Query & Communication Complexity
- [MW13] A Survey of Quantum Property Testing by Ashley Montanaro, Ronald de Wolf.
- [G01] Quantum Communication Complexity (A Survey) by Gilles Brassard.
- Separations of classical/quantum complexity
- [ATYY16] Exponential Separation of Quantum Communication and Classical Information by Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu.
- Query lower bound
- Polynomial method. [BBCMW98] Quantum Lower Bounds by Polynomials by R. Beals et al.
- Adversarial method. [A00] Quantum lower bounds by quantum arguments by Andris Ambainis.
- [HLS07] Negative weights make adversaries stronger P. Hoyer T. Lee, R. Spalek.
- [R09] Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function by Ben W. Reichardt.
Quantum and crypto
- Post-quantum crypto cope with quantum codebreakers
- [R04] Quantum Computation and Lattice Problems by Oded Regev.
- [Z12] How to Construct Quantum Random Functions by Mark Zhandry.
- [Z13] Quantum-Secure Message Authentication Codes by Dan Boneh and Mark Zhandry.
- [S14] A Note on Quantum Security for Post-Quantum Cryptography by F. Song.
- [HHS11] Classical Cryptographic Protocols in a Quantum World by Sean Hallgren, Adam Smith, Fang Song.
- [BDF+11] Random Oracles in a Quantum World, by Dan Boneh et al.
- [KLLNP16] Breaking Symmetric Cryptosystems using Quantum Period Finding by Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia.
- Quantum cryptograpy equip codemakers with quantum information
- Survey. [BS15] Quantum Cryptography Beyond Quantum Key Distribution by Anne Broadbent, Christian Schaffner.
- QKD [R05] Security of Quantum Key Distribution by Renato Renner.
- Quantum key exchange a la Merkle [BHK+11] Merkle Puzzles in a Quantum World by G. Brassard, P. Hoyer, K. Kalach, M. Kaplan, S. Laplante, L. Salvail.
- [BCG+02] Authentication of Quantum Messages by Howard Barnum et al.
- Quantum Secure Computation: a nice (a litte dated) talk by Adam Smith.
- Quantum Money [AC12] Quantum Money from Hidden Subspaces by Scott Aaronson, Paul Christiano.
- Quantum homomorphic encryption [DSS16] Quantum homomorphic encryption for polynomial-sized circuits by Yfke Dulek, Christian Schaffner, Florian Speelman.
- [U13] Revocable quantum timed-release encryption by Dominique Unruh.
- Device-independence, randomness amplification What if your devices for cryptography cannot be trusted (recall what NSA did)? Quantum non-locality enables certified security and a lot many fanscinating tasks.
Other models of quantum computation
- Adiabetic quantum computation [AvDK+04] Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation by D. Aharonov et al.
- Topological quantum computation [K97] Fault-tolerant quantum computation by anyons by A. Yu. Kitaev.
- Measurement-based [RB01] A One-Way Quantum Computer by Robert Raussendorf and Hans J. Briegel.
- A non-univeral model concerning bonson sampling. [AA11] The Computational Complexity of Linear Optics by S. Aaronson and A. Arkhipov.
- Qubit is precious, be conservative. [KL98] On the Power of One Bit of Quantum Information by E. Knill, R. Laflamme.
Quantum software and logic
- Universal quantum gates. Quantum computer is digital!
- [SHT16] ProjectQ: An Open Source Software Framework for Quantum Computing by Damian S. Steiger, Thomas Häner, Matthias Troyer. More info. on their project website.
- [WS14] LIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum Computing by QuArC @ Microsoft Research. Github.
- [GLRSV13] Quipper: A Scalable Quantum Programming Language by A. S. Green et al. Project website.
- [PRZ17] QWIRE: A Core Language for Quantum Circuits by Jennifer Paykin Robert Rand Steve Zdancewic.
- [YYW17] Invariants of Quantum Programs: Characterisations and Generation by M. Ying, S. Ying and X. Wu.
Quantum-inspired proofs for classical theorems
The techniques and formalism in quantum information processing have inspired proofs for mathematical theorems that seem to have nothing to do with Quantum.
- [DW11] Quantum Proofs for Classical Theorems by Andrew Drucker, Ronald de Wolf.
- [FMP+11] Linear vs. “Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf.
- [A11] A Linear-Optical Proof that the Permanent is #P-Hard by Scott Aaronson.