Quest 5: Virtuose Algorithmen

Einer der Hauptgründe, warum wir die Quanteninformatik erforschen, ist, dass Quantencomputer manche Probleme viel schneller lösen können, als alle uns aktuell zur Verfügung stehenden Computer. Um Quantencomputer von normalen Computern zu unterscheiden, verwenden wir den Begriff klassischer Computer für all jene Computer, die wir zurzeit haben. Das beinhaltet deinen Laptop oder PC, sehr kleine Computer wie dein Smartphone oder eine Smartwatch sowie auch sehr große und leistungsstarke Supercomputer die so groß wie ganze Räume sein können. Was all diese Computer von Quantencomputern unterscheidet ist nicht ihre Größe oder Rechengeschwindigkeit, sondern dass ihre internen Funktionen durch klassische Physik (genauer gesagt Elektromagnetismus) beschrieben werden können. Ihre Hardware funktioniert also auf eine Art und Weise, die mit alten physikalischen Theorien beschrieben werden, die es schon viel länger als die Quantenphysik gibt. Das ist in etwa so, wie die von Mozart und Bach komponierte Musik als klassische Musik bezeichnet wird. Genau wie bei klassischen Computern werden auch in der klassischen Musik keine modernen Musikinstrumente wie E-Gitarren oder Synthesizer benutzt.

Aufgrund der Hardware, die klassische Computer nutzen, werden alle Informationen die sie speichern – sei es ein Bild, eine Tondatei, ein Video oder eine Website – durch Bitstrings, also eine Folge von Nullen und Einsen, dargestellt. Diese Informationen werden dann entsprechend einiger Regeln so verarbeitet, dass das Ergebnis eine sinnvolle Antwort darstellt. Wir nennen diese Folge von Befehlen einen Algorithmus. Du kannst dir einen Algorithmus vorstellen wie ein Rezept – wenn du den enthaltenen Anweisungen genau folgst, erhältst du das gewünschte Ergebnis, zum Beispiel Schokoladen-Brownies! Ein Algorithmus könnte zum Beispiel zwei Bitstrings als Eingabe nehmen und einen anderen Bitstring ausgeben, der die Summe der ersten beiden Bitstrings (als Zahlen interpretiert) enthält. Genau wie Rezepte wurden auch Algorithmen ursprünglich von Menschen ausgeführt. Tatsächlich bezeichnet das Wort Computer (engl. für “Rechner:in”) ursprünglich eine Person, die rechnet. Heutzutage werden Algorithmen aber auf echten Computern ausgeführt. Da Computer selbst nicht besonders intelligent sind, müssen diese Algorithmen ihnen sehr genau beschrieben werden. Diese Beschreibung, ein Programm, ist eine konkrete Umsetzung (Implementierung) des abstrakten Algorithmus, sodass der Computer sie verstehen kann. Dafür müssen wir eine Programmiersprache benutzen, die der Computer selbst in Operationen auf Nullen und Einsen übersetzen kann, um sie dann anschließend auf der Hardware auszuführen.

Wenn du einen Algorithmus entwirfst, ihn in deinen Computer einprogrammierst und ausführst, möchtest du die Antwort in einer angemessenen Zeit erhalten. Wie lange es aber tatsächlich braucht, um die Lösung zu berechnen, hängt von vielen Faktoren ab:

1. 1.
   ​

   wie schnell dein Computer elementare Operationen ausführen kann,

2. 2.
   ​

   ob die Eingabe deines Programms von der Festplatte, aus einer Netzwerkverbindung oder direkt vom Speicher ausgelesen wird,

3. 3.
   ​

   welche Programmiersprache du für dein Programm genutzt hast (und die Version des Kompilers oder Interpreters, der das Programm ausführt),

und so weiter. Das macht es sehr schwer, verschiedene Algorithmen zu vergleichen.

Um verschiedene Algorithmen besser vergleichen zu können, betrachten Informatiker:innen nicht, wie lange das Ausführen auf einem bestimmten Computer dauert. Stattdessen zählen sie, wieviele elementare Operationen der Algorithmus ausführt. So können sie sichergehen, dass sie die Algorithmen selbst vergleichen und nicht die Computer, auf denen die Algorithmen laufen (sonst könnte ein guter Algorithmus auf einem langsamen Computer schlechter aussehen, als ein schlechter Algorithmus auf einem schnellen Computer). Genauer gesagt interessiert Informatiker:innen wie die Anzahl der Operationen mit der Größe des Problems, das der Algorithmus lösen soll, wächst. Denn je mehr Daten verarbeitet werden müssen, desto länger braucht der Algorithmus, egal wie gut er ist. Man will also wissen, ob der Algorithmus in der Lage ist, mit sehr großen Datenmengen umzugehen. Dieser Forschungsbereich wird auch Komplexitätstheorie genannt.

In der Quanteninformatik sind wir daran interessiert, Quantenalgorithmen zu entwerfen, welche Rechenprobleme lösen, indem sie Quantenzustände anstelle von Bitstrings manipulieren. Die elementaren Anweisungen dabei sind Gatter, wie das Hadamard-Gatter, das kontrollierte-NOT-Gatter oder eine Messung. Wir werden diese Quantenalgorithmen bildlich durch Quantenschaltungen darstellen, die du schon oft in Quirky erstellt hast. Es ist aber auch möglich, eine textuelle Darstellung zu verwenden, wie man sie von einem üblichen Computerprogramm erwarten würde. Zum Beispiel entspricht die Quantenschaltung auf der linken Seite dem rechten Programmtext:

CNOT q1 -> q2;
H q1;

wobei q1und q2 sich auf die zwei Qubits bezeichnen (bedenke, dass der untere Draht dem ersten Qubit entspricht). Gegeben eines Rechenproblems können wir dann vergleichen, wie viele elementare Operationen die besten bekannten klassischen- und Quantenalgorithmen jeweils benötigen, um das Problem zu lösen. So können wir den Vorteil zukünftiger Quantencomputer gegenüber klassischen Computern besser verstehen.