Quantum information and computation

Course description

Prerequisites

The course material will be accessible to both computer scientists and physicists, provided they have a strong mathematical background. No explicit prerequisites are set for this course. We will review what is necessary but students with weaker math backgrounds may need to review material outside the course as necessary.

My expectation is that students have a strong mathematical background in linear algebra (such as MATH 318, 340, or equiv.). They should have taken and done well in such courses. In terms of computer science prerequisites, exposure to the theory of computation (such as CSE 431, 531, or equiv.) and theory of algorithms (such as CSE 417, CSE 521-22, 525, or equiv.) is useful as we will be extending the results from classical computation to quantum computation. No physics knowledge is necessary but it doesn't hurt to have taken a previous course on quantum mechanics (such as PHYS 225, 324, or equiv.). It is also helpful (but not necessary) to have taken group theory (such as MATH 402-04, 411-12, or equiv.), and analysis (such as MATH 327, 424-28 or equiv.).

Undergraduate students or graduate students of non-traditional backgrounds for this course are encouraged to contact me to see if this course is right for them.

Literature and other material

• Nielsen and Chuang. Quantum Computation and Quantum Information.
• Kitaev, Shen, and Vyalyi. Classical and Quantum Computation.

• Watrous. The Theory of Quantum Information.
• Arora and Barak. Computational Complexity: A Modern Approach.
• Vidick and Wehner. Introduction to Quantum Cryptography.
• This video lecture series from Watrous at IBM may also be helpful.

Course schedule and topics

• Lecture 00: Video Lecture on Perspective and Course Administration

  • This video lecture covers the broad perspective on what is quantum information and computation and how we will study it through this course. It also goes over most of the administrative questions you may have.
  • The video is from the 2024 version of the course. That iteration had an in-class final exam. This class will have a take-home final exam. More details will be listed near the end of the quarter. The grade split is roughly 70% problem sets and 30% final exam.
  • Video is ~40 minutes in length but definitely watchable at 2x speed.
  • We will hit the ground running in Lecture 1 with some mathematics so don't skip out on this video.
  • Peruse Problem Set 0. Additionally, the following linear algebra notes (1 & 2) from previous course iterations are helpful if problem set 0 is challenging.
  • Supplementary reading: (Problem Set 0) N&C 2.0.0 - 2.1.10
• Lecture 01 (9/24): Axioms of quantum computation, probability theory review

  • Supplementary reading: N&C 1.0.0-1.3.2, 2.2.1-2.2.2
  • Lecture 01 notes
• Lecture 02 (9/29): Elitzur-Vaidman Bomb Tester

  • Supplementary reading: N&C 1.3.3-1.3.4, 1.4.4, Sinha's notes: File 1 and File 2
  • Lecture 02 notes
• Lecture 03 (10/1): Deutsch-Josza game, Entanglement, Density Matrices

  • Supplementary reading: N&C 2.2.5-2.4
  • Lecture 03 notes
• Lecture 04 (10/6): Density matrices

  • Supplementary reading: N&C 2.6
  • Supplementary reading: Yuen's slides
  • Lecture 04 notes
• Lecture 05 (10/8): CHSH game and Bell inequalities

  • Supplementary reading: Watrous' notes
  • Lecture 05 notes
• Lecture 06 (10/13): Proof of optimality

  • Supplementary reading: Aaronson's notes
  • Lecture 06 notes
• Lecture 07 (10/15): Proof of optimality, Schmidt decompositions

  • Lecture 07 notes
