Quantum computing: algorithms and complexity

(Chalmers University, Spring 2023)

Outline

Quantum computing is a rapidly growing field that brings together computer science, physics and mathematics. At a high level, quantum computing aims to make use of quantum physical effects in order to do computations that outperform non-quantum (or classical) computers at certain tasks. Examples include factoring integers, finding periods of certain functions or simulating quantum physical systems, all of which admit efficient quantum algorithms, but which are believed to be intractable for classical computers.

This PhD course will introduce the basics of quantum computation, with a focus on algorithmic capabilities and complexity. The first half of the course will be about understanding how quantum computation works (at an abstract level) and how it can be used to design efficient algorithms. We'll cover the main quantum algorithms (such as those of Bernstein and Vazirani, Simon, Shor and Grover). The second half will be about understanding where quantum computing fits in the landscape of efficient computation. We'll investigate the fundamental capabilities and limitations of quantum computing by looking at query complexity, circuit lower-bounds and (interactive) proofs. The topics covered in the second half will mostly be research-level and at the forefront of our understanding about quantum computing.

The course will be largely theoretical, though we will look at some example implementations of algorithms in a quantum programming language.

Schedule

The course will take place in person at Chalmers, starting March 15. See dates and rooms below or import the calendar event.

  • Lecture 1. Mar 15, 13:15-15:00, EC. Introduction to the course. Basics of quantum information (qubits and unitaries). [NC00] Ch 1,2; [W19] Lec 1; [A10] Lec 1.
  • Lecture 2. Mar 17, 10:00-12:00, EE. More basics: universal gates, reversibility, simple quantum circuits. [NC00] Ch 4; [W19] Lec 2; [A10] Lec 2, 3.
  • Lecture 3. Mar 22, 13:15-15:00, Zoom. Efficient computation. Boolean circuits vs unitaries and introducing oracles. [NC00] Ch 3; [W19] Lec 2; [A10] Lec 3.
  • Lecture 4. Mar 24, 10:00-12:00, Zoom. Quantum algorithms 1. The Bernstein-Vazirani problem and Simon's problem. [W19] Lec 2,3; [A10] Lec 6.
  • Lecture 5. Mar 29, 13:15-15:00, EE. Quantum algorithms 2. Shor's algorithm for factoring and the Hidden Subgroup Problem. [NC00] Ch 5; [W19] Lec 4,5,6; [A10] Lec 7.
  • Lecture 6. Mar 31, 10:00-12:00, EC. Complexity theory 1. Classical complexity classes (P, NP, coNP, PH etc). [NC00] Ch 3.2; [AB07] Ch 1,2,5.
  • Lecture 7. Apr 5, 13:15-15:00, EC. Complexity theory 2. Randomized and quantum complexity classes (BPP, MA, BQP, QCMA, QMA etc). [AB07] Ch 7,9,20; [A10] Lec 14,15,16.
  • Lecture 8. Apr 12, 13:15-15:00, EL41. Simulating quantum computation and understanding interference. [W19] Lec 13.3; [AB07] Ch 20.8; Quantum Computing Since Democritus.
  • Lecture 9. Apr 14, 10:00-12:00, EA. Query complexity. Proving lower bounds in the oracle model and revisiting Simon's problem. [AB07] Ch 3; [W19] Lec 3; Lower bound for Simon's.
  • Lecture 10. Apr 19, 13:15-15:00, EE. Quantum query complexity. Query lower bounds for quantum algorithms and introducing Grover's algorithm. [A10] Lec 9,10; [W19] Lec 7, 11.
  • Lecture 11. Apr 21, 10:00-12:00, EC. Quantum advantage 1. Shallow circuits. [AB07] Ch 6.5 Parity Halving Problem.
  • Lecture 12. Apr 26, 13:15-15:00, EC. Quantum advantage 2. Random quantum circuit sampling. Random Circuit Sampling.
  • Lecture 13. May 3, 13:15-15:00, ED. Quantum advantage 3. Proofs of quantumness and interactive tests of quantum advantage. Proofs of quantumness.
  • Lecture 14. May 5, 10:00-12:00, EC. Basics of Hamiltonian complexity. Variants of the local Hamiltonian problem and the quantum PCP conjecture. [W19] Lec 14; [A10] Lec 15, 16; [AB07] Ch 18; Survey on quantum PCP conjecture; Proof of NLTS.
  • Lecture 15. May 19, 10:00-12:00, Zoom. Verification of quantum computation. Is quantum mechanics falsifiable?; Survey paper on quantum verification; Mahadev's verification protocol.
  • Project presentations. May 24, 13:00-15:00, EE. Students present a research topic.

Requirements

Students taking the course should be familiar with the basics of:

  • Complex numbers. Euler's formula, roots of unity.
  • Linear algebra. Groups, vector spaces, inner product spaces, linear maps.
  • Probability theory. Joint and conditional probabilities, the union bound, Markov's inequality.
  • Asymptotic notation. The big O notation.

While not required, familiarity with basic programming in Python would be very useful.

Reference material

The main resources we'll be using are:

Partial lecture notes can be found here (thanks to Ivan Oleynikov).

Coding examples will be in Microsoft's Q#.

Grading and Credits

Students will be graded based on 3 written (problem-solving) assignments and a project presentation. The project (possibly in groups) will involve giving a short talk on a research topic in the last lecture.

The course will have 7.5 credits. Only PhD students can take the course for credits.

Assignments

Assignment 1 can be found here. It is due on 01.04.2023 at 23:59 CET. See sample solutions from Hanna Ek and David Wärn.

Assignment 2 can be found here. It is due on 22.04.2023 at 23:59 CET.

Assignment 3 can be found here. It is due on 17.05.2023 at 23:59 CET.

Info about project presentations and suggested topics are here. To be presented on 24.05.2023 at 13:00 CET.

Registration

Registration is closed.

Contact

Instructor: Andru Gheorghiu, Assistant professor, CSE department, Chalmers.

Email: andru at agheorghiu dot com.

Credit for the first 2 images goes to Vivian Uhlir.