(Spring 2020) CS 410/510 - Intro to Quantum Computing

Course Project

Instructions

2-3 people group projects. You may choose one (or superposition) of the options below.

  • Research project. Take any route to gain some research experience.
    • 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 on 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.
  • Programming project. Sure, why not get your hands dirty, thanks to the exciting advances of physical devices and software frameworks (see some popular ones below). You may test and optimize quantum algorithms and protocols in a platform, or you might want to contribute to new features of these tools.

  • Societal-impact project. Quantum technology is reaching to the larger society. You are definitely seeing more and more news reports on quantum computing, as well as stories on quantum start-ups. What is the broader implication of quantum technology? What is happening in the society to get ready for this technology? Studies on these questions seem falling behind!

Milestones

  • Proposal: 1-2 pages consisting of 1) the topic, background, context, and motivation; 2) identify a few core references; and 3) a goal you intend to achieve and a plan. (10%)
  • 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 engage 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. (20%)
  • Final report: ~10 pages. This should resemble a research paper: 1) a short abstract; 2) an introduction that motivates the topic and offers 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. (10%)
  • 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. You will earn extra credit if you typeset your final report in LaTeX.

Timeline (Tentative)

  • Week 1 - 3: forming groups.
  • Week 4 - 5: discussing project ideas.
  • May 3: proposal due, 11:59pm anytime on Earth.
  • Week 10: in-class presentations.
  • June 12: 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. Suggestions on “societal-impact” and “programming” are brief to give your creativity enough room. Here are a few general readings.

Societal impact

(We need scientists and engineers to advance the field of quantum computing. But what is equally important, if not more, is to have more people think broadly the implications and proper actions to take.)

  • Misconceptions in mass media. Are we doing a good job so far to deliver the idea of quantum computing to the general audience? Some popular sites: [Phys.org, Quantamagazine, MIT Tech Review]. An ebook by Graves on Deciding what’s true is available via Library eLink.
  • The research efforts and focuses of different regions and countries. For instance, look at the Quantum Internet effort in EU. US National Strategic Overview.
  • Impact on labor market. How many patents are being filed? How much investiment is being injected in quantum startup companies? Are we going to see jobs in quantum? This report on AI might help.
  • Impact on education. Are there sufficient resource to pick up quantum computing (e.g., MOOC at various levels)? Shall we update the curriculum in college (or even in high school)? Some teasers: [IHE, Fermilab].
  • More to be filled by you …

Programming

  • Popular quantum programming platforms (some with hardware too): IBM Qiskit, Microsoft Q# development kit, Google Cirq, Rigetti Forrest SDK. You may conduct a comparative study on the qualities of their physical devices, as well as features of the software kits. Here is an introduction to benchmarking quantum computers, and a more recent one on benchmarking an 11-qubit quantum computer.
  • [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?
  • Extensions to consider for implementation and simulation of quantum algorithms: optimize the circuit, estimate the cost, test variations (e.g., robustness against noise), etc.
  • Tools on optimizing reversible/quantum circuit: [RevKit,Feynman,ZX-Calculus]
  • Develop a quantum computer game? Here is an example quantum battleship.

Research

  • Check out the frontier research topics at these venues: QIP, Qcrypt, and general TCS conferences (e.g., STOC, FOCS, SODA, Crypto).

  • More quantum algorithms
    • [YLC14] Fixed-point quantum search.
    • [AGJ19] A Unified Framework of Quantum Walk Search.
    • [GSLW18] Introduces singular value transformation, a nice framework unifying several quantum algorithmic techniques.
    • [CKS15] (Improved) quantum algorithm for solving linear systems, which inspired many quantum machine learning algorithms.
    • [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.
    • [AR19] Quantum Approximate Counting, Simplified.
    • [ABI+19] Quantum speedups for exponential-time dynamic programming algorithms.
    • [CSZJ20] Variational Quantum State Eigensolver. An algorithmic framework suitable for near-term quantum devices.
  • 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.
  • Quantum information theory
    • [HHL04] Superdense coding of quantum states.
    • [CBTW15] Uncertainty relation, a unique feature in quantum theory, in the language of entropy.
    • [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 lightning, with applications in quantum money. Can you construct it from other problems?
    • [DPVR12] Making randomness extractors secure against quantum side information.
  • Clearing up the folklore
    • [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?