1.1 Information ist physikalisch

Der Duden gibt folgende Definition für Information: »als räumliche oder zeitliche Folge physikalischer Signale, die mit bestimmten Wahrscheinlichkeiten oder Häufigkeiten auftreten, sich zusammensetzende Mitteilung, die beim Empfänger ein bestimmtes (Denk)verhalten bewirkt.« Wesentliche Beachtung verdient hier das Wort »physikalisch«. Information ist nicht nur ein abstrakter Begriff: Bei der Übertragung von Information erfolgt immer die Umsetzung einer Nachricht in ein physikalisches Medium. Beispielsweise benutzen Winnetou und Old Shatterhand u.a. optische Mittel (Rauch- oder Feuerzeichen) zur Informationsübertragung. Wenn man eine Nachricht spricht, so wird sie in akustische Wellen umgewandelt, die wiederum beim Zuhörer empfangen und über Ohr und Gehirn in ein Signal verwandelt und interpretiert werden. Bei der digitalen Informationsverarbeitung in einem Computer werden 0 und 1 durch eine hohe bzw. niedrige Spannung kodiert. Diese drei Beispiele betreffen drei wichtige Teilbereiche der Physik: Optik, Akustik und Elektrodynamik. Jede der beschriebenen Methoden hat Vor- und Nachteile, die durch die physikalische Implementation bedingt sind: z.B. ist die optische Informationsübertragung nur dann möglich, wenn kein Hindernis im Weg steht, die akustische nur dann, wenn nicht zu viel Hintergrundrauschen vorhanden ist.

Die bedeutsamste klassische Methode der Informationsverarbeitung ist sicherlich der Computer. Hier hat die Weiterentwicklung der Halbleitertechnologie zu immer kleineren Bauteilen und immer höheren Geschwindigkeiten geführt. In absehbarer Zeit wird man durch die Miniaturisierung der Bauteile an die Quantengrenze stoßen. Welche Neuerungen ergeben sich, wenn die Gesetze der Quantenphysik eine dominante Rolle bei der Informationsverarbeitung spielen?

Die weitreichenden Konsequenzen und vielfältigen neuen Möglichkeiten, die sich aus der Symbiose von klassischer Informationstheorie und Quantenphysik – der Quanteninformation – ergeben, werden erst seit den 90er Jahren des 20. Jahrhunderts intensiv erforscht. Da es sich um einen jungen Forschungsbereich handelt, der sich weiterhin rasant entwickelt, kann dieses Buch nur auf die grundlegenden Prinzipien der Quanteninformation eingehen und eine Momentaufnahme des derzeitigen Wissensstands liefern.

Bevor wir dazu kommen, jedoch zunächst eine Einführung in wichtige Konzepte der klassischen Informationstheorie.

1.2 Die Turingmaschine

Alan Turing entwickelte 1936 ein abstraktes Konzept eines Computers, die so genannte Turingmaschine. Sie kann alle Funktionen berechnen, die berechenbar sind. Die Elemente, aus denen sie besteht, sind die folgenden (siehe Abb. 1):

Eine Programmzeile gibt eine Vorschrift für einen gegebenen internen Zustand der Maschine und einen gegebenen Eintrag auf dem Band an. Diese Vorschrift besagt, ob der interne Zustand der Maschine geändert wird oder nicht, ob der Eintrag auf dem Band überschrieben wird oder nicht, und ob sich der Schreib- und Lesekopf danach einen Schritt nach rechts oder links bewegt.

Ein einfaches Beispiel für ein solches Programm ist das Auffinden der Parität einer gegebenen Folge von Nullen und Einsen. (Bei einer geraden Anzahl von Einsen spricht man von gerader, ansonsten von ungerader Parität.) Hierzu sei der interne Zustand der Maschine anfänglich 0. Der Lese- und Schreibkopf liest den jeweiligen Eintrag auf dem Band. Ist der Eintrag 1, so wird der interne Zustand der Maschine geändert, d.h. wenn er 0 war, wird er zu 1 und umgekehrt. Ist der Eintrag auf dem Band aber gleich 0, so bleibt der interne Zustand ungeändert. Danach rückt der Kopf einen Schritt nach rechts. Das Auftreten eines leeren Segments des Bandes bedeutet das Anhalten der Turingmaschine: Ist nun ihr interner Zustand 0, so hat die getestete Folge von Nullen und Einsen gerade, ansonsten ungerade Parität.

Über dieses abstrakte Konzept eines Computers kann die Komplexität von mathematischen Problemen definiert werden, wie im nächsten Kapitel erläutert. Das Modell der klassischen Turingmaschine kann ferner auf das Modell eines Computers erweitert werden, der auf quantenphysikalischen Prinzipien beruht – die Quanten-Turingmaschine.

1.3 Über die Komplexität von Problemen

Wie schwierig ist es, ein gegebenes mathematisches Problem zu lösen? Mit...