Programmieren eines Quantencomputers: Generieren echter Zufallszahlen

Computer sind deterministische, vorhersehbare Maschinen und so konstruiert, dass sie Anweisungen auf wiederholbare Weise blind folgen. Diese Art von Computern hat uns im Verlauf des letzten Jahrhunderts natürlich außerordentlich geholfen, aber dieses Design weist einen fundamentalen Mangel auf: Es kann keine zufälligen Operationen ausführen¹. Zufallszahlengeneratoren sind heutzutage ein äußerst wichtiger Bestandteil vieler Anwendungen, aber obwohl die von ihnen generierten Zahlen zufällig genug sind, sind sie „pseudo“ zufällig und können oft vorhergesagt oder in irgendeiner Weise rückentwickelt werden.

Heutzutage ist es möglich, die seltsame, unvorhersehbare Natur subatomarer Teilchen zu nutzen und damit Berechnungen in einem Quantencomputer durchzuführen. Mit nur wenigen Codezeilen können wir einen echten Quantencomputer programmieren, um echte Zufallszahlen für uns zu generieren. Was bisher mit einem klassischen Computer auf Turing-Basis nicht möglich war.

Zufallsgeneratoren heute

In den meisten gängigen Programmiersprachen ist eine Art Zufallszahlengenerator für Entwickler integriert. Diese Generatoren nehmen im Allgemeinen einen Input-Startwert, der das aktuelle Datum und die aktuelle Uhrzeit darstellt, verschlüsseln diesen Wert mithilfe eines Algorithmus und geben einen Wert aus, der sich so von der Eingabe unterscheidet, dass wir ihn als zufällig betrachten. Die Scrambling-Funktion ist ein vorhersagbarer Algorithmus mit einem hohen Entropiebetrag (bei einer kleinen Änderung der Eingabe wird eine große Änderung der Ausgabe zurückgegeben), und es wird jedes Mal eine andere Zahl ausgegeben, da sich der Eingabesamen mit der Zeit ändert. Für fast alle praktischen Anwendungen funktioniert dieses System perfekt, aber da es ein vorhersehbares System ist, ist es nicht wirklich zufällig.

Nehmen wir als Beispiel den Zufallszahlengenerator von Javascript. Da Javascript eine Sprache ist, die in verschiedenen Umgebungen (Browser oder node.js) interpretiert wird, muss der Interpreter zunächst entscheiden, welche Algorithmen verwendet werden sollen, die der ECMAScript-Spezifikation entsprechen. Heutzutage verwenden die meisten modernen Browser denselben Zufallsalgorithmus, um die Math.random () - Funktion von Javascript mit dem Namen xorshift128 + zu aktivieren.

Hier ist eine allgemeine Version dieses in C² geschriebenen Algorithmus:

Der Zweck dieses Codes besteht darin, eine Eingabe (den Startwert) zu nehmen und in einem solchen Ausmaß zu verschlüsseln, dass zwei beliebige Ausgaben der beiden separaten Eingaben völlig unterschiedlich und daher zufällig erscheinen. Der Algorithmus erreicht dies, indem er die Binärdarstellungen des Startwerts nach oben und unten verschiebt und die Bitdarstellungen zwischen den Schritten umkehrt, was zu einer Bitdarstellung einer Zahl führt, die sich vollständig von der Eingabe des Startwerts unterscheidet.

Damit diese Funktion bei jedem Start unterschiedliche Ergebnisse liefert, benötigen wir einen sich ständig ändernden Startwert. Browser (und andere Programmiersprachen) verwenden häufig einfach eine numerische Darstellung des aktuellen Datums und der aktuellen Uhrzeit³, beispielsweise die UNIX-Epochenzeit, die Anzahl der Millisekunden, die seit dem 1. Januar 1970 vergangen sind⁴.

