Summer 2012

Computational Complexity and Physics

Course description
(MSc, BSc, WP2; 10 ECTS points; lectures Mondays 2 pm - 4 pm FRIAS lecture theater, and Wednesdays 12:00 pm - 2 pm, SR 1, physics high rise; exercise session Mondays 12 pm, SR1.)

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
• Factoring: 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 Theorem, undecidable problems in quantum mechanics (first identified in 2011)
  • 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
  • Existence of "true randomness" from Bell's argument
  • Quantum computing: teleportation, Deutsch-Jozsa algorithm, Shor's algorithm, BQP, QMA
  • Church-Turing thesis, billiard ball computers, DNA-computers
  • 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
   

Hand-written notes

Some notes are available.

Exercises

Sheet 1 2 3 4 5 6 7 8 9 10

Participants who require a certificate that they have passed the exercises should contactFrau Kaiser.

Exam standards

Those who want to take the exam may find some guidelines here.

Quantum Coherence Seminar

The Quantum Coherence seminar takes place Thursdays 12:00 pm - 2:00 pm, HS 1, physics high rise.