Computational Complexity and Physics
Fall term 2015. 3 hrs. lectures and 1 hr. exercises. 6 ECTS
points. Monday 14.0015.30 Library Insitute for Nuclear Physics, and Wednesday 16.0017.30 Room 0.01 THP New
Building.
Primary Areas of Specialization: ThSol (specialized course).
Lecturer: David Gross; Exercises: Richard Kueng.
Announcements

I talked on Nov 4th about the Graph Isomorphism problem. On the evening of Nov 4th, a significant advance in its theory has been
announced. Exciting times!
Course description
Complexity theory is a branch of theoretical computer science. It
provides quantitative statements about how hard it is to solve certain problems
on a computer. Examples of such problems include:
 Traveling Salesman: Find the shortest route through a given list of cities
 Integer Factorization:
Break the secure "https" internet communication protocol
 Ground State: Find the ground state energy of a physical spin system
Physics and complexity theory overlap in two distinct ways:
In principle, the laws of physics enable a computer to make arbitrary predictions about the behavior of physical systems. In practice, however, this often involves solving problems for which no efficient algorithms are known to exist. Complexity theory helps us to decide when the lack of efficient algorithms reflects an insurmountable, intrinsic difficulty of the problem, rather than our limited understanding.
Conversely, physics also contributes to complexity theory. The reason is that computers are physical systems themselves and what they can and cannot do is therefore ultimately a physical question. The task here is to decide whether the mathematical models employed by computer scientists faithfully capture all computational processes allowed for by Nature (the young theory of quantum computing indicates that this may not be the case).
Covered topics
 Complexity theory for physics
 Computable and uncomputable functions: Halting Problem, Kolmogorov Complexity, GĂ¶del's Incompleteness Theore
 Complexity classes: P, NP, NP completeness, BPP, P/poly
 Important decision problems: Satisfiability, cuts in graphs
 Hard problems in physics: ground state energies, partition functions, protein folding
 Physics for complexity theory
 ChurchTuring thesis, billiard ball computers, DNAcomputers
 Quantum computing: teleportation, DeutschJozsa algorithm, Shor's algorithm, BQP, QMA
 Existence of "true randomness" from Bell's argument
 Reversibility, entropy, Landauer principle, Maxwell's demon
Prerequisites
The quantum computing part requires basic knowledge of quantum mechanics. Beyond that, the course will be selfcontained.
Literature
Material
Some notes for students who want to prepare for the exam.
Exercises
There will be one exercise session instead of a lecture every second week (on
average). Generally, we'll aim to hold the exercise session every second
Monday. However, we'll start on Wednesday the 28th, as will have to cover some
material before it makes sense to hand out the first sheet.
Sheets:
 Exercise 1  due Wednesday, Oct. 28th before the tutorial at 4pm
 Exercise 2  due Wednesday, Nov. 11th before the tutorial at 4pm
 Exercise 3  due Monday, Nov. 30th before the tutorial at 4pm
 Exercise 4  due Monday, Jan. 11th
 Exercise 5  due Monday, Jan. 25th
 Exercise 6  due Wednesday, Feb. 10th