Mit diesem Keim und dem obigen Algorithmus für hohe Entropie können wir einen sehr überzeugenden Zufallszahlengenerator erzielen. Computersysteme verwenden diese Funktionen die ganze Zeit ohne Probleme, aber wir können es nicht als echten Zufallsgenerator bezeichnen. Wenn jemand weiß, wie der Zufallszahlengenerator funktioniert, und den Eingabesamen vorhersagen kann, kann er auch die Ausgabe der Funktion vorhersagen. Eine Möglichkeit, die Zufälligkeit dieses Systems zu verbessern, besteht darin, die Vorhersage des Samens zu erschweren. Beispielsweise verwenden viele Systeme die kosmische Mikrowellen-Hintergrundstrahlung (die elektromagnetischen Funkwellen, die der Urknall noch übrig lässt) als Keim, da niemand vorhersagen kann, wie sich dieses Hintergrundrauschen zu einem bestimmten Zeitpunkt verhält.

Ein Zufallssystem, das einen unvorhersehbaren Keim wie den Mikrowellenhintergrund verwendet, ist derzeit nach heutigem Kenntnisstand völlig zufällig. Derzeit kann niemand vorhersagen, wie sich dieser Startwert zu einem bestimmten Zeitpunkt verhalten wird, und kann daher die von ihm erzeugte Zufallszahl nicht vorhersagen. Diese Art von Samen kann in Zukunft möglicherweise nicht mehr vorhergesagt werden, aber wenn wir den kosmischen Mikrowellenhintergrund mit einem anderen messen und ihn als Eingabe für den Zufallszahlengenerator verwenden, können wir deren Ergebnis vorhersagen .

Um eine wirklich zufällige Zahl zu generieren, müssen wir etwas in der Natur finden, das wir nicht perfekt vorhersagen können, etwas, das nur durch Wahrscheinlichkeit beschrieben werden kann. Man glaubte, dass dies bis zum Beginn des 20. Jahrhunderts nicht existierte, aber die Theorie der Quantenmechanik öffnete Türen zu einer noch seltsameren und unvorhersehbaren Welt.

Wahrscheinlichkeit in der Quantenwelt

Die Quantenmechanik ist eine Theorie, die die Natur von Teilchen auf der subatomaren Skala beschreibt. Es heißt, wenn wir die Welt in immer kleinerem Maßstab betrachten, werden klassische Beschreibungen von Teilchen und Kräften, wie sie im 18. Jahrhundert von Sir Isaac Newton definiert wurden, ungenauer, und wir müssen zu unterschiedlichen, statistisch und wahrscheinlichkeitsgetriebenen Quantenbeschreibungen übergehen. Zum Beispiel kann die genaue Position eines Elektrons um ein Atom nicht vorhergesagt werden, wir können nur die Wahrscheinlichkeit vorhersagen, ein Elektron in einem bestimmten Bereich um das Atom zu einem bestimmten Zeitpunkt zu finden.

Um die Dinge noch merkwürdiger zu machen, besagt die Kopenhagener Interpretation der Quantenmechanik von Niels Bohr und Werner Heisenberg, dass Quantensysteme vor der Messung keine bestimmten Eigenschaften haben, sondern in allen möglichen Zuständen gleichzeitig nach einem Prinzip existieren, das als Überlagerung bekannt ist. Nur wenn das System beobachtet wird, kollabiert die Überlagerung und das System existiert in einem einzigen bestimmten Zustand. Dies wird als Beobachter-Effekt bezeichnet. Am Beispiel der Position eines Elektrons lässt sich die Wahrscheinlichkeit vorhersagen, dass sich ein Elektron zu einem bestimmten Zeitpunkt an einem bestimmten Ort befindet. Vor dieser Messung befindet sich das Elektron jedoch an allen möglichen Positionen um das Atom herum. Während der Messung zeigt sich, dass sich das Elektron an einem Ort befindet. Durch Beobachtung und Messung des Elektrons haben wir jedoch seinen Zustand geändert und können andere Eigenschaften wie den Impuls aufgrund des Unsicherheitsprinzips nicht bestimmen.

Diese Interpretation der Quantenwelt erschütterte damals verständlicherweise die Physik und wird bis heute diskutiert. Einstein weigerte sich zu glauben, dass die Realität von der Wahrscheinlichkeit bestimmt wird und sagte: „Ich bin jedenfalls davon überzeugt, dass Er (Gott) keine Würfel wirft“ und „Glaubst du wirklich, der Mond ist nicht da, wenn du nicht hinschaust? daran?". Als Antwort antwortete Niles Bohr später: "Einstein, sag Gott nicht, was zu tun ist."

