# Complexity Theory and Quantum Computing

## WS 2009/10

### News

- The certificates about successful participation in the exercise classes for Diplom Students can be received at the secretary's office.
- Please contact Prof. Grädel by 28 January to make an appointment for the oral examination.
- The sixth chapter of the lecture notes has been completed.
- If you intend to participate in the exercise classes and hand in solutions to exercises, please take note of the information below.

### Schedule

Type | Date | Location | Organizer | ||||
---|---|---|---|---|---|---|---|

V4 | Mo | 10:00 | – | 11:30 | AH II | ab 19. Oktober | E. Grädel |

Do | 10:00 | – | 11:30 | AH V | ab 22. Oktober | E. Grädel | |

Ü2 | Mi | 15:00 | – | 16:30 | AH I | ab 28. Oktober | D. Fischer, T. Ganzow, B. Puchala |

### Assignments

The current assigment is made available on this website on Mondays. You can work on the exercises in groups of up to three students and hand in solutions by noon on the following Monday either in the box at the institute or after the lecture.

The first assigment will be issued on Monday, October 26, however the first tutorial is already given on Wednesday, October 28.

For Diplom students, the presentation of own solutions to the exercises is part of the assessment.

### Coursework

- Homework 1 [pdf] [ps]
- Homework 2 [pdf] [ps]
- Homework 3 [pdf] [ps]
- Homework 4 [pdf] [ps]
- Homework 5 [pdf] [ps]
- Homework 6 [pdf] [ps]
- Homework 7 [pdf] [ps]
- Homework 8 [pdf] [ps]
- Homework 9 [pdf] [ps]
- Homework 10 [pdf] [ps]
- Homework 11 [pdf] [ps]
- Homework 12 [pdf] [ps]

### Lecture Notes Complexity Theory

- All chapters [pdf] [pdf-2up]
- Chapter 1: Deterministic Turing Machines and Complexity Classes [pdf] [pdf-2up]
- Chapter 2: Nondeterministic complexity classes [pdf] [pdf-2up]
- Chapter 3: Completeness [pdf] [pdf-2up]
- Chapter 4: Oracles and the polynomial hierarchy [pdf] [pdf-2up]
- Chapter 5: Alternating Complexity Classes [pdf] [pdf-2up]
- Chapter 6: Complexity Theory for Probabilistic Algorithms [pdf] [pdf-2up]

### Lecture Notes Quantum Computing

- All chapters [pdf] [pdf-2up]
- Chapter 1: Introduction [pdf] [pdf-2up]
- Chapter 2: Universal Quantum Gates [pdf] [pdf-2up]
- Chapter 3: Quantum Algorithms [pdf] [pdf-2up]

### Content

#### Complexity Theory

Complexity theory classifies algorithmic problems according to the amount of ressources (like time, space, hardware, ...) that are necessary to solve them. In this lecture, we study the most important complexity classes for deterministic, nondeterministic, parallel, and probabilistic computations. Particular attention will be paid to the relationships between differrent computation models and to complete problems in the most relevant complexity classes.

#### Quantum Computing

You have nothing to do but mention the quantum theory, and people will take your voice for the voice of science, and believe anything.(George Bernard Shaw)

The development of Quantum Computers aims at exploiting quantum mechanical effects to build non-classical computing systems. While it is still unclear whether quantum computers with more than just a few qubits are physically realisable, at least in theory quantum phenomena allow for fundamentally new kinds of computations. Indeed, the theory of quantum computations, which has been developed during the last years, yields interesting and surprising results.

*Quantum Turing Machines* and *Quantum Gate Arrays*
serve as formal models of quantum computation,
which are probabilistic models of computation using
interference of configurations and transition rules
specified by probability amplitudes instead of probabilities.
We will analyse these models and investigate several algorithm
for quantum computers.
In particular, we will prove the prominent result of P. Shor
that the prime factorisation problem can be solved in polynomial
time on quantum computers. It is still an open question whether
this problem is efficiently solvable on classical machines,
and the currently used public-key crypto systems rely on its
assumedly higher (classical) complexity.

Because nature isn't classical, dammit...(Richard P. Feynman)

### Literature

#### Introductory literature on Complexity Theory

[1] | D. P. Bovet and P. Crescenzi. Introduction to the theory of complexity. Prentice Hall, New York, 1994. |

[2] | C. Papadimitriou. Computational complexity. Addison-Wesley, 1994. |

[3] | K. R. Reischuk. Einführung in die Komplexitätstheorie. Teubner, Stuttgart, 1990. |

#### Advanced literature on Complexity Theory

[1] | P. Bürgisser, M. Clausen, and M. Shokrollahi. Algebraic Complexity Theory. Springer-Verlag, 1997. |

[2] | J. Balcazar, J. Diaz, and J. Gabarro. Structural complexity. Springer-Verlag, 1988. |

[3] | R. Downey and M. Fellows. Parametrized complexity. Springer-Verlag, 1999. |

[4] | R. Greenlaw, H. J. Hoover, and L. Ruzzo. Limits to parallel computation: P-completeness theory. Oxford University Press, 1995. |

[5] | J. Hartmanis. Feasible computations and provable complexity properties. SIAM, Philadelphia, 1978. |

[6] | N. Immerman. Descriptive complexity. Springer-Verlag, 1999. |

[7] | D. Johnson. Handbook of Theoretical Computer Science (J. V. Leeuwen, ed.). Elsevier Science Publishers B.V., 1990. |

[8] | K. Wagner and G. Wechsung. Computational complexity. Reidel, 1986. |

[9] | I. Wegener. Grenzen der Effizienz von Algorithmen. Springer-Verlag, Berlin u.a., 2003. |

[10] | I. Wegener. The complexity of Boolean functions. Teubner, Stuttgart, 198. |

#### Literature on Quantum Computing

[1] | J. Gruska. Quantum Computing. McGraw-Hill, 1999. |

[2] | M. Hirvensalo. Quantum Computing. Springer, 2001. |

[3] | N. D. Mermin. Quantum Computer Science: An Introduction. Cambridge University Press, 2007. |

[4] | M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. |

### Prerequisites

- Basic knowledge of computability and complexity theory
- Linear Algebra

### Classification

- Mathematik (D): Reine Mathematik
- Mathematik (B.Sc.): 5./6. Semester
- Informatik (D): Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
- Informatik (B.Sc.): Wahlpflicht Theoretische Informatik
- Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
- Software Systems Engineering (M.Sc.): Theoretical Computer Science

### Assessment

- Bachelor- and Master studies: Solving 50% of the exercises and final oral examination
- Diploma studies: Solving 50% of the exercises and active participation in the exercise classes

### Contact

Erich Grädel, Diana Fischer, Tobias Ganzow, Bernd Puchala