• Lecture 08 (10/20): Certifiable randomness, Grover's search

  • Supplementary reading: (Grover's search) N&C 6-6.1,6.4
  • Supplementary reading: N&C 6.6-6.7
  • Lecture 08 notes
• Lecture 09 (10/22): Grover's search optimality, group theory

  • Supplementary reading: Aaronson's notes
  • Lecture 09 notes
• Lecture 10 (10/27): Bernstein-Vazirani and Simon's algorithms, quantum Fourier Transform, Abelian hidden subgroup

  • Supplementary reading: N&C 5-5.1, 5.4.1, 5.4.3
  • Lecture 10 notes
• Lecture 11 (10/29): Order finding and factoring problems (part i)

  • Supplementary reading: N&C 5.2-5.3
  • Supplementary reading: Vazirani's notes
  • Lecture 11 notes
• Lecture 12 (11/03): Order finding and factoring problems (part ii)

  • Supplementary reading: N&C 10.5.1-10.5.4
  • Lecture 12 notes
• Lecture 13 (11/05): Order finding and factoring problems (part iii)

  • Supplementary reading: Regev's notes
  • Lecture 13 notes
• Lecture 14 (11/10): Classical algorithms for quantum computation

  • Lecture 14 notes
• Lecture 15 (11/12): Introduction to quantum complexity theorys

  • Supplementary reading: Chapter 14 of Kitaev, Vyali and Shen. Note, back then the class QMA was known as BQNP.
  • Lecture 15 notes
• Lecture 16 (11/17): QMA, in-place amplification

  • Supplementary reading: N&C 10 - 10.2
  • Lecture 16 notes
• Lecture 17 (11/19): QMA-completeness, local Hamiltonian problem

  • Supplementary reading: N&C 10.3, 10.5 - 10.5.3
  • Lecture 17 notes
• Lecture 18 (11/24): Finish local Hamiltonian, Introduction to Error Correction

  • Lecture 18 notes
• No lecture on 11/26
• Lecture 20 (12/01): Properties of Error Correction, Toric Code

  • Childs' notes
  • Lecture 20 notes
• Lecture 21 (12/03): Toric Code, Hamiltonian Simulation

  • Lecture 21 notes
• Final Exam (12/08)

Problem sets and grading

• Problem Set 0: Optional and not graded.
• Problem Set 1: Due Oct 2nd 11:59pm
• Problem Set 2: Due Oct 16th 11:59pm
• Problem Set 3: Due Nov 6th 11:59pm
• Problem Set 4: Due Nov 20th 11:59pm
• Problem Set 5: Due Dec 6th 11:59pm

Grades in this course are based 70% on ~5 problem sets and 30% on the (take-home) final. As this is a graduate course, we will try to be lenient for reasonable extension requests on problem sets but all requests are up to the discretion of the TA and a reason for refusal or approval will not be given.

Artificial intelligence

The primary goal of problem sets is to help you learn and solidify the course material. Working through problems is one of the best ways to develop intuition, strengthen problem-solving skills, and prepare for the exam — which constitutes a significant fraction of your grade. Homework itself counts for only a small portion of your grade and is used primarily for pedagogical purposes, to guide your learning and ensure steady practice.

You are encouraged to collaborate with your peers on problem sets. Discussing approaches, explaining your reasoning, and hearing how others think about the problems are excellent ways to deepen your understanding. The use of AI tools (e.g., ChatGPT, Gemini, etc.) is welcome for learning purposes but not for solving explicit problems. Some problems per homework will be labelled "solve individually", so that you can honestly gauge your grasp of the material. Ultimately, you are responsible for engaging with the coursework in the way that helps you learn most effectively.

If an AI system or a peer significantly helps you in your problem-solving process, you should acknowledge them in your submission (e.g., by listing their name or the tool you used on that problem). This is both because it is an academic norm, and also to help us understand how the class is doing; although it will have no effect on the grading.

Lastly, the take home exam will not allow any access to AI tools but will be open to any notes or resources you have generated using AI tools prior to the exam.

Guidelines, Resources and Expectations

Academic Integrity

The University takes academic integrity very seriously. Behaving with integrity is part of our responsibility to our shared learning community. If you’re uncertain about if something is academic misconduct, ask me. I am willing to discuss questions you might have.

Acts of academic misconduct may include but are not limited to:

• Cheating (working collaboratively on quizzes/exams and discussion submissions, sharing answers, and previewing quizzes/exams)
• Plagiarism (representing the work of others as your own without giving appropriate credit to the original author(s))

Concerns about these or other behaviors prohibited by the Student Conduct Code will be referred for investigation and adjudication by (include information for specific campus office).

Students found to have engaged in academic misconduct may receive a zero on the assignment (or other possible outcome).

Conduct

Accessibility and Disability Resources

Your experience in this class is important to me. It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), please activate your accommodations via myDRS so we can discuss how they will be implemented in this course.

If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), contact DRS directly to set up an Access Plan. DRS facilitates the interactive process that establishes reasonable accommodations. Contact DRS at disability.uw.edu.

Religious Accomodations

Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy (https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/). Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form (https://registrar.washington.edu/students/religious-accommodations-request/).

Safety

Call SafeCampus at 206-685-7233 anytime – no matter where you work or study – to anonymously discuss safety and well-being concerns for yourself or others. SafeCampus’s team of caring professionals will provide individualized support, while discussing short- and long-term solutions and connecting you with additional resources when requested.

The University of Washington prohibits sex discrimination and sex-based harassment and expects all UW community members to respect one another in our shared academic and work environments. Sex discrimination and sex-based harassment can include sexual assault, relationship violence, stalking, unwanted sexual contact, sexual exploitation, sexual harassment, and discrimination based on sex.

Students who believe they have experienced sex discrimination or sex-based harassment are encouraged to contact a Title IX case manager by making a Title IX report. The case manager can provide guidance on available support resources and resolution options.