Programmieren eines Quantencomputers: Erzeugen wahrer Zufallszahlen

Computer sind deterministische, vorhersehbare Maschinen und so konzipiert, dass sie Anweisungen auf wiederholbare Weise blind folgen. Diese Art von Computern hat uns natürlich während des größten Teils des letzten Jahrhunderts sehr gute Dienste geleistet, aber dieses Design weist einen grundlegenden Fehler auf: Es kann keine zufälligen Operationen ausführen¹. Zufallszahlengeneratoren sind heutzutage ein äußerst wichtiger Bestandteil vieler Anwendungen, aber obwohl die von ihnen erzeugten Zahlen zufällig genug sind, sind sie „pseudozufällig“ und können häufig auf irgendeine Weise vorhergesagt oder rückentwickelt werden.

Heute 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. Etwas, das mit einem klassischen Computer auf Turing-Basis bisher unmöglich war.

Zufallsgeneratoren heute

In den meisten gängigen Programmiersprachen ist ein Zufallszahlengenerator integriert, den Entwickler verwenden können. Diese Generatoren verwenden im Allgemeinen einen Eingabesamen, der das aktuelle Datum und die aktuelle Uhrzeit darstellt, verschlüsseln diesen Wert mithilfe eines Algorithmus und geben einen Wert aus, der sich so stark von der Eingabe unterscheidet, dass wir sie als zufällig wahrnehmen. Die Verschlüsselungsfunktion ist ein vorhersagbarer Algorithmus mit einer hohen Entropie (für eine kleine Änderung der Eingabe geben sie eine große Änderung der Ausgabe zurück), und wir erhalten jedes Mal eine andere Zahl, da sich der Eingabesamen im Laufe der Zeit ändert. Für fast alle praktischen Anwendungen funktioniert dieses System einwandfrei, 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) so 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ären Darstellungen des Seeds nach oben und unten verschiebt und die Bitrepräsentationen zwischen den Schritten umkehrt, was zu einer Bitdarstellung einer Zahl führt, die sich vollständig von der Seed-Eingabe 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³, z. B. 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 ständig ohne Probleme, aber wir können es nicht als echten Zufallszahlengenerator bezeichnen. Wenn jemand weiß, wie der Zufallszahlengenerator funktioniert, und den Eingabe-Startwert 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 Radiowellen, die noch vom Urknall übrig bleiben) als Keim, da niemand vorhersagen kann, wie sich dieses Hintergrundrauschen zu einem bestimmten Zeitpunkt verhält.

Ein Zufälligkeitssystem, das einen unvorhersehbaren Keim wie den Mikrowellenhintergrund verwendet, ist nach heutigem Kenntnisstand zu diesem Zeitpunkt völlig zufällig. Niemand kann derzeit vorhersagen, wie sich dieser Startwert zu einem bestimmten Zeitpunkt verhält, und kann daher die von ihm erzeugte Zufallszahl nicht vorhersagen. Diese Art von Saatgut kann in Zukunft möglicherweise nicht vorhergesagt werden, aber wenn wir den kosmischen Mikrowellenhintergrund genauso messen wie jemand anderes und ihn als Eingabe für den Zufallszahlengenerator verwenden, können wir dessen Ergebnis vorhersagen .

Um eine wirklich zufällige Zahl zu erzeugen, müssen wir etwas in der Natur finden, das wir nicht perfekt vorhersagen können, etwas, das nur durch Wahrscheinlichkeit beschrieben werden kann. Bis zum Beginn des 20. Jahrhunderts glaubte man, dass dies 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 subatomarer Ebene beschreibt. Es heißt, wenn wir die Welt in immer kleinerem Maßstab beobachten, werden klassische Beschreibungen von Teilchen und Kräften, wie sie von Sir Isaac Newton im 18. Jahrhundert definiert wurden, weniger genau und wir müssen zu verschiedenen Quantenbeschreibungen wechseln, die von Statistik und Wahrscheinlichkeit bestimmt werden. 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 seltsamer zu machen, besagt die von Niels Bohr und Werner Heisenberg entwickelte Kopenhagener Interpretation der Quantenmechanik, dass Quantensysteme vor der Messung keine bestimmten Eigenschaften haben, sondern in allen möglichen Zuständen gleichzeitig in einem als Überlagerung bekannten Prinzip existieren. Nur wenn das System beobachtet wird, kollabiert die Überlagerung und das System existiert in einem einzigen bestimmten Zustand. Dies ist als Beobachter-Effekt bekannt. Am Beispiel der Position eines Elektrons können wir eine Wahrscheinlichkeit vorhersagen, dass ein Elektron zu einem bestimmten Zeitpunkt an einem bestimmten Ort vorhanden sein wird, aber vor dieser Messung existiert das Elektron 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 aufgrund des Unsicherheitsprinzips keine anderen Eigenschaften wie den Impuls bestimmen.

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

Ob es Ihnen gefällt oder nicht, die Quantentheorie bleibt unser bestes Verständnis der subatomaren Welt und wurde zum Herzen eines völlig neuen 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 Teilchen 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 dar, indem sie ein 0- oder 1-Bit verwenden, aber sie implementieren diese Zustände physikalisch unter Verwendung der binären Eigenschaften subatomarer Teilchen. 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 quantenmechanisch beschrieben werden und beide Zustände gleichzeitig überlagern. Dies bedeutet, dass ein Quantenbit an Information 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 Quantengatter ähnlich den Gattern einer klassischen Schaltung. Während ein klassischer Computer Operationen an Bits ausführen kann, wie sie beispielsweise auf ihren entgegengesetzten Wert umgedreht werden, können Quantengatter diese Operationen und fortgeschrittenere Quantenoperationen ausführen, wie beispielsweise ein Qubit in eine Überlagerung beider möglicher Werte zu schieben. Ein Gatter, das ein Qubit in eine Überlagerung drückt, wird als Hadamard-Gatter bezeichnet und ist eines der grundlegendsten und am häufigsten verwendeten Logikgatter im Quantencomputer¹⁰.

Wenn wir den Spin eines Elektrons in eine Überlagerung von möglichen Spin-Up- und Down-Zuständen schieben, die die Werte 1 und 0 eines Qubits darstellen, kann gesagt werden, dass das Elektron einen gleichzeitigen Spin beider Werte aufweist, und das Qubit befindet sich in einer Überlagerung von 0 und 1. Wenn wir dieses Qubit messen, kollabieren wir die Überlagerung und zwingen sie in einen dieser beiden möglichen Zustände mit jeweils gleicher Eintrittswahrscheinlichkeit¹¹. 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. Erzwinge 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 zugreifen und in den obigen Schritten programmieren, um unseren echten Zufallszahlengenerator zu erstellen.

Programmieren eines Quantencomputers

Erstaunlicherweise haben einige Unternehmen jetzt einfache Quantencomputer in der Cloud für die breite Öffentlichkeit verfügbar gemacht. 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 weltweit verteilt sind. Sobald Benutzer ein kostenloses Konto erstellt haben, wird die Rechenzeit mithilfe eines Kreditsystems zugewiesen, und kostenlose Benutzer erhalten eine kleine Anzahl von Credits, die sie täglich für diese Aktualisierung verwenden können. 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, die ausgeführt werden soll, wenn der Prozessor ausgeführt wird als nächstes verfügbar.

Um unseren Zufallszahlengenerator zu erstellen, verwenden wir das mitgelieferte SDK für IBM Q Experience namens 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 unserem eigenen Computer testen, um Zeit und Credits zu sparen.

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

Hier erstellen wir eine Quantenschaltung aus zwei Einzelbitregistern, einem Quantenregister mit einem einzelnen Qubit und einem klassischen Register ähnlicher Größe für die Interaktion mit dem Quantenregister. Wir wenden dann ein Hadamard-Gate auf unser einzelnes Qubit an, um es in einen Überlagerungszustand zu zwingen, und messen diesen Zustand an unserem klassischen Register. Schließlich führen wir den gerade 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 mitteln, um die inhärente Zufälligkeit im System zu beseitigen. Für unsere Zwecke funktioniert jedoch nur ein einziger Lauf perfekt. Wir können die Anzahl unserer Ergebnisse ausdrucken, die als Karte möglicher Bitwerte angezeigt werden, wie oft sie für jeden Lauf gemessen wurden, z. B.: {"0": 1, "1": 0}. Sie werden feststellen, dass, sobald dieses Programm auf einem Quantenprozessor ausgeführt wird, die Messung eines 0- oder 1-Werts mit einer Wahrscheinlichkeit von 50% erfolgt.

Dieser Code hat uns das Äquivalent eines perfekten Münzwurfs gegeben. Jetzt müssen wir nur noch einen Weg finden, eine Reihe von binären Münzwürfen zu nehmen und sie in eine Zufallszahl in einem bestimmten Bereich umzuwandeln. Eine einfache Möglichkeit, dies zu tun, besteht darin, die zufälligen Bitwerte, die wir mit dem obigen Code generieren, zu verwenden, um eine Binärzahl zu erstellen. Wenn wir diese Binärzahl in eine Dezimalzahl umwandeln, werden wir feststellen, dass es sich jedes Mal um eine zufällige Dezimalzahl handelt.

Wenn wir einem Benutzer die Eingabe eines Bereichs zum Generieren unserer Zahl erlauben möchten, müssen wir herausfinden, wie viele Bits erforderlich sind, um eine bestimmte Ganzzahl der Basis 10 darzustellen, damit wir wissen, wie viele zufällige Bits generiert werden müssen. Die Gleichung, die wir dazu benötigen, lautet ²:

Was wir in Python als Funktion darstellen können:

Auf diese Weise können wir eine Funktion schreiben, die eine Zufallszahl bis zu einem bestimmten Maximum erzeugt, indem wir die obige Quantenschaltung für jedes benötigte Bit wiederholen:

Dieser Code ist der Kern unseres Quantenzufallszahlengenerators. Wir berechnen die Anzahl der Bits, die erforderlich sind, um eine Zahl bis zum angegebenen Maximum zu generieren, und für jedes erforderliche Bit generieren wir mit Qiskit einen Zufallswert und fügen ihn einer Zeichenfolge generierter Bits hinzu. Wir analysieren diese Zeichenfolge dann als Ganzzahl zur Basis 10 von 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 bis zu einem Maximum der nächstgelegenen Zweierpotenz zum Eingang erzeugt. 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 als das angegebene Maximum sein. Es ist überraschend schwierig, dieses Problem zu lösen, und der beste Weg, die Zahl unter unserem Maximum zu halten, ohne eine andere statistische Verzerrung einzuführen, ist die Verwendung der Ablehnungsstichprobe¹³. Wir müssten einfach eine Nummer generieren, und wenn sie zu groß wäre, lehnen Sie diese Nummer ab und führen Sie den Prozess erneut aus. Da wir bei IBM Q Experience nur über begrenzte Ressourcen für ein kostenloses Konto verfügen, halten wir unseren Code einfach und beschränken die Benutzereingabe nur auf Zweierpotenzen, indem wir die Eingabe auf die nächsthöhere Potenz aufrunden:

Wir können auch ganz einfach die Befehlszeileneingaben eines Benutzers analysieren, um ein gewünschtes Maximum zu erfassen, sowie ein Flag, das dem Programm mitteilt, 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 sie eine minimale Anzahl von Schleifen durchläuft, um freie Ressourcen auf unserem Cloud-Quantenprozessor zu sparen. Wenn wir beispielsweise den 5-Qubit-Prozessor „IBM Q5 Tenerife“ (Backend-Name ibmqx4) verwenden würden, könnten wir alle 5 Qubits verwenden, indem wir sie alle durch Hadamard-Gates leiten und ihre gemessenen Werte kombinieren. Dies würde es uns ermöglichen, eine Zufallszahl von bis zu 31 mit einer einzelnen Schleife zu generieren, und IBM Q Experience bietet genügend Credits für 3 Anweisungen, sodass wir in einem einzigen Lauf eine Zahl von bis zu 32767 generieren können.

Wenn alle diese Elemente kombiniert sind, 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 fünfzehn

Sie werden feststellen, dass der Vorgang einige Zeit in Anspruch nimmt (ca. 10 bis 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 zufällige Bits erforderlich sind, um eine Zahl zwischen 0 und der nächsten Potenz von 2 von 15 darzustellen. In diesem Fall sind 4 Bits erforderlich, um eine Zahl bis 16 zu erstellen, was nur einen Befehl bedeutet an einen 5-Qubit-Quantenprozessor senden.
  2. Eine Reihe von Anweisungen wird vom Qiskit SDK erstellt und zur Ausführung an IBM Q Experience gesendet.
  3. Ihre Anweisungen werden in eine Warteschlange gestellt, die vom Quantencomputer „IBM Q5 Tenerife“ in New York ausgeführt wird.
  4. Sobald der IBM Q5 Tenerife-Quantencomputer bereit ist, weist er der angeforderten Aufgabe 4 von 5 verfügbaren Qubits zu. Es wendet ein Hadamard-Gate auf diese 4 Qubits an und führt sie in eine Überlagerung von Quantenspin ein.
  5. Der Spin jedes Qubits wird gemessen, wobei 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 an IBM Q Experience und an das auf Ihrem Computer ausgeführte Qiskit SDK zurückgesendet.
  7. Ihr Computer nimmt diese Binärmessungen vor und erstellt daraus eine 4-Bit-Binärzahl.
  8. Ihre Binärzahl wird in eine Basiszahl 10 umgewandelt und an den Benutzer zurückgegeben.

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

Kennen Sie einige interessante praktische Anwendungen für Cloud Quantum 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), Zufallszahlengenerierung in Javascript
  4. The Open Group Base Specifications Ausgabe 7 (2018), 4.16: Sekunden seit der Epoche
  5. Jeffrey S. Lee, Gerald B. Cleaver, Universitätsbibliothek Cornell (2015), Das kosmische Mikrowellen-Hintergrundstrahlungsleistungsspektrum als Zufallsbitgenerator für die Kryptographie mit symmetrischen und asymmetrischen Schlüsseln
  6. Tony Hey, Patrick Walters, Cambridge University Press (1987), Das Quantenuniversum
  7. Alastair IM Rae, Taylor & Francis Group (2008), Quantenmechanik (5. Aufl.)
  8. Wikipedia (2018), Kopenhagener Interpretation
  9. Eleanor Riefffel, Wolfgang Polak, Massachusetts Institute of Technology (2011), Quantencomputer: Eine sanfte Einführung
  10. Artur Ekert, Patrick Hayden, Hitoshi Inamori, Universität Oxford (2008), Grundlegende Konzepte in der Quantenberechnung
  11. Daniel Baumann, Universität Cambridge (2013), Konzepte in der theoretischen Physik
  12. Rick Regan, Exploring Binary (2012), Anzahl der Bits in einer Dezimalzahl
  13. Dimitri DeFigueiredo Ph.D (2017), Generieren zufälliger Ganzzahlen aus zufälligen Bytes

Bearbeiten: Vielen Dank an Bob Sutor für den Hinweis, dass der IBM Q 5 Tenerife-Quantencomputer nur namentlich mit Teneriffa verwandt ist und nicht in New York.

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