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).
- 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.
- 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.
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.
- [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.
- [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 . Can you extend to high dimensions, i.e., by reducing it to the one-dimensional case? Note that period finding over 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 …