| Hardware | Quantencomputing

Quantencomputing

Definition und Abgrenzung

Die Informatik beschäftigt sich mit der algorithmischen Lösung von Problemen, wie etwa dem Suchen in einer unsortierten Liste oder der Zerlegung einer Ganzzahl in ihre Primfaktoren. Problemen wird hierbei eine sogenannte Laufzeitkomplexität zugewiesen. Das ist die Anzahl an Rechenschritten, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Für einige Probleme ist die Laufzeitkomplexität bekannt, wie zum Beispiel die Suche in einer unsortierten Liste, für andere hingegen nicht, wie etwa die Primfaktorzerlegung.

Ist ein optimaler Algorithmus zu einem Problem gefunden, so gibt es bislang keine Möglichkeit, die Berechnung der Lösung weiter zu beschleunigen, mit Ausnahme der Skalierung der Hardware. Doch aufgrund des absehbaren Endes von Moore’s Law, also der Verdopplung der Transistoren auf einem Mikrochip alle zwei Jahre, ist auch die Hardwareskalierung in Zukunft nicht mehr in diesem Maße möglich.

Hier kommt nun das Quantencomputing ins Spiel. Die Theorie lautet, dass mithilfe quantenmechanischer Berechnung manche Probleme in einer niedrigeren Laufzeitkomplexität zu lösen sind als mit einem klassischen Computer. Diese theoretische Quantenüberlegenheit wurde bisher allerdings nur für wenige Probleme bewiesen, so etwa für die Suche in einer unsortierten Liste mithilfe des Grover-Algorithmus [1]. Für andere Probleme wird aktuell eine theoretische Quantenüberlegenheit vermutet, etwa für die Primfaktorzerlegung mit dem Shor-Algorithmus [2].

Der Quantencomputer nutzt für seine Berechnungen mehrere quantenmechanische Phänomene wie etwa die Superposition und die Verschränkung.

Während ein klassisches Bit entweder im Zustand 0 oder im Zustand 1 sein kann, kann sich ein Quanten-Bit (kurz: Qubit) in einer Superposition dieser beiden Zustände befinden. Es ist dann zum Beispiel zu 25 % im Zustand 1 und zu 75 % im Zustand 0. Erst bei der Messung kollabiert das Qubit auf einen der zwei Zustände, und zwar genau mit der Wahrscheinlichkeit, in der es sich in dem Zustand befand. Also bei der Messung des obigen Qubits würde man mit einer Wahrscheinlichkeit von 25 % den Zustand 1 messen und mit einer Wahrscheinlichkeit von 75 % den Zustand 0. Wenn man also denselben Algorithmus auf dieselbe Eingabe anwendet, kann man unterschiedliche Ergebnisse erhalten. Die Berechnung mit einem Quantencomputer ist also probabilistisch.

Die Verschränkung ist eine Eigenschaft von Quantenobjekten: Mehrere Objekte verbinden sich so miteinander, dass sie nicht mehr als eigenständige Objekte betrachtet werden können, sondern nur noch als ein gemeinsames Objekt. Dadurch wird der Zustandsraum exponenziert. Denn während ein einzelnes Qubit sich in einer Superposition von zwei Zuständen befinden kann, kann ein aus zwei Qubits bestehendes (verschränktes) Quantenregister nun in einer Superposition von 4 Zuständen sein, ein 3-Qubit-Register dann aus 8 und so weiter. Ein Quantenregister mit N Qubits kann sich also in einer Superposition von 2Zuständen befinden.

Mithilfe von Gattern können die Gewichte der einzelnen Zustände (auch Amplituden genannt), also aus dem obigen Beispiel die 25 % und die 75 %, verändert werden. Der Clou ist nun, dass durch ein einzelnes Gatter die Amplituden aller 2Zustände gleichzeitig verändert werden können. Dadurch ist theoretisch ein exponentieller Speed-up gegenüber einer klassischen Berechnung möglich. Das Ziel eines Quantenalgorithmus ist nun stets, die Amplitude des gesuchten Zustandes durch eine geeignete Abfolge von Gattern zu vergrößern (natürlich ohne diesen Zustand zu kennen), sodass bei der Messung die Wahrscheinlichkeit des Kollapses auf diesen Zustand erhöht ist.

Geschichte

Die Anfänge des Quantencomputings reichen zurück bis in die frühen 1980er-Jahre. In dieser Zeit entwickelten Pioniere wie der amerikanische Physiker Paul Benioff [3] oder der russische Mathematiker Yuri Manin erste Konzepte für das Quantencomputing [4]. Auch Richard Feynman erkannte das Potenzial und die Notwendigkeit des Quantencomputings zur Simulation von physikalischen Prozessen. Legendär ist insbesondere sein berühmter Satz: „Wenn Sie eine Simulation der Natur bauen wollen, dann sollte sie besser quantenmechanisch sein, und, ei der Daus, plötzlich ist das ein wunderbares Problem, weil es ganz und gar nicht einfach aussieht.“ [5]

Die ersten bahnbrechenden Quantenalgorithmen wurden Mitte der 1990er-Jahre entwickelt. Angefangen mit Peter Shor, der einen Algorithmus zur Primfaktorzerlegung präsentierte, für die es bis heute keinen effizienten klassischen Algorithmus gibt. Da die Schwierigkeit der Primfaktorzerlegung der wesentliche Grundpfeiler für die Sicherheit der RSA-Verschlüsselung ist, hätte ein ausreichend großer Quantencomputer ernsthafte Konsequenzen für deren Sicherheit. Allerdings sind die derzeit zur Verfügung stehenden Quantencomputer viel zu klein und zu fehleranfällig, als dass sie RSA gefährden könnten. Zwei Jahre nach Shor entwickelte Lov Grover den Grover-Algorithmus zur quadratisch beschleunigten Suche in unsortierten Datenbanken.

