Was ist ein Quantencomputer?

<<     >>

Durch Quantencomputer wird die rätselhafte Quantenmechanik dafür genutzt, um völlig neuartige berechnende Systeme bereit zustellen. Deshalb besitzen Quantencomputer Eigenschaften die schier unglaublich wirken: So steigert sich die Leistungsfähigkeit eines Quantencomputers zum Beispiel „explosionsartig“ mit zunehmender Größe. Schon sehr bald wird die Grenze der „Quanten-Überlegenheit“ überschritten werden. Die ersten Quantencomputer werden dann für bestimmte Berechnungen jeden herkömmlichen Supercomputer überflügeln. Und das ist erst der Anfang!

Der Paukenschlag: Der Shor-Algorithmus

Im Jahr 1994 hatte der Mathematiker Peter Shor vom renommierten Massachusetts Institute of Technology / MIT die Idee seines Lebens. Eine Idee, die eine neue Ära einleiten würde.

Shor untersuchte ein neues Verfahren, um eine ganze Zahl in Primzahlen zu zerlegen. Diese Primzahlfaktorisierung ist eine extrem aufwendige Angelegenheit. Um sehr großen Zahlen in Primzahlen zu zerlegen, brauchen selbst sehr leistungsstarke Supercomputer mehrere Jahre. i

Unter anderem deshalb wird sie für die sichere Datenverschlüsselung im Internet verwendet. Es ist zwar sehr einfach große Zahlen aus bekannten Primzahlen zusammenzusetzen (z.B. 7×13×13×17×53 = 1065883). Da die Umkehrung aber nahezu unmöglich ist, ist die Verschlüsselung im Internet bombensicher.

Eigentlich!

Shor fragte sich, ob man das neue Verfahren nutzen könnte, um neue Algorithmen für die Primzahlzerlegung zu erstellen. Irgendwann erinnerte er sich an eine Pflichtvorlesung über Quantenmechanik, die er seinerzeit als Mathematik-Student noch am California Institute of Technology (Caltech), hatte hören müssen. Ihm kam die grandiose Idee, dass das Verfahren ungleich schneller zum Ziel führen könnte, wenn man zur Berechnung nicht einen herkömmlichen Computer, sondern einen Quantencomputer verwenden würde. Er tüfftelte ein Jahr an seinem Quantenalgorithmus und kam am Ende tatsächlich zu dem gewünschten Ergebnis ii.

Shors Algorithmus schlug ein wie eine Bombe. Bis zu diesem Zeipunkt, war es noch niemanden gelungen einen Quantencomputer zu konstruieren. Der Shor-Algorithmus war aber der erste Beweis, wie ungeheuer leistungsstark ein Quantencomputer sein und welche gesellschaftlichen Auswirkungen er haben würde. Shors Algorithmus löste einen regelrechten Boom in den Quantencomputer-Szene aus.

Ein Quantencomputer macht sich die außergewöhnlichen Eigenschaften der atomaren Welt zu nutze, um über spezielle Quantenprogrammen, den Quantenalgorithmen, ganz neue Dimensionen in der Rechengeschwindigkeit zu erzielen. Das Wort „außergewöhnlich“ ist hierbei wohl stark untertrieben. Die Quantenwelt ist eine rätselhafte Welt mit schon fast magischen Eigenschaften.

Um einen Eindruck davon zu bekommen, was das Besondere an einem Quantencomputer ist, müssen wir uns erst einmal anschauen, wie ein herkömmlicher Computer funktioniert.

Wie funktioniert eigentlich ein herkömmlicher Computer?