Ob es Ihnen gefällt oder nicht, die Quantentheorie bleibt unser bestes Verständnis der subatomaren Welt und wurde zum Herzstück eines völlig neuartigen Informationsprozessors entwickelt. Quantencomputer verlassen sich auf die Fähigkeit von Quantenteilchen, in einer Überlagerung mehrerer Zustände gleichzeitig zu existieren, um Berechnungen durchzuführen. Da Quantencomputer die Überlagerungen von Partikeln manipulieren können, die von der Wahrscheinlichkeit bestimmt werden, können wir sie als Werkzeug verwenden, um die Natur der Quantenwelt zu nutzen und einen echten Zufallszahlengenerator aufzubauen.

Qubits und Quantentore

Klassische Computer verwenden Binärziffern oder Bits, um Informationen darzustellen. Ein Bit kann die Werte 0 oder 1 annehmen und wird durch einen von zwei Gleichspannungspegeln in einem Computerprozessor dargestellt. Quantencomputer stellen Informationen normalerweise auf die gleiche Weise mit einem 0- oder 1-Bit dar, aber sie implementieren diese Zustände physikalisch unter Verwendung der binären Eigenschaften von subatomaren Partikeln. Diese Eigenschaften können der Spin eines Elektrons (Spin up und Spin down) oder die Polarisation eines Photons (horizontale und vertikale Polarisation) sein. Jede dieser Darstellungen kann durch die Quantenmechanik beschrieben werden und beide Zustände gleichzeitig überlagern. Dies bedeutet, dass ein Quanten-Informationsbit oder Qubit in einer Überlagerung beider Zustände 0 und 1 gleichzeitig existieren kann. Um das Ergebnis einer Berechnung zu messen, müssen wir den Quantenzustand im Computer messen und diese Teilchen zwingen, einen 0- oder 1-Zustand zu wählen.

Um Qubits in einem Quantencomputer zu manipulieren, verwenden wir Quantentore ähnlich den Toren einer klassischen Schaltung. Während ein klassischer Computer Operationen an Bits ausführen kann, beispielsweise das Umkehren auf ihren entgegengesetzten Wert, können Quantentore diese Operationen ausführen und fortgeschrittenere Quantenoperationen, beispielsweise das Verschieben eines Qubits in eine Überlagerung beider möglicher Werte. Ein Gatter, das ein Qubit in eine Überlagerung drückt, wird Hadamard-Gatter genannt und ist eines der grundlegendsten und am häufigsten verwendeten Logikgatter im Quantencomputing¹⁰.

Wenn wir den Spin eines Elektrons in eine Überlagerung der beiden möglichen Spin-Up- und -Down-Zustände bringen, die die Werte 1 und 0 eines Qubits darstellen, kann gesagt werden, dass das Elektron einen gleichzeitigen Spin beider Werte hat und das Qubit sich in einer Überlagerung befindet von 0 und 1. Wenn wir dieses Qubit messen, kollabieren wir die Überlagerung und zwingen sie in einen dieser beiden möglichen Zustände, von denen jeder mit gleicher Wahrscheinlichkeit¹¹ auftritt. Bei jeder Überlagerung und Messung haben wir eine 50% ige Chance, entweder 1 oder 0 zu messen. Wir hätten dann das Äquivalent eines Münzwurfs unter Verwendung der Grundgesetze der subatomaren Welt durchgeführt.

Um unsere Zufallszahl aus einem Quantenmünzwurf zu generieren, müssen wir nur Folgendes tun:

  1. Holen Sie sich ein Qubit mit einem vordefinierten Status. Entweder 0 oder 1 reicht aus.
  2. Zwinge dieses Qubit mit einem Hadamard-Tor in eine Überlagerung.
  3. Messen Sie den Zustand des Qubits.
  4. Erhalten Sie mit gleicher Wahrscheinlichkeit einen Wert von 0 oder 1.

Jetzt müssen wir nur noch auf einen Quantencomputer und ein Programm zugreifen, um unseren echten Zufallszahlengenerator zu erstellen.

Programmieren eines Quantencomputers

Erstaunlicherweise haben einige Unternehmen einfache Quantencomputer in der Cloud für die breite Öffentlichkeit bereitgestellt. Einer dieser Services wird von IBM bereitgestellt und heißt IBM Q Experience. Derzeit bietet dieser Dienst Zugriff auf zwei 5-Qubit-Prozessoren und zwei 16-Qubit-Prozessoren, die auf der ganzen Welt verteilt sind. Sobald ein Benutzer ein kostenloses Konto erstellt hat, wird die Berechnungszeit mithilfe eines Kreditsystems zugewiesen und freien Benutzern wird eine kleine Anzahl von Kredits zur Verfügung gestellt, die jeden Tag aktualisiert werden. Sie können Ihre Schaltung mit einem Online-Editor oder programmgesteuert über ein SDK entwerfen (16-Qubit-Prozessoren stehen derzeit nur Benutzern des SDK zur Verfügung). Wenn Ihr Programm zur Ausführung bereit ist, wird es in eine Warteschlange gestellt, damit es ausgeführt werden kann, wenn sich der Prozessor in der Warteschlange befindet nächstes verfügbar.

Um unseren Zufallszahlengenerator zu erstellen, verwenden wir das bereitgestellte SDK für IBM Q Experience mit dem Namen Qiskit. Wir müssen unseren Code in Python schreiben, und während wir die Anwendung schreiben, können wir ihn auch auf einem simulierten Quantenprozessor lokal auf unserer eigenen Maschine testen, um Zeit und Credits zu sparen.

Beginnen wir zunächst mit dem Basiscode, um die vier obigen Schritte auszuführen:

Hier erstellen wir eine Quantenschaltung aus zwei Einzelbitregistern, einem Quantenregister mit einem einzelnen Qubit und einem ähnlich großen klassischen Register zur Interaktion mit dem Quantenregister. Wir wenden dann ein Hadamard-Gatter auf unser einzelnes Qubit an, um es in einen Überlagerungszustand zu zwingen, und messen diesen Zustand in unserem klassischen Register. Schließlich führen wir den soeben beschriebenen Prozess auf einem lokalen simulierten Prozessor aus und weisen das SDK an, den Prozess nur einmal auszuführen. Für die meisten anderen Zwecke möchten wir eine Quantenschaltung mehrmals ausführen und die Ergebnisse auswerten, um die inhärente Zufälligkeit im System zu beseitigen. Für unsere Zwecke funktioniert jedoch nur ein einziger Durchlauf einwandfrei. Wir können die Zählungen unserer Ergebnisse ausdrucken, die als Karte möglicher Bitwerte die Häufigkeit anzeigen, mit der sie für jeden Lauf gemessen wurden, z. B .: {"0": 1, "1": 0}. Sobald dieses Programm auf einem Quantenprozessor ausgeführt wird, erfolgt die Messung eines 0- oder 1-Werts mit einer Wahrscheinlichkeit von 50%.

Dieser Code hat uns das Äquivalent eines perfekten Münzwurfs gegeben. Jetzt müssen wir nur noch eine Reihe binärer Münzwürfe finden, um sie in eine Zufallszahl in einem bestimmten Bereich umzuwandeln. Eine einfache Möglichkeit, dies zu tun, besteht darin, die Zufallsbitwerte, die wir mit dem obigen Code erzeugen, zu einer Binärzahl zusammenzusetzen. Wenn wir diese Binärzahl in eine Dezimalzahl konvertieren, stellen wir fest, dass es sich jedes Mal um eine zufällige Dezimalzahl handelt.

Wenn wir zulassen möchten, dass ein Benutzer einen Bereich zum Generieren unserer Zahl eingibt, müssen wir herausfinden, wie viele Bits für eine bestimmte Ganzzahl zur Basis 10 erforderlich sind, damit wir wissen, wie viele zufällige Bits generiert werden müssen. Die Gleichung, die wir dazu brauchen, lautet:

Was wir in Python als Funktion darstellen können:

Damit können wir eine Funktion schreiben, die eine Zufallszahl bis zu einem bestimmten Maximum erzeugt, indem wir die obige Quantenschaltung für jedes Bit wiederholen, das wir benötigen:

Dieser Code ist der Kern unseres Quanten-Zufallsgenerators. Wir berechnen die Anzahl der Bits, die erforderlich sind, um eine Zahl bis zum angegebenen Maximum zu generieren, und generieren für jedes erforderliche Bit einen Zufallswert mit Qiskit und addieren ihn zu einer Zeichenfolge generierter Bits. Wir analysieren diese Zeichenfolge dann als eine Ganzzahl zur Basis 10 von der Basis 2.

Es gibt jedoch ein entscheidendes Problem mit diesem Code. Wenn Sie es genügend oft ausführen, werden Sie feststellen, dass es tatsächlich Zahlen erzeugt, die maximal der nächsten Zweierpotenz zur Eingabe entsprechen. Dies liegt daran, dass wir berechnet haben, wie viele Bits erforderlich sind, um eine bestimmte Zahl darzustellen. Wenn jedoch alle diese Bits den Wert 1 haben, kann unsere Zahl leicht höher sein als das angegebene Maximum. Es ist überraschend schwierig, dieses Problem zu lösen, und der beste Weg, um die Zahl unter unserem Maximum zu halten, ohne eine andere statistische Verzerrung einzuführen, ist die Verwendung von Ablehnungsstichproben³. Wir müssten einfach eine Nummer generieren, und wenn diese zu groß ist, lehnen Sie diese Nummer ab und führen Sie den Prozess erneut aus. Da wir nur über begrenzte Ressourcen für ein kostenloses Konto bei IBM Q Experience verfügen, halten wir unseren Code einfach und beschränken die Benutzereingabe auf Zweierpotenzen, indem wir die Eingabe auf die nächsthöhere Potenz aufrunden:

Sie können auch ganz einfach die Befehlszeileneingaben eines Benutzers analysieren, um ein gewünschtes Maximum einzugeben, sowie ein Flag, um dem Programm mitzuteilen, ob es auf einem echten Quantencomputer ausgeführt werden soll, und eine Option zum Übergeben eines API-Schlüssels für IBM Q Experience:

Bevor wir unseren Code auf einem echten Quantenprozessor ausführen können, ist es am besten, unsere Lösung so zu optimieren, dass eine minimale Anzahl von Schleifen ausgeführt wird, um freie Ressourcen auf unserem Cloud-Quantenprozessor zu sparen. Wenn wir zum Beispiel den 5-QBit-Prozessor „IBM Q5 Tenerife“ (Backend-Name ibmqx4) verwenden würden, könnten wir alle 5 QBits nutzen, indem wir sie alle durch Hadamard-Gatter führen und ihre gemessenen Werte kombinieren. Auf diese Weise könnten wir mit einer einzigen Schleife eine Zufallszahl von bis zu 31 generieren, und IBM Q Experience bietet genügend Credits für drei Anweisungen, sodass wir in einem einzigen Durchgang eine Zahl von bis zu 32767 generieren können.

Wenn all diese Elemente kombiniert werden, wird unser endgültiger Code:

Den vollständigen Code und eine Beschreibung zur Ausführung finden Sie auf GitHub.

Was ist gerade passiert?

Wenn Sie sich für ein kostenloses Konto bei IBM Q Experience anmelden, besorgen Sie sich einen API-Schlüssel und führen Sie dieses Programm folgendermaßen aus:

python ./main.py -remote --qx-token  15

Sie werden feststellen, dass der Vorgang einige Zeit in Anspruch nimmt (ca. 10–20 Minuten) und eine zufällige Ganzzahl zwischen 0 und 16 zurückgibt. Folgendes ist passiert, während Sie gewartet haben:

  1. Ihr Computer hat die Befehlszeileneingabe analysiert und berechnet, wie viele Zufallsbits erforderlich sind, um eine Zahl zwischen 0 und der nächsten Potenz von 2 aus 15 darzustellen. In diesem Fall sind 4 Bits erforderlich, um eine Zahl bis 16 zu erstellen, was nur eine Anweisung bedeutet an einen 5-Qubit-Quantenprozessor senden.
  2. Das Qiskit SDK erstellt eine Reihe von Anweisungen, die zur Ausführung an IBM Q Experience gesendet werden.
  3. Ihre Anweisungen werden in eine Warteschlange gestellt, die vom Quantencomputer „IBM Q5 Tenerife“ in New York ausgeführt wird.
  4. Sobald der Quantencomputer IBM Q5 Tenerife bereit ist, weist er der angeforderten Task 4 von 5 verfügbaren Qubits zu. Es wendet ein Hadamard-Gate auf diese 4 Qubits an und überlagert sie mit einem Quantenspin.
  5. Der Spin jedes Qubits wird gemessen, wodurch die Quantenüberlagerung kollabiert und ein zufälliger Binärzustand aufgedeckt wird, der dann in ein klassisches 4-Bit-Register ausgegeben wird.
  6. Der gemessene Binärstatus wird dann zurück an IBM Q Experience und zurück an das Qiskit SDK gesendet, das auf Ihrem Computer ausgeführt wird.
  7. Ihr Computer führt diese binären Messungen durch und erstellt daraus eine 4-Bit-Binärzahl.
  8. Ihre Binärzahl wird in eine Ganzzahl zur Basis 10 umgewandelt und an den Benutzer zurückgegeben.

Herzlichen Glückwunsch, Sie haben gerade einen Quantencomputer gesteuert und die seltsamen unvorhersehbaren Eigenschaften subatomarer Partikel genutzt, um eine echte Zufallszahl zu generieren. Bitte erwägen Sie, Ihre neu gefundenen Superkräfte für immer zu nutzen.

Kennen Sie interessante praktische Anwendungen für Cloud-Quanten-Computing? Lass es mich wissen @robbiemccorkell.

Verweise:

  1. Jason M. Rubin, MIT School of Engineering (2011), Kann ein Computer eine wirklich zufällige Zahl erzeugen?
  2. Daniel Simmons, Hackernoon (2014), Wie generiert Math.random () von JavaScript Zufallszahlen?
  3. Adam Hyland, bocoup (2013), Zufallsgenerierung in Javascript
  4. The Open Group Base Specifications Issue 7 (2018), 4.16: Sekunden seit der Epoche
  5. Jeffrey S. Lee, Gerald B. Cleaver, Universitätsbibliothek Cornell (2015), Das kosmische Mikrowellenhintergrund-Strahlungsleistungsspektrum als Zufallsbitgenerator für die Kryptographie mit symmetrischen und asymmetrischen Schlüsseln
  6. Tony Hey, Patrick Walters von der Cambridge University Press (1987), The Quantum Universe
  7. Alastair I. M. Rae, Gruppe Taylor & Francis (2008), Quantenmechanik (5. Aufl.)
  8. Wikipedia (2018), Kopenhagen Interpretation
  9. Eleanor Riefffel, Wolfgang Polak, Massachusetts Institute of Technology (2011), Quantum Computing: Eine sanfte Einführung
  10. Artur Ekert, Patrick Hayden, Hitoshi Inamori, Universität Oxford (2008), Grundbegriffe der Quantenberechnung
  11. Daniel Baumann, Universität Cambridge (2013), Konzepte der theoretischen Physik
  12. Rick Regan, Exploring Binary (2012), Anzahl der Bits in einer Dezimalzahl
  13. Dimitri DeFigueiredo Ph.D (2017), Generieren von Zufallszahlen aus Zufallsbytes

Bearbeiten: Vielen Dank an Bob Sutor, der darauf hingewiesen hat, dass der Quantencomputer IBM Q 5 Tenerife nur mit dem Namen und nicht mit dem Standort Teneriffas verwandt ist und sich in New York befindet.

Ursprünglich auf blog.red-badger.com veröffentlicht.