# Quantum Course Project (Winter 2024)

As part of the course, you will be required to do a course project. The project can be done in groups of up to 3. There will be two components -- a project report and a short 5-min presentation. The project report and presentation are due towards the end of the course.

## Project report and presentation (due Tues March 12th)

Pick a paper related to quantum computing, and prepare a short 2 page report summarizing the main ideas of the paper, and record a short 5 minute presentation about the paper that you chose (Zoom is fine). Only one report and one presentation is needed per group.

## Sample papers
Note: This list may potentially be updated with other examples. You can also suggest another paper not on the list -- but please do run it by the instructors first.

**Quantum Algorithms**

An Efficient Quantum Factoring Algorithm (Oded Regev)
https://arxiv.org/abs/2308.06572

A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space (Oded Regev) https://arxiv.org/abs/quant-ph/0406151

A CS guide to the quantum singular value transformation (Ewin Tang, Kevin Tian) https://arxiv.org/abs/2302.14324

Quantum Algorithms for Element Distinctness https://arxiv.org/abs/quant-ph/0007016

A Quantum Advantage for a Natural Streaming Problem (John Kallaugher) https://arxiv.org/abs/2106.04633

Exponential algorithmic speedup by quantum walk (Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman)
https://arxiv.org/abs/quant-ph/0209131

Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics (Gilyen, Su, Low, Wiebe) https://dl.acm.org/doi/pdf/10.1145/3313276.3316366

Quantum Algorithms for Solving Systems of Linear Equations(Harrow, Hassidim, Lloyd) https://math.berkeley.edu/~linlin/2018Spring_290/HHL09.pdf

Provably efficient machine learning for quantum many-body problems. H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, J. Preskill. https://arxiv.org/abs/2106.12627

Learning quantum Hamiltonians at any temperature in polynomial time (Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang)
https://arxiv.org/abs/2310.02243

**Quantum Complexity**

Classical Verification of Quantum Computations (Urmila Mahadev) https://arxiv.org/abs/1804.01082

Computational Complexity of Linear Optics (Scott Aaronson, Denis Arkhipov) http://www.theoryofcomputing.org/articles/v009a004/

NLTS Hamiltonians from good quantum codes
Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe.
https://arxiv.org/abs/2206.13228

Oracle Separation of BQP and PH (Ran Raz, Avishay Tal) https://eccc.weizmann.ac.il/report/2018/107/
(This may be challenging)

Quantum Coupon Collector (Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf) https://arxiv.org/abs/2002.07688

Quantum lower bounds for the collision and the element distinctness problems (Yaoyun Shi) https://arxiv.org/abs/quant-ph/0112086

Lower Bounds on Stabilizer Rank (Shir Peleg, Amir Shpilka, Ben Lee Volk) https://arxiv.org/abs/2106.03214

Quantum Approximate Counting, Simplified (Scott Aaronson, Patrick Rall) https://arxiv.org/abs/1908.10846

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation (Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev) https://arxiv.org/abs/quant-ph/0405098

The Computational Complexity of Linear Optics (Boson Sampling) (Scott Aaronson, Denis Arkhipov) https://arxiv.org/abs/1011.3245

A polynomial-time classical algorithm for noisy random circuit sampling (Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh Vazirani) https://arxiv.org/abs/2211.03999

**Entanglement**

Mixed-state entanglement and distillation: is there a “bound” entanglement in nature? (Michal Horodecki, Pawel Horodecki, Ryszard Horodecki) https://arxiv.org/abs/quant-ph/9801069

Testing product states, quantum Merlin-Arthur games and tensor optimisation (Aram W. Harrow, Ashley Montanaro)
https://arxiv.org/abs/1001.0017

A quasipolynomial-time algorithm for the quantum separability problem (Brandao, Christandl, Yard) https://arxiv.org/abs/1011.2751

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality (Adam Bouland, Bill Fefferman, Umesh Vazirani)
https://arxiv.org/abs/1910.14646

**Quantum Information**

Stabilizer Codes and Quantum Error Correction (Daniel Gottesman) https://arxiv.org/abs/quant-ph/9705052

Surface codes: Towards practical large-scale quantum computation (Austin G. Fowler, Matteo Mariantoni, John M. Martinis, Andrew N. Cleland)
https://arxiv.org/abs/1208.0928