Nehmen wir Ihren Computer, mit dem Sie diese Zeilen lesen. Er steuert Informationen in Form von Nullen und Einsen über Bits bzw. Bytes an. Die Zahl „71“ wird z.B. durch die Bit-Reihe „0100 0111“ dargestellt und der Buchstabe „J“, per Konvention, durch die Bit-Reihe „100 1010“. Ihr Computer merkt sich, ob eine Bit-Reihe eine Zahl, einen Buchstaben, ein Bild oder Musik darstellt. Die Bits selbst existieren in Form von Milliarden elektrischer An / Aus – Schalter, den Transistoren. Zusammen bilden sie den Arbeitsspeicher Ihres Computers. Ein guter herkömmlicher Computer besitzt etwa 16 * 8 Milliarden Bits oder anders ausgedrückt: 16 Gigabyte. Ein Computerprogramm manipuliert diese Bits in einzelnen Rechenschritten über die elementarsten Bausteine der menschlichen Logik: UND-Verknüpfungen, ODER-Verknüpfungen, NICHT-Verknüpfungen. Diese Verknüpfungen werden auch „Gatter“ genannt (englisch gates). Eine NICHT-Verknüpfung kehrt ein einzelnes Bit z.B. in sein Gegenteil um: NICHT 0 = 1, NICHT 1 = 0 .

Über geschickte elektrische Schaltungen, dem Datenbus, ist Ihr Computer in der Lage jedes der unzähligen Bits im Arbeitsspeicher gezielt anzusteuern, auszulesen oder mit neuen Werten zu überschreiben. Ein Rechenschritt sieht dann zum Beispiel so aus:

„Lese den Wert des Bits mit der Adress-Nummer 1543216 und den Wert des Bits mit der Adress-Nummer 6543 aus und verknüpfe beide Werte mit einem UND-Befehl. Speicher das Ergebnis im Bit mit der Adress-Nummer 789874“. Durch eine geschickte Hintereinanderreihung dieser elementaren UND-, ODER-, NICHT-Verknüpfungen ist Ihr Computer zum Beispiel in der Lage zwei Zahlen miteinander malzunehmen. Nach jedem einzelnen dieser Rechenschritte schreibt Ihr Computer die Zwischenergebnisse wieder in den Arbeitsspeicher hinein und ruft sie von dort wieder für den nächsten Rechenschritt auf. Das Programm für das Mal-Nehmen sieht unnötig umständlich und mechanisch stupide aus. Da Ihr Computer aber in der Lage ist Milliarden von Rechenschritten pro Sekunde auszuführen ist er jedem Menschen am Ende in solchen Aufgaben gigantisch überlegen.

Nun zum Quantencomputer: Die Qubits

Ein Quantencomputer steuert im Gegensatz dazu die Informationen nicht über einfache An / Aus-Schalter an, also den herkömmlichen Bits, sondern über sogenannte „Qubits“ (für Quanten-Bits). In einem Qubit sind die Werte 0 / 1 bzw. An / Aus gleichzeitig in einer überlagerten Form vorhanden. Das sieht auf den ersten Blick vielleicht harmlos aus. Tatsächlich ist diese Überlagerung eines der großen Rätsel der Quantenmechanik.

Die zweite so außergewöhnliche Eigenschaft von Qubits ist die Folgende. Selbst kleinste Mengen an Qubits in einem Quantencomputer können eine riesige Anzahl von Informationen gleichzeitig aufnehmen und verarbeiten: iii

  • 1 Qubit entspricht 2 herkömmlichen Bits
  • 2 Qubits entsprechen 4 herkömmlichen Bits
  • 10 Qubits entsprechen 16 herkömmlichen kilo-Byte
  • 20 Qubits entsprechen 16 herkömmlichen Mega-Byte
  • 30 Qubits entsprechen 16 herkömmlichen Giga-Byte
  • 31 Qubits entsprechen 32 herkömmlichen Giga-Byte

Jedes weitere Qubit verdoppelt also die Anzahl von gleichzeitig verwendbaren Informationen! Die Leistungsfähigkeit eines Quantencomputers steigt also exponentiell! Und so geht’s weiter:

  • 45 Qubits entsprechen in etwa der Speichergröße des größten aktuellen, herkömmlichen Supercomputers
  • 50 Qubits, die „Quanten-Überlegenheit“-Grenze: Die, zumindest theoretische, Grenze an dem ein Quantencomputer gewisse Berechnungen durchführen kann, die mit keinem der aktuellen Supercomputern durchführbar wären. iv Die Tech-Riesen leisten sich um genau diese Grenze gerade das große Wettrennen.
  • 250 Qubits: Die absolute Grenze die überhaupt machbar wäre für herkömmliche Computer. Um die Speichergröße eines 250 Qubit-Quantencomputers zu erreichen, müsste ein herkömmlicher Computer jedes Atom im Universum als herkömmliches Bit verwenden.

