# (Spring 2019) CS 440/640 Quantum Algorithms

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