Course Identification

Basic knowledge in theoretical computer science (computability, computational complexity, algorithms, boolean circuits, at undergraduate level).

Proficiency in linear algebra (vectors, vector spaces, operators, norms, projections, tensor products, the trace operator).

Proficiency in probability theory (probabilities, expectation, random variables, distributions, statistical distance).

Basic knowledge in algebra (groups, generators).

Important: Proficiency in LaTeX. Homework is required to be written in LaTeX and be adequately readable.

Quantum computing and quantum information theory provide tools to analyze quantum systems at a level of abstraction beyond their particular physical properties. This allows to analyze the computational capabilities and the information theoretic properties of a system regardless of the underlying physics. Therefore the theory of quantum computing is useful for analyzing computational devices that rely on quantum systems (a.k.a quantum computers) but also in understanding the basic principles that govern any quantum system and thus (presumably) the universe.

Our approach will be rigorous and quantitative. We will in general provide mathematical proofs for claims that are made. A similar level of rigor will be required in the homework.

We will not touch upon physics or engineering aspects such as the construction of quantum computers.

Time permitting we will touch upon the following aspects:

Quantum states, distributions over states, density matrices.

Measurements and their meaning in terms of quantum information.

The quantum circuit model and its properties.

Quantum non locality and its implications.

The quantum Fourier transform.

Basic quantum algorithms.

Quantum complexity theory and complexity classes.

The ability to describe a quantum system as an evolution of the state density matrix.

Familiarity with basic quantum information theoretic and algorithmic techniques.