(Fall 2022) 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 carefully. You will 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.
-
Programming project. Sure, why not get your hands dirty, thanks to the 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 is becoming a buzz word. What is the broader implication of quantum technology? What is happening in the society to get ready for this technology? Are there ethical issues concerning the technology and the workforce development?
Milestones
- Proposal: 1-2 pages consisting of 1) the topic, background, context, and motivation; 2) a few core references; and 3) your goal and a plan. (10%)
- Oral presentation: Each group will have about 30 minutes 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 fellow students. (20%)
- Final report: <= 10 pages (excluding references). 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 the main 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: discussing project ideas.
- Week 5: proposal due on 10/28, 11:59pm anytime on Earth.
- Week 8: progress check-up meetings.
- Week 10: in-class presentations.
- 12/08: final report due, 11:59pm anytime on Earth.
Suggested topics
The list below is far from complete, and is only intended as a starting point for you to explore your options. Suggestions on “societal-impact” and “programming” are especially brief to give your creativity enough room. Here are a few general readings.
- [deWolf17] The Potential Impact of Quantum Computers.
- [CCC17] Next Steps in Quantum Computing: Computer Science’s Role.
- [NAP19] Quantum Computing: Progress and Prospects.
- [Quantum software – beneath the quantum hype] Reflections on NISQ era.
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.)
- Misinformation 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. Where is the US government’s funding going? How is it influencing the gap between resources to different institutes?
- 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].
- Ethical issues. Can quantum technology help alleviate pressing social crisis? Or is it possibly exacerbating problems such as global warming and inequality? An APS interview titled “Should We Build Quantum Computers at All? ”.
- 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 device, as well as features of the software kits. Here is an introduction to benchmarking quantum computers, and a report 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 advantage”, 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
- [YZ22] A breakthrough result showing quantum advantage with an unstructured oracle.
- [CKKD+22] Quantum analogue of the ubiquitous Divide-and-Conquer technique.
- [YLC14] Fixed-point quantum search.
- [AGJ19] A Unified Framework of Quantum Walk Search.
- [GSLW18] Introduces singular value transformation, a cute framework unifying several quantum algorithmic techniques.
- [AR19] Quantum Approximate Counting, Simplified.
- [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.
- [Ros22] Grover search lower bound under a mix of classical and quantum queries.
- 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.
- [HMY22] Trading quantum gravity for quantum cryptography?
- [BCMVV18] Testing quantumness and generating certifiable randomness.
- [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.
- [MY21 AQY22] Cryptography from quantum pseudorandomness. What is the minimal assumption for cryptography?
- Clearing up the folklore