Description: The modern view on quantum computing has emerged through remarkable progress in the competing practices of quantum algorithm design and hardness results. For example, demonstrations of quantum advantage in computation are fatefully tied with complexity-theoretic lower bounds, and limitations on quantum algorithms for preparing physical quantum states directly stem from quantum analogues of the famous Cook-Levin theorem. This course will address the imperative need to develop a combined understanding of quantum algorithms and quantum complexity, with emphasis on ties to quantum many-body physics and quantum information.

We will venture into some essential quantum algorithms such as quantum phase estimation, Grover's search and quantum walks; study the complexity class Quantum Merlin-Arthur along with the local Hamiltonian problem; explore the models of computation that show provable advantage of quantum resources; and discuss connections between non-locality, multi-prover interactive proofs and cryptography. Intended for graduate students and advanced undergraduate students, the course will provide sufficient background to take specialized future courses in quantum computing and apply the knowledge to pursue open questions in the field. 

Pre-requisite: CS 124 and CS 121 are required (exemption with instructor’s permission), knowledge of writing proofs is strongly recommended, knowledge in random variables, probability distributions and markov chains at the level of STAT 110 is strongly recommended. 

Scribe notes: The Scribe notes for the course are available here , along with the course content.

Student Projects: 

QITE and QLanczos: Solving Eigenstates by Quantum Methods (Weiyu Li)

Classical Simulation of Quantum Stabilizers and Clifford Circuits (Ethan Lee, Jothi Ramaswamy).

Quantum Programming Languages (William McInroy)

Proving the BQP-Completeness of the Quantum Linear Systems Problem Using a Clock Construction (Tarun Prasad, Ashley Zhuang)

Robust self-testing of a singlet via the CHSH game (Wenjie Gong) 

MA and Stoquastic Hamiltonians in Quantum Complexity Theory (Benji Kan, Vassilios Kaxiras)

Analysis of the Trotter Method for Hamiltonian Simulation (Sabina Dragoi)

Online Quantum Learning (Aayush Karan)

(many more to be added...)