DD3335 Quantum Computing 6.0 Credits

   Course Description
  • The purpose of this course is to give a concise introduction to the theory of quantum computation. We will be in particular concerned with the algorithmic aspects of the theory, but topics such as quantum computational complexity, classical simulation of quantum circuits and exotic models of quantum computation will also be addressed. The expected audience for the course will be master and PhD students in computer science, mathematics or physics, but in principle anybody with enough curiosity will be more than welcome. The main prerequisite for the course is a good knowledge of linear algebra.
   Practical Information
  • The course will run on Mondays, 10:00-12:00, starting from November 5th.
  • Room: 4523, Department of Theoretical Computer Science KTH.
  • Contact: Mateus de Oliveira Oliveira (mdeoliv@kth.se)
  • Course Mailing List: Please feel free to send me an email with any question concerning the course, or to tell me if you wish to be added to the course's mailing list.
  • Course Official Homepage: DD3335
   Planed Lectures: (Preliminary Version)

  • Lecture 1 - Overview of The Course (05/NOV/2012) - Slides to be posted soon.

    • Motivation: In this lecture we gave a brief historical overview of some of the main results in quantum computation. We described the implications of several quantum algorithms: Deutsch's, Deutsch-Jozsa's, Bernstein-Vazirani's, Simon's, Shor's Integer factorization and Grover's search. We motivated the Abelian Hidden subgroup problem by arguing that, it generalizes all algorithms described above (except Grover's), and the non-Abelian Hidden subgroup problem by showing its connections with the unique shortest vector problem, lattice based cryptography and graph isomorphism. We also addressed the possibility of simulating certain quantum systems using classical computers. Finally we motivated the study of the approximation of the Jones Polynomial for Knots, and the approximation of the ground state energy of hamiltonians by showing its connections to quantum computational complexity. The goal of this course is to turn all these results accessible by assuming only familiarity with linear algebra.
  • Lecture 2 - Basics (12/NOV/2012) - Slides available on the link.

    • Postulates of Quantum Mechanics.
    • Qubits, Gates, Measurements ...
    • Quantum circuits
  • Lecture 3 - Simple Protocols (19/NOV/2012) - Slides available on the link.

    • Superposition, Boolean vs Quantum Circuits, etc
    • Deutch's problem
    • Bernstein Vazirani problem
  • Lecture 4 - The Hidden Subgroup Problem (26/NOV/2012) - Slides available on the link.

    • Simon's Algorithm
    • The Hidden Subgroup Problem
    • Simple reductions to the Hidden Subgroup Problem
    • Quantum Fourier Transform for the integers
  • Lecture 5 - The Quantum Fourier Transform (03/DEC/2012) - Slides available on the link.

    • Hidden subgroup for Abelian Groups (Shor's algorithm)
    • Hidden subgroup for non-abelian groups
    • Quantum Fourier transform for General Groups
  • Lecture 6 - Quantum Search (10/DEC/2012) - Slides available on the link.

    • Grover's Algorithm
    • Phase Estimation
    • Eigenvalue Estimation
  • Lecture 7 - Quantum Errror Correction I (17/DEC/2012) - Slides available on the link.

    • Classical vs Quantum Error Correction
    • Shor code
  • Lecture 8 - Quantum Error Correction II - Toric Code (14/01/2013) - Slides available on the link.

    • Stabilizer codes
  • Lecture 9 - Classical Simulation Of Restricted Classes of Quantum Circuits (21/01/2013) - Slides available on the link.

    • Tensor networks and simulation of circuits of small tree width.
  • Lecture 10 - Approximation of the Jones Polynomial (28/01/2013) - Slides available on the link.

    • Jones Polynomial
    • Temperley-Lieb Algebras
    • Aharonov-Jones-Landau's algorithm for approximating the Jones Polynomial
  • Lecture 11 - The Local Hamiltonian Problem (04/02/2013) - Slides available on the link.

    • QMA vs NP
    • The Local Hamiltonian Problem is Complete for QMA
  • Lecture 12 - Non Local Games (11/02/2013) - Slides available on the link.

    • XOR games
    • Tsirelson's Theorem
    • Grothendiek's inequality
   Course Evaluation
  • Three problem sets covering basic material from the course.
  • If you were not able to handle some of the problem sets, then you can replace up to two problem sets by one of the following options:
    • A 12 pages survey on some of the advanced topic of your choice.
    • A small open ended project of your choice.
    • A 50min lecture given by you on some advanced topic per problem set (up to 2 problem sets).
  • Grade Scale: Pass-Fail for doctoral students. A-F for master students.
   Some Advanced Topics for Projects or Surveys (Preliminary List)
  • On the search for a Quantum PCP theorem.
  • Topological quantum field theories.
  • Quantum Fault Tolerance.
  • Simulation of Quantum Circuits.
   Course Material
  • A. Yu. Kitaev, A. H. Shen and M. N. Vyalyi: Classical and Quantum Computation
  • M. A. Nielsen and I. L. Chuang: Quantum Computation and Quantum Information.
  • N. D. Mermin: Quantum Computer Science, an Introduction
  • Links for the papers in which the course is being based will be posted soon.