
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:0012: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, DeutschJozsa's, BernsteinVazirani'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 nonAbelian 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 nonabelian 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.

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

TemperleyLieb Algebras

AharonovJonesLandau'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: PassFail for doctoral students. AF 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.
