## 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