# (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****Non-abelian**hidden subgroup problem

### 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
**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.

- [BHMT02]
- [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.

### Quantum simulation related algorithms

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.

### 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.

- [FMMC12]
**Quantum Shannon Theory**Quantum information shows distinct features than what Shannon’s theory about classical information describes.- 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.

- [A16 Chapter 6]

### 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? - 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.

- [M18]
**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.

- [AN02]

### 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.

### 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.

- [Z12]
**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.

- [BCMVV18]

### 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.

- [AA11]
- 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?**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.