Computational Complexity and Physics

Fall term 2015. 3 hrs. lectures and 1 hr. exercises. 6 ECTS points. Monday 14.00-15.30 Library Insitute for Nuclear Physics, and Wednesday 16.00-17.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
  • Church-Turing thesis, billiard ball computers, DNA-computers
  • Quantum computing: teleportation, Deutsch-Jozsa 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 self-contained.

Literature

• Arora & Barak, Computational complexity: a modern approach
• Feynman, Lectures on Computation
• Nielsen & Chuang, Quantum Information and Quantum Computation
• More to be announced

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:

1. Exercise 1 -- due Wednesday, Oct. 28th before the tutorial at 4pm
2. Exercise 2 -- due Wednesday, Nov. 11th before the tutorial at 4pm
3. Exercise 3 -- due Monday, Nov. 30th before the tutorial at 4pm
4. Exercise 4 -- due Monday, Jan. 11th
5. Exercise 5 -- due Monday, Jan. 25th
6. Exercise 6 -- due Wednesday, Feb. 10th