(Spring 2018) CS 410/510 - Intro to Quantum Computing

Course Project

Instructions

2-3 people group projects. You may choose to do a literature review project or (more exciting) mini 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!).

Specs

  • 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 followed by 5-minute Q&A. Your presentation should demonstrate 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: 1) a short abstract; 2) an introduction that motivates the topic/problem and gives an overview of the entire report; 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: you are recommended to typeset your reports in LaTeX, and manage your bibliography using BibTeX. The resource page has links to materials to pick up LaTeX. You should use single-column, single-space (between lines) format on letter-size papers. Here is a barebone [TeX PDF] template. You may also follow a suitable ACM Article Template (e.g., ACM Small format). Many LaTeX templates are availabe there. There are online TeX editors available if you don’t want to install a local engine, e.g., Overleaf.

Timeline (Tentative)

  • Week 1 & 2: forming groups.
  • Week 3 & 4: meeting and discussing project ideas.
  • April 27: proposal due.
  • May 14: mid-term report due.
  • Week 10: in-class presentations.
  • June 13: final report due, 11:59pm any time zone.

Suggested Topics

Feel free to pursue a project not on this list. I’m happy to meet with your group and discuss about your ideas.

A few venues to look for inspirations:

Quantum algorithms for algebraic problems

Shor’s quantum factorization problems is a notable example of solving algebraic problems faster, sometimes with exponential speedup, on a quantum computer than best known classical algorithms.

  • General survey [CvD10] Quantum algorithms for algebraic problems by Andrew M. Childs, Wim van Dam.
  • [W01] Quantum algorithms for solvable groups by J. Watrous.
  • (Generalized) hidden shift problem
    • [vDHI02] Quantum Algorithms for some Hidden Shift Problems by W. van Dam, S. Hallgren, and L. Ip. A. Childs and W. van Dam, “Quantum algorithm for a generalized hidden shift problem”.
    • [CvD05] Quantum algorithm for a generalized hidden shift problem by A. Childs and W. van Dam.
  • Non-abelian hidden subgroup problem
    • [EK04] The quantum query complexity of the hidden subgroup problem is polynomial by M. Ettinger, P. Høyer, E. Knill.
    • [K03] A subexponential-time quantum algorithm for the dihedral hidden subgroup problem by G. Kuperberg.

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. Grover’s quantum search algorithm can be viewed as a special case of quantum random walk.

  • Survey papers
    • [K03] Quantum random walks – an introductory overview by J. Kempe.
    • [A04] Quantum walks and their algorithmic applications by A. Ambainis.
  • Amplitute amplification: simple generalization of Grover’s search algorithm.
    • [BHMT02] Quantum Amplitude Amplification and Estimation by Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp.
    • Oblivious amplitute amplification. [BCC+14] Exponential improvement in precision for simulating sparse Hamiltonians by D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, R. D. Somma.
  • [MNRS06] Search via Quantum Walk by F. Magniez, A. Nayak, J. Roland, and M. Santha.
  • [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.

Original motivation of quantum computers proposed by R. Feynman. Closely related to quantum algorithms for linear systems. They might already be meaningful on near-term quantum processors (~100 noisy qubits). Machine learning is a potential application.

  • [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.
    • A survey. [AW17] A Survey of Quantum Learning Theory by S. Arunachalam, R. de Wolf.
    • [LMR14] Quantum principal component analysis by Seth Lloyd, Masoud Mohseni, Patrick Rebentrost.

Quantum Information Theory

  • Quantum error correcting and fault-tolerence. We only scratch the surface of this topic in class. Quantum information is prone to noise, and to transmit quantum information reliably and build a robust quantum computer, we need to correct errors and further make all computation fault-tolerant. These techniques have also found critical in quantum cryptography.
    • [FMMC12] Surface codes: Towards practical large-scale quantum computation by Austin G. Fowler, Matteo Mariantoni, John M. Martinis, Andrew N. Cleland.
    • [ABO99] Fault-Tolerant Quantum Computation with Constant Error Rate by D. Aharonov and M. Ben-Or.
    • [CR17a] Quantum error correction with only two extra qubits by Rui Chao, Ben W. Reichardt.
    • [CR17b] Fault-tolerant quantum computation with few qubits by Rui Chao, Ben W. Reichardt.
  • Quantum Shannon Theory Quantum information shows distinct features than what Shannon’s theory about classical information describes.
    • [HOW05] Quantum information can be negative by M. Horodecki, J. Oppenheim, A. Winter.
    • [SY08] Quantum Communication With Zero-Capacity Channels by G. Smith, J. Yard.
  • Quantum information and black holes. There is some fancinating connection to the theory of black holes.
    • [A16 Chapter 6] From quantum money to balck holes by S. Aaronson.

Quantum Computational Complexity

There is a large body of research that explores abstractly the strengths and the limits of quantum computing.

  • General survey [W09] Quantum Computational Complexity by J. Watrous.
  • Quantum interactive proofs What problems can you compute by interacting with a ``powerful’’ guru?
    • A comprehensive survey. [VW16] Quantum Proofs by Thomas Vidick, John Watrous.
    • [JJUW09] QIP = PSPACE by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
  • Can you verify a quantum computer by a classical computer? Someone claims a quantum computer at hand, can you trust him/her?
    • [M18] Classical Verification of Quantum Computations by Urmila Mahadev.
  • Hamiltonian Complexity How difficult is it to determin the ground energy of a physical system?
    • [AN02] Quantum NP - A Survey by Dorit Aharonov, Tomer Naveh.

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
    • [ABDK16] Separations in query complexity using cheat sheets by Scott Aaronson, Shalev Ben-David, and Robin Kothari.
    • [ABBD+16] Separations in communication complexity using cheat sheets and information complexity by Anurag Anshu et al.
  • [ATYY16] Exponential Separation of Quantum Communication and Classical Information by Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu.

Quantum and crypto

  • Post-quantum crypto cope with quantum codebreakers
    • [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.
    • [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.
    • [SY17] Quantum Security of NMAC and Related Constructions by F. Song and A. Yun. A positive message, proving several security constructions, in regard to the above attack.
  • Quantum cryptograpy equip codemakers with quantum information processing
    • Survey. [BS15] Quantum Cryptography Beyond Quantum Key Distribution by Anne Broadbent, Christian Schaffner.
    • 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.
    • Quantum Money [AC12] Quantum Money from Hidden Subspaces by Scott Aaronson, Paul Christiano. [A16 Chapter 8,9] From quantum money to balck holes by S. Aaronson.
    • Quantum homomorphic encryption [DSS16] Quantum homomorphic encryption for polynomial-sized circuits by Yfke Dulek, Christian Schaffner, Florian Speelman.
  • Device-independence, randomness amplification What if your devices for cryptography cannot be trusted (recall what NSA did)? Quantum non-locality enables certified security.
    • [BCMVV18] Certifiable Randomness from a Single Quantum Device by Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, T. Vidick.

Other models of quantum computation

  • Adiabetic quantum computation [AvDK+04] Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation by D. Aharonov et al.
  • Measurement-based [Jozsa05] An introduction to measurement based quantum computation by R. Jozsa.
  • Topological quantum computation: Microsoft is pursing this direction. A beautiful idea that would make noises much easier to deal with. [K97] Fault-tolerant quantum computation by anyons by A. Yu. Kitaev.
  • A non-univeral model concerning bonson sampling, which is also a promising approach to demonstrate quantum supremacy.
    • [AA11] The Computational Complexity of Linear Optics by S. Aaronson and A. Arkhipov.
    • [BFNV18] Quantum Supremacy and the Complexity of Random Circuit Sampling by A. Bouland, B. Fefferman, C. Nirkhe, U. Vazirani.
  • 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! How come one can implement a continuous space of unitary operations by a constant-size gate set?
    • Survey. [DN05]The Solovay-Kitaev algorithm by Christopher M. Dawson, Michael A. Nielsen.
    • [S03] Both Toffoli and Controlled-NOT need little help to do universal quantum computation by Y. Shi.
  • Quantum software (and hardware) platforms. Project idea: survey some popular platforms, and write quantum programs to simulate selected quantum algorithms on some backends (classical simulator or actual quantum processor).
    • [IBM18] IBM Q Experience and Quantum information software Kit QISKit.
    • [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.
    • MS18 Microsoft Quantum Development Kit by QuArC @ Microsoft.
    • [GLRSV13] Quipper: A Scalable Quantum Programming Language by A. S. Green et al. Project website.
  • Thoery of quantum programing. [LY18] _Algorithmic Analysis of Termination Problems for Quantum Programs _ by Y. Li, M. Ying.