Introduction to Quantum Computing (Fall 2023)

Course Number: COMS 4281
Date/Time: MW 11:40am-12:25pm
Room: Uris Hall 326
First meeting: September 6

Syllabus

This Week’s Office Hours (updated every Sunday)

Description

This class is an introduction to the theory of quantum computing and quantum information. Topics covered include:

• The fundamental postulates of quantum information theory
• Entanglement and nonlocality
• The quantum circuit model
• Basic quantum protocols, such as quantum teleportation and superdense coding
• Basic quantum algorithms, such as Simons’ algorithm, the Quantum Fourier Transform, Phase Estimation, Shor’s Factoring algorithm, Grover search, amplitude amplification
• Quantum error correction and fault-tolerance
• (Time permitting) Quantum cryptography, quantum advantage/quantum supremacy, quantum complexity theory

The goal of the course is to provide a rigorous foundation for future research/studies in quantum computing and quantum information, and along the way provide students with an understanding of the state of the field, and where it’s headed.

No background in quantum physics is required. However, having familiarity and comfort with abstract linear algebra is a must.

Jupyter Resources

We will be using Jupyter for lectures and assignments. Here are some resources to help you get up to speed on writing Markdown, LaTeX, and code in a Jupyter Notebook.

• Quantum Lab Primer
• Markdown and LaTex Tutorial
• Jupyter LaTex Cheat Sheet
• Jupyter Matplotlib Tutorial

Problem Sets

All problem sets will be available on this Overleaf [link]: All solutions must be submitted on Gradescope.

0. Pset0, due September 13.
1. Pset1, due September 27. Theory parts are on [Overleaf], and the programming part is [here].
2. Pset2, due October 15. Programming and theory are all in one Jupyter notebook this time; this can be downloaded [here]. [PDF Preview]
3. Pset3, due November 5. This is a theory-only Pset, which can be found on the [Overleaf].
4. Pset4, due November 22. This is a theory-only Pset, which can be found on the [Overleaf].
5. Pset5, due December 13. This has both theory and programming in Jupyter notebook environment; this can be downloaded [here]. [PDF Preview]

Schedule

All Zoom recordings are on CourseWorks

1. Week 1
   • September 6. Overview of quantum computing and the class. Class organization. Reversible computing.
   • [Slides]
2. Week 2
   • September 11. Reversible computing. Basics of quantum info.
   • September 13. Basics of quantum info, continued.
   • [Reversible computing slides] [Quantum information basics slides]
3. Week 3
   • September 18. Partial measurements. Quantum teleportation.
   • September 20. Measurements in other bases. Heisenberg's Uncertainty Principle. The EPR Paradox.
   • [Slides]
4. Week 4
   • September 25. Holevo's theorem. Superdense coding. Universal gate sets. Deutsch algorithm.
   • September 27. Simon's algorithm.
   • [Slides] [Board work for Simons algorithm]
5. Week 5
   • October 2. Quantum Fourier Transform.
   • October 4. No lecture -- President Shafik's inauguration.
   • [Slides]
6. Week 6
   • October 9. Phase Estimation Algorithm, RSA and Factoring.
   • October 11. Quantum algorithm for Order Finding.
   • [Slides]
7. Week 7
   • October 16. Grover search.
   • October 18. Quantum counting and amplitude amplification.
   • [Slides]
8. Week 8
   • October 23. Quantum complexity theory.
   • October 25. Lower bounds on Grover search. Random circuit sampling.
   • [Slides] [Lower bound on Grover board work]
9. Week 9
   • October 30. Introduction to Hamiltonians.
   • November 1. Hamiltonian simulation.
   • [Slides]
10. Week 10
    • November 8. Mixed states and noise.
    • [Slides]
11. Week 11
    • November 13. Mixed states, principle of deferred measurement, noise. [Slides]
    • November 15. Error correction. [Slides]
12. Week 12
    • November 20. Quantum error correction and fault tolerance. [Slides]
13. Week 13
    • November 27. Stabilizer formalism. [Slides]
    • November 29. Stabilizer formalism continued. Gottesman Knill Theorem. Stabilizer codes. [Slides]
14. Week 14
    • December 4. Quantum cryptography: QKD and quantum money. [Slides]
    • December 6. Ask me anything. [Slides]