Es folgte eine längere Phase ohne große neue Entwicklungen, bis in den letzten Jahren zahlreiche große Techunternehmen, wie etwa Google, Microsoft, IBM oder Amazon, in die Entwicklung von Quantencomputern einstiegen. Im Jahr 2019 war es dann so weit: der Beweis der sogenannten Quantenüberlegenheit [6]. Der Beweis also, dass ein Quantencomputer eine bestimmte Aufgabe schneller lösen kann als jeder klassische Computer. Sycamore, der Quantencomputer von Google, war in der Lage, eine spezielle Aufgabe zu lösen, für die der derzeit beste klassische Supercomputer schätzungsweise über 10.000 Jahre brauchen würde.

Anwendung und Beispiele

Das Quantencomputing ist trotz seiner zahlreichen Erfolge nach wie vor in der Entwicklungsphase. Das Problem, für das Google eine Quantenüberlegenheit gezeigt hat, ist sehr speziell und hat wenig praktische Relevanz. Für praktisch relevante Probleme, wie etwa die Primfaktorzerlegung, sind die derzeit zur Verfügung stehenden Quantencomputer noch zu klein und fehleranfällig.

Sind die Hardwareprobleme des Quantencomputings aber erst einmal gelöst, so eröffnet sich eine Vielzahl von Anwendungsgebieten, zum Beispiel die Entwicklung neuer Medikamente [7], wo der Quantencomputer bei der Simulation von Molekülen eingesetzt wird. Weitere Anwendungsgebiete sind unter anderem die Unterstützung des Maschinellen Lernens [8] und die beschleunigte Lösung von Optimierungsproblemen [9, 10].

Kritik und Probleme​​

Es gibt bereits eine Fülle von Quantenalgorithmen, jedoch mangelt es bislang an ausreichend guten Quantencomputern. Als Probleme sind hierbei insbesondere die schlechte Skalierbarkeit (geringe Anzahl Qubits), die Fehleranfälligkeit der Qubits (Relaxation) und die geringe Kohärenzzeit zu nennen, also der Verlust der Superposition.

Auch wurde bisher nur für wenige Quantenalgorithmen bewiesen, dass sie eine geringere Laufzeitkomplexität besitzen als ihre klassischen Äquivalente.

Forschung

Es wird derzeit an mehreren Ansätzen geforscht, wie die Qubits physikalisch realisiert werden. Die drei wichtigsten davon sind die Ionenfallen, Photonen und die Supraleiter.

Bei den Ionenfallen dient ein einzelnes Atom als Qubit. Hat das Atom nicht gleich viele Elektronen wie Protonen, so ist es elektrisch geladen (ein Ion) und kann daher mit elektrischen Feldern räumlich fixiert werden. Darüber hinaus haben Atome mehrere sogenannte Energieniveaus, also diskrete energetische Zustände. Fügt man einem im ersten Energieniveau befindlichen Atom genau die Energiedifferenz zu, zum Beispiel mittels eines Lasers, so springt es vom ersten Energieniveau in das zweite. Die zwei Energieniveaus dienen bei dieser Art des Quantencomputings als die beiden möglichen Zustände des Qubits.

Bei einem Photonen-Quantencomputer werden die Qubits durch Photonen realisiert. Hierbei wird die fundamentale Eigenschaft von Quantenobjekten genutzt, dass sie sowohl als Teilchen als auch als Welle betrachtet werden können. Als orthogonale Zustände für die Qubits werden nun senkrecht aufeinanderstehende Polarisationen der Photonen (also der Wellen) verwendet.

Bei der Supraleiter-Technologie wiederum werden die Qubits durch elektrische Ströme in widerstandslosen (also supraleitenden) Chips repräsentiert. Sycamore, der Quantencomputer von Google, verwendet diese Art des Quantencomputings [6].

Jede dieser Technologien hat ihre Vor- und Nachteile. Welche Technologie sich am Ende durchsetzen wird, kann heute noch nicht vorhergesagt werden. Neben der Hardware wird auch an neuen Quantenalgorithmen geforscht, ebenso wie an neuen „post-Quanten“ Verschlüsselungsverfahren [11] für den Fall, dass RSA irgendwann unsicher wird.

Weiterführende Links und Literatur​​​​

Standardwerke zur Einführung in das Quantencomputing:

  • Quantum Computing verstehen, M. Homeister
  • Quantum Computation and Quantum Information, M. A. Nielsen and I. L. Chuang

Cloudzugriff auf die Quantencomputer von IBM:

Quellen

[1] A fast quantum mechanical algorithm for database search, L. K. Grover, 1996

[2] Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, P. W. Shor, 1996

[3] https://scholar.google.com/citations?user=3LWI7NkAAAAJ&hl=en

[4] Computable and Uncomputable (in Russian), Y. Manin, 1980

[5] Simulating Physics with Computers, R. P. Feynman, 1982

[6] Quantum Supremacy Using a Programmable Superconducting Processor, F. Arute et al., 2019

[7] https://www.boehringer-ingelheim.com/press-release/partnering-google-quantum-computing

[8] Overview on Quantum Computing and Its Applications in Artificial Intelligence, N. Abdelgaber and C. Nikolopoulos, 2020

[9] A Cross-Disciplinary Introduction to Quantum Annealing-based Algorithms, S. E. Venegas-Andraca et al., 2018

[10] A Quantum Approximate Optimization Algorithm, E. Farhi, J. Goldstone and S. Gutmann, 2014

[11] Intuitive Understanding of Quantum Computation and Post-Quantum Cryptography, Q. T. M. Nguyen, 2020