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