Quantum Computing: Foundations to Frontier

Course Number: CSC2451/MAT1751H
Location: Bahen 1220
Date/Time: Wednesday 2-5pm
Office hours: TBD


This course will give a broad overview of the field of quantum computing. We will start with a crash course in the fundamentals of quantum computing (qubits, quantum circuits, basic quantum algorithms such as Grover’s search algorithm and Shor’s factoring algorithm). Armed with the basics, we will then explore topics at the frontier of quantum computing: quantum simulation, quantum cryptography, connections with physics, quantum machine learning algorithms, and quantum supremacy. Students will make project presentations at the end of the course. This is a theoretical course that requires mathematical maturity and a strong background in linear algebra and probability theory.

Schedule (tentative)

Date Topic, Notes, and References
September 12 Administrativa. Basics of quantum information.
September 19 Entanglement, Bell games, randomness generation. Quantum circuit model, Solovay-Kitaev.
September 26 Algorithms (Grover, Simons, Hidden Subgroup, Quantum Fourier Transform)
October 3 Quantum Hamiltonians, Simulation, Chemistry, AdS/CFT, Blackhole Firewall Paradox
October 10 Quantum Machine Learning. HHL Algorithm. Phase estimation. Recommendation systems. Quantum neural networks, QRAM.
October 17 Quantum complexity theory. BQP and friends. QMA completeness. Lower bounds.
October 24 Near-term quantum computing. Quantum supremacy. BosonSampling/Random circuit sampling. Complexity theoretic evidence.
October 31 QAOA, variational eigensolvers, classical-quantum hybrid algorithms. Konig-Bravyi-Gosset.
November 7 Reading week, no class
November 14 Crypto I (information-theoretic). Quantum key distribution. Device-independence. Impossibility of quantum bit commitment. Coin flipping. Quantum resistant crypto.
November 21 Crypto II. Delegated quantum computation. Quantum money. Quantum homomorphic encryption. Entangled proof systems.
November 28 Grabbag.
December 5 Project Presentations