Introduction to Quantum Computing

Course Number: COMS 4281
Zoom link: https://columbiauniversity.zoom.us/j/94433279768 (Passcode: available on CourseWorks, or e-mail me)
Piazza link: http://piazza.com/columbia/spring2021/comsw4281
Date/Time: MW 2:40-3:55pm
First meeting: January 11

Syllabus

This Week’s Office Hours

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.

Problem Sets

All problem sets can be found at this Overleaf link. Problem Set $n$ is in the file “ps$n$.tex”. You can also use the tex file as your LaTeX template for your solutions.

• Problem Set 0 - due January 19, 11:59pm EST
• Problem Set 1 - due January 31, 11:59pm EST
• Problem Set 2 - due February 14 February 16, 11:59pm EST
• Problem Set 3 - due March 14, 11:59pm EST
• Problem Set 4 - due March 28 March 30, 11:59pm EST
• Problem Set 5 - due April 11 April 18, 11:59pm EST

Worksheets

These worksheets are meant to help you get practice with Dirac notation and basic linear algebraic manipulations used in the class. These are not collected nor graded. The TAs are more than happy to help you with them in Office Hours.

• Worksheet 1

• Worksheet 2

Schedule

1. Week 1
   • January 11. Overview of the quantum computing and quantum information; class administrivia, and basic postulates of quantum information. [Slides] [Video]
   • January 13. Classical versus quantum bits. How to safely test a bomb (with high probability). Composite quantum systems. No-cloning. [Slides] [Video]
   • Supplementary reading: Nielsen and Chuang, Sections 2.1 and 2.2.
2. Week 2
   • January 20. Outer products in Dirac notation. Quantum teleportation protocol. [Whiteboard] [Video]
   • Supplementary reading: Nielsen and Chuang, Sections 2.1.4 and Section 1.3.7. See also these lecture notes.
3. Week 3
   • January 25. Measurement in other bases. Projective measurements. Heisenberg's Uncertainty Principle. [Whiteboard] [Video]
   • January 27. Entanglement and quantum correlations. The EPR Paradox and Bell's Theorem. CHSH game. [Whiteboard] [Video]
   • Supplementary reading: Nielsen and Chuang, Sections 2.2.5, and lecture notes.
4. Week 4
   • February 1. Holevo's theorem. Superdense coding. Introduction to the quantum circuit model. [Whiteboard] [Video]
   • February 3. Universal gate sets. Solovay-Kitaev theorem. Implementing classical computation in quantum circuits. Deutsch-Josza algorithm. [Whiteboard] [Video]
   • Supplementary reading: Nielsen and Chuang Sections 1.4.4 and 4.5. See also these lecture notes.
5. Week 5
   • February 8. Review Deutsch's Algorithm. Simon's Algorithm. [Whiteboard] [Video]
   • February 10. Quantum Fourier Transform, and Phase Estimation. [Whiteboard] [Video]
   • Supplementary reading: notes
6. Week 6
   • February 15. Phase Estimation Algorithm. RSA, Factoring, and Order Finding. [Whiteboard] [Video]
   • February 17. Quantum algorithm for order finding. Post-quantum cryptography. [Whiteboard] [Video]
   • Supplementary reading: Sections 5.3 of Nielsen and Chuang. Continued fractions on Wikipedia.
7. Week 7
   • February 22. Grover Search algorithm. [Lecture notes] [Video]
   • February 24. Quantum counting and Amplitude Amplification. [Whiteboard] [Video]
   • Supplementary reading: Section 6 of Nielsen and Chuang.
8. Week 8
   • March 8. Introduction to Quantum Complexity Theory. [Whiteboard] [Video]
   • March 10. Lower bounds for solving unstructured search with a quantum computer. [Whiteboard] [Video]
   • Supplemental reading: notes
9. Week 9
   • March 15. Quantum algorithms for game tree evaluation, and quantum supremacy experiments. [Whiteboard] [Video]
   • March 17. Verification of quantum supremacy experiments. Introduction to Hamiltonians. [Whiteboard] [Video]
   • Supplemental reading: notes 1 (Quantum supremacy) and notes 2 (Hamiltonians).
10. Week 10
    • March 22. Hamiltonians. Spectral theorem and functions of Hermitian matrices. Physics perspective. Encoding CSPs as local Hamiltonians. [Whiteboard] [Video]
    • March 24. Hamiltonian simulation algorithms. HHL algorithm for solving linear systems. [Whiteboard] [Video].
    • Supplemental reading: notes and Section 2.4 of these notes for information about Hamiltonians. notes on the HHL algorithm.
11. Week 11
    • March 29. Mixed states and density matrices. [Whiteboard] [Video]
    • March 31. Distinguishability of mixed states. Modelling noise. Principle of deferred measurement. Quantum operations. [Whiteboard] [Video]
    • Supplemental reading: Section 2.4 of Nielsen and Chuang.
12. Week 12
    • April 5. Noise and errors in classical computation. Errors in quantum computation. Bitflip code, phaseflip code, Shor's 9 qubit code. [Whiteboard] [Video]
    • April 7. Finish up discussion of Shor's code. Why correcting X/Y/Z errors is enough. Other error correcting codes. Fault tolerance and the threshold theorem. [Whiteboard] [Video]
    • Supplemental reading: notes
13. Week 13
    • April 12. Quantum key distribution, quantum money. [Whiteboard] [Video]
    • April 14. Quantum computing hardware and the NISQ era. [Slides] [Video]
    • Supplemental reading: notes