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
Primary Areas of Specialization: ThSol (specialized course).
Lecturer: David Gross; Exercises: Richard Kueng.
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!
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).
- 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
The quantum computing part requires basic knowledge of quantum mechanics. Beyond that, the course will be self-contained.
Some notes for students who want to prepare for the exam.
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.
- 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