Das wirkt unglaublich. Ist es auch!

Und nun bedenken Sie mal, dass die Quantencomputer-Szene das Ziel hat irgendwann einmal Quantencomputer mit Millionen von Qubits zu bauen!

Quantenparallelismus: Die Superposition

Der Clou bei diesen ungeheuren Zahlen ist aber tatsächlich Folgender: Nehmen wir nochmal das Beispiel mit dem Mal-Nehmen. Ihr herkömmlicher Computer nimmt zwei Zahlen, in Form von zwei Bit-Reihen im Arbeitsspeicher, führt das festgelegte Programm von einzelnen Rechenschritten aus und erhält am Ende eine Zahl in Form von einer Bit-Reihe.

Ein Quantencomputer nimmt im Gegensatz dazu für eine Aufgabe zwei Qubit-Reihen, speichert die Zwischenergebnisse wieder in Qubits und erhält am Ende das Ergebnis in Form einer Qubit-Reihe v. Da in einer Qubit-Reihe aber riesige Mengen von Informationen gleichzeitig enthalten sein können (s.o.), kann der Quantencomputer das Programm letztendlich gleichzeitig mit einer riesigen Menge von Zahlen ausführen. Dies ist der Quantenparallelismus. Normalerweise spricht man aber von Superposition. Tatsächlich gibt diese Form von Überlagerung öfter in der Natur und nicht nur in der Quantenmechanik vi. Was den Quantenparallelismus so besonders macht ist die Tatsache, dass nur wenige Qubits so unvorstellbar große Datenmengen überlagern können. Die Qubits werden nämlich nicht nur einzeln überlagert, sondern der gesamte Verbund an Qubits. Und gerade dabei erhöht sich die Anzahl von möglichen Kombination so rasant. Für drei Qubits werden also z.B. bis zu acht mögliche Zustände gleichzeitig verwendet: Nämlich 000, 100, 001, 101, 011, 111, 010 und 110.

Einsteins spukhafte Verschränkung

Das vorangegangene Beispiel hat eine bizarre Konsequenz. Albert Einstein höchstpersönlich sagte sie 1935 in einem berühmten Aufsatz voraus: Die „Quanten-Verschränkung“ (engl. entanglement) oder „spukhafte Fernwirkung“, wie er das Phänomen nannte. Wir können zwei Qubits (oder auch mehrere Qubits) derart überlagern, dass wir sie nicht mehr als einzelne Qubits erkennen können. Stattdessen bilden sie eine völlig neuartige, einheitliche Zustandsform. Sie erscheinen „verschränkt“: Eine Messung am ersten Qubit hat sofort Auswirkungen auf das zweite Qubit.

Ziel von Einsteins Arbeit war es tatsächlich, der Quantenmechanik einen grundlegenden Denkfehler nachzuweisen. Laut Einstein müsste diese Einheit bestehen bleiben, selbst wenn die beiden Qubits Lichtjahre voneinander entfernt wären. Deshalb sprach er von Fernwirkung. Das Verrückte dabei ist: Alle Experimente deuten daraufhin, dass es genauso ist.

Solche verschränkte Zustandsformen gibt es nirgendwo sonst in den Naturwissenschaften. Vielleicht bis auf eine Ausnahme:

Ein sogenanntes astronomisches „Wurmloch“, das zwei schwarze Löcher über eine Distanz von vielen Lichtjahren miteinander verbinden kann, als eine Art Hyper-Schnellstraße. Inwiefern diese beiden Phänomen zusammenhängen werde ich in einem späteren Beitrag erläutern.

Aber: Jede Messung zerstört die Quanteneigenschaften

Die enorme parallele Rechenleistung eines Quantencomputers hat leider einen großen Haken: Sie funktioniert nur solange der Quantencomputer perfekt von seiner Umgebung isoliert ist und die Qubits ungestört sind. Indem wir am Ende allerdings das Ergebnis des Quantenprogramms aus den Qubits auslesen tun aber wir aber genau das. In diesem Moment „zerfallen“ die gleichzeitig vorhandenen Werte und übrig bleibt nur ein einziger Wert der darüber hinaus auch noch zufällig ist. Dieser Zerfall ist als „Kollaps der Wellenfunktion“ bekannt und ist noch so ein Mysterium der Quantenwelt. Er war der Grund, warum manche Physiker, unter ihnen auch Einstein, die Quantentheorie zwar schätzten aber im Grunde ablehnten „Gott würfelt nicht“.

Und jetzt? Was ist überhaupt gewonnen, wenn am Ende doch nur alles vom Zufall abhängt?

Jetzt kommt das Aber: Die Wahrscheinlichkeiten, mit denen die verschiedenen Werte am Ende ausgelesen bzw. gemessen werden, kann man beeinflussen. Die Kunst eines Quantenprogramms besteht unter anderem darin die Qubits, während der Quantencomputer noch isoliert ist, so zu manipulieren dass das gesuchte Ergebnis am Ende am Wahrscheinlichsten gemessen wird. Bis dahin kann dann die enorme Rechenpower des ungestörten Quantencomputers genutzt werden.

Quantengatter: Die Bausteine der Quantenprogramme

In einem Quantenprogramm verwendet der Quantencomputer in jedem Rechenschritt übrigens ebenfalls elementare Logik-Bausteine, den „Quantengattern“ (engl. quantum gates). Diese spiegeln allerdings nicht unsere normale, Alltags-Logik wieder, sondern die Quantenlogik: Somit heißen die elementaren Bausteine nicht mehr UND, ODER oder NICHT. Stattdessen verwendet ein Quantencomputer Logik-Bausteine die Hadamard, X, Y, Z und CNOT heißen. Dies ist unter anderem der Grund, warum ein Quantenprogramm nur für Kenner für Quantenalgorithmen lesbar ist und verstanden werden kann.

Für alle Darstellungen von Quantengattern verwende ich auf Quantencomputer-Info den exzellenten Quantencomputer-Simulator „Quirk“ von Craig Gidney.

http://algassert.com/quirk

Quirk ist öffentlich erreichbar und kann direkt im Browser ausprobiert werden.

Folgendes Beispiel zeigt den Grover-Algorithmus für zwei Qubits, den ich Ihnen in einem späteren Beitrag im Detail vorstellen werde:

 

 

In jedem Bereich der herkömmlichen Programmierung existiert eine lebhafte IT-Szene im Internet, die die weitere Entwicklung stark beeinflusst: Seien es Server, Netzwerke. Datenbanken, Internet, Programmierung, … Die IT-Szene für Quantenprogrammierung sitzt noch in den Forschungseinrichtungen von Universitäten und hauptsächlich in den Spezialabteilungen von Google, IBM, Microsoft, D-Wave & Co. Seit dem Frühjahr 2018 gibt es zwar das neue Diskussionsforum „Quantum Computing Stack Exchange“ vii, dass sich sehr lebhaft und inhaltlich hochwertig entwickelt. Wichtige Ergebnisse werden trotzdem weiterhin über komplizierte wissenschaftliche Arbeiten veröffentlicht.

Die wohl folgenreichste dieser Veröffentlichung war gerade der Algorithmus von Peter Shor, der in der Lage ist die als sicher geglaubte Datenverschlüsselung im Internet zu knacken. Mittlerweile wurden andere, rasend schnelle und wahrscheinlich interessantere Quantenalgorithmen konstruiert.

Teil des Shor-Algorithmus, Beispiel von der Quirk-Homepage: