Quantum Computation
Spring 2021, Arizona State University
Class meetings: Mondays and Wednesdays 9–10:15am.
Instructor: Zilin Jiang (he, him, his)
Office hours: Mondays 10:15–11:00am, and Fridays 10am–11am.
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]
Onboarding:
- Please fill out the pre-semester questionnaire.
- Learn how to use LaTeX (I recommend the tutorials on Overleaf).
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.
Grading
Scribing lecture notes worth 10%, and homework for the remaining 90%.
Homework
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
Schedule
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