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

Lecture Notes Complexity Theory

Lecture Notes Quantum Computing

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