CSE 598 Spring 2021

Class meetings: Mondays and Wednesdays 9–10:15am (online).

Instructor: Zilin Jiang (he, him, his).

Course description

In this guided tour, we will explore quantum computation from the perspective of theoretical computer science. Topics include quantum algorithms, quantum error correction, and quantum information.

Prerequisites: A strong undergraduate background in linear algebra, discrete probability, and theory of computation. No background in physics is required.

Required textbook: Mermin, N. David. Quantum computer science: an introduction. Cambridge University Press, 2007. [library]


Asking questions:

For class-related questions it is best to come to office hours. Another possibility: Ask them on Piazza. Administrative questions too can be asked there, especially if other students might be able to answer them or might learn from the answer.


Scribing lecture notes worth 10%, and homework for the remaining 90%.


Submissions must be typed in LaTeX. All steps should be justified. You are strongly encouraged to do as much homework as possible individually; you will gain the most of out the course this way.

Sources and collaboration policy. Collaboration and use of external sources are permitted, but must be fully acknowledged and cited. Collaboration may involve only discussion; all the writing must be done individually. Failure to do so will be treated as cheating (see What is Academic Integrity?).

Late policy. In general no late homework will be accepted unless there is a genuine emergency backed up by official documents.

Homework 1 due on Feb 1

Homework 2 due on Feb 15

Homework 3 due on March 1

Homework 4 due on March 15

Homework 5 due on March 29

Homework 6 due on April 12


Week 1

Jan 11. Class overview, multiplication vs factorization.

Jan 13. Probabilistic computation, matrix multiplication probabilistic checker, primality testing.

Week 2

Jan 18. No class (Martin Luther King Jr. Holiday)

Jan 20. Qbit, two laws in quantum mechanics, measurement, Dirac’s bra-ket notation, measuring in different bases

Week 3

Jan 25. Three polarizers, the Elitzur–Vaidman bomb-tester

Jan 27. Unitary transformations, discriminating two states

Week 4

Feb 1. Tensor product, CNOT gate, Bell state, partial transformation

Feb 3. Partial measurement

Week 5

Feb 8. Indistinguishable mixed states, the CHSH game

Feb 10. The CHSH game (continued), quantum teleportation, quantum swapping

Week 6

Feb 15. No-cloning theorem, Wiesner’s scheme, (5/8)^n-attack

Feb 17. Wiesner’s scheme (continued), public-key quantum money

Week 7

Feb 22. Effective simulation of classical circuits by reversible (quantum) circuits, CSWAP is universal for reversible circuits

Feb 24. Un-computing garbage, (sign-)implementation, Hadamard transformation

Week 8

Mar 1. Boolean Fourier transformation, revealing XOR patterns

Mar 3. XOR-pattern vectors, Bernstein–Vazirani algorithm, Deutsch–Jozsa algorithm

Week 9

Mar 8. Simon’s algorithm

Mar 10. Discrete Fourier transform

Week 10

Mar 15. Simon’s algorithm over ℤ/Nℤ

Mar 17. Shor’s algorithm

Week 11

Mar 22. Hidden subgroup problem

Mar 24. Hidden subgroup problem (cont.) and Grover’s algorithm

Week 12

Mar 29. Grover’s algorithm (cont.)

Mar 31. Quantum query complexity model, basic adversary method

Week 13

Apr 5. Basic adversary method (cont.), density matrices of mixed states

Apr 7. Working with density matrices

Week 14

Apr 12. Quantum probability, positive operator-valued measurements, observables

Apr 14. Quantum information theory, entropy, partial trace operation, mutual information

Week 15

Apr 19. A simple model in quantum error correction

Apr 21. 5-qbit quantum error correction