# (Spring 2019) CS 440/640 Quantum Algorithms

## Project

## Instructions

2-3 people group projects. You may go with one (or superposition) of the following options

*literature review*. Pick a topic of interest, and summarize the state of art of it. The final outcome would be a*survey*paper including open problems.*completing “folklore”*. There are ``folklore’’ results in the filed or missing details in class that are worth spelling out more carefully. You will conduct a careful study a dedicated problem and give a thorough exposition on it.*original research*. Challenge yourself with some open question in the field. You are encouraged to explore the potential of quantum computing in your own research area. Be*creative*and keep a*critical*mind.*quantum programming*. Implement some quantum algorithms and protocols in quantum programming platforms (e.g., Q#,Quirky,IBM QISKIT,RigettiForest), and go beyond by optimizing the circuit, estimating the cost, and testing variations (e.g., robustness against noise).

### Specs

**Proposal**: 1-2 pages consisting of 1) the topic, background, context, and motivation; 2) identify a few core papers to be studied; and 3) a goal you intend to achieve and a plan.**Oral presentation**: Each group will have about 30mins to present your project including Q&A. Your need to demonstrate both*breath*and*depth*. Aim for a clear introduction that would**interest**the audience, and then explain 1-2 technical ideas in some detail. Every group member needs to participate, and your group will be graded by other fellow students. You may use slides or whiteboard.**Final report**: ~10 pages. This should resemble a 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 & definitions), explaining some main technical results; and finally 4) further discussion and open questions.**Report format**: I recommend you 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.

### Timeline (Tentative)

**Week 1 & 3**: forming groups.**Week 4 & 5**: discussing project ideas.**February 18**: proposal due, 11:59pm anytime on Earth.**Week 14-15**: in-class presentations.**May 03**: final report due, 11:59pm anytime on Earth.

## Suggested Topics

The list below is necessarily incomplete, and you are welcome to choose a topic not on the list. A few venues to look for inspirations: QIP, Qcrypt, and general TCS conferences (e.g., STOC, FOCS, SODA, Crypto).

### More quantum algorithms

- [CvD07,IPS18]
Generalized hidden-shift problem via various techniques (e.g.,
*pretty-good-measurement*). - [BKL+18,AG18] Quantum algorithms for solving semi-definite programs, a central problem in convex optimization.
- [GSLW18] Introduces
*singular value transformation*, a nice framework unifying several quantum algorithmic techniques. - [CKS15] Improves HHL’s quantum algorithms for solving linear systems.
- [FG14]
*Quantum Approximate Optimization Algorithm*(QAOA). - [AW17,LMR14]
Quantum algorithms for machine learning, e.g.,
*principal component analysis*. - [Tang18,CLLW19] Tang’s novel idea enables efficient classical algorithms (in a non-standard model) for recommendation systems and other problems, inspired by quantum algorithms.
- [LGNR18] Quantum advantage in distributed computing.

### Quantum complexity

- [KSdW05] Time‐Space Tradeoffs for quantum query complexity. Any implication in Proof-of-work or Proof-of-Space in blockchain designs in the presence of quantum attacks?
- [BBCMW01,ABP17]
One central quantum lower-bound technique:
*polynomial method*. - [HLS07,Reichardt11]
Another central quantum lower-bound technique:
*adversary method*. - [JJUW09] QIP = PSPACE (=IP). Quantum interactive proof systems turn out to assume the same power of classical IP, but still with unique properties.

### Quantum information theory

- [CBTW15] Uncertainty relation, a unique feature in quantum theory, in the language of entropy.
- [FMMC12,CR17a,CR17b,FGL18]
Recent advances on quantum error-correction and fault-tolerance,
e.g.
*Surface codes*and FT with*constant*overhead. - [HOW05,SY08] Some weirdness about quantum information, such as
*negative*information and communicating with*zero-capacity*channels. - [HH13,A16 Chapter 6]
Some fascinating connection of quantum information to the theory of
**black holes**.

### Quantum-safe cryptography

- [PQC,ToB18]
Securing classical cryptography against quantum attacks, known as
*post-quantum cryptography*. - [Urmila18] Homomorphic encryption that admit evaluation of quantum circuits. A novel idea that also lead to breakthrough results by the same author.
- [Zhandry18] A unique quantum primitive, quantum lightening, with applications in quantum money. Can you construct it from other problems?
- [DPVR12] Making
randomness extractors secure against
*quantum side information*.

### Programming and simulating quantum computers

- [Urmila18] Implement a protocol
for verifying a server’s
*quantumness*. Optimize the quantum circuit by some tool for circuit synthesis (Cf. MM16). - [HM17,FH16,CZH+18,QWE19] Test (on a small scale) proposals for “quantum supremacy”, and compare with simulations on classical computers.
- [KLLNP16,GM19] Simon’s algorithm can break some symmetric-key cryptosystems. Can you demonstrate some toy example?
- Some tools on optimizing reversible/quantum circuit: [RevKit,Feynman]

### Clearing up the folklore

- [Shor97,Childs] Shor’s algorithm can be seen as period finding over \(\mathbb{Z}\). Can you extend to high dimensions, i.e., \(\mathbb{Z}^n\) by reducing it to the one-dimensional case? Note that period finding over \(\mathbb{Z}^n\) can also be solved as a special case of a more general problem in EHKS14.
- [Cleve11,KNP05] Exact lower bounds for Simon’s problem, on probabilistic and quantum computers. Bounding the success probability given a fixed number of queries.
- [BSS03] Workspace in a quantum query algorithm. Does more space give you more power?
- More to come …