Wie würde ein sehr einfaches Quantenprogramm aussehen?

76

Angesichts der Ankündigung des weltweit ersten programmierbaren quantenphotonischen Chips habe ich mich gefragt, wie Software für einen Computer mit Quantenverschränkung aussehen würde. Eines der ersten Programme, das ich jemals geschrieben habe, war so etwas wie

for i = 1 to 10
  print i
next i

Kann jemand ein Beispiel für einen Code von vergleichbarer Einfachheit nennen, der Quantenphotonen-Chips (oder ähnliche Hardware) in Pseudocode oder Hochsprache verwendet? Ich habe Schwierigkeiten, den konzeptionellen Sprung von der traditionellen Programmierung zur Verschränkung usw. zu schaffen.

xpda
quelle
Ihre Verbindung ist unterbrochen
Suresh Venkat
1
+1 und für diese Frage. Ich bin sehr neugierig auf eine Programmiersprache unter einem anderen Paradigma als Turing Machines, wie weit wir auch davon entfernt sein mögen, den Code tatsächlich in einem Quantencomputer auszuführen.
Janoma

Antworten:

60

Vorbehalt Emptor: Folgendes ist stark von meiner eigenen Forschung und Sichtweise auf dem Gebiet der Qualitätskontrolle abhängig . Dies stellt keinen allgemeinen Konsens auf diesem Gebiet dar und kann sogar eine gewisse Eigenwerbung beinhalten.

Das Problem, eine "Hallo Welt" des Quantencomputers zu zeigen, ist, dass wir im Grunde immer noch so weit von Quantencomputern entfernt sind, wie es Leibnitz oder Babbage von Ihrem aktuellen Computer waren. Obwohl wir wissen, wie sie theoretisch funktionieren sollten, gibt es keine Standardmethode, um einen physikalischen Quantencomputer zu bauen. Ein Nebeneffekt davon ist, dass es kein einzelnes Programmiermodell für Quantencomputer gibt. Lehrbücher wie Nielsen et al. zeigt Ihnen ein "Quantum Circuit" -Diagramm, aber das sind alles andere als formale Programmiersprachen: Sie erhalten ein wenig "Handbewegung" in Bezug auf Details wie die klassische Steuerung oder den Umgang mit Eingabe- / Ausgabe- / Messergebnissen.

Was mir in meiner Forschung als Programmiersprachen-Informatiker am besten gefallen hat und um den Jist of QC anderen Informatikern nahe zu bringen, ist die Verwendung des einfachsten QC-Modells, auf das ich gestoßen bin, das alles kann.

Das einfachste Quantencomputerprogramm, das ich gesehen habe und das alle wesentlichen Elemente enthält, ist ein kleines Programm mit drei Befehlen im einfachsten Quantenprogrammiermodell, das mir begegnet ist. Ich benutze es wie eine "Hallo Welt", um die Grundlagen zu vermitteln.

Gestatten Sie mir eine kurze, vereinfachte Zusammenfassung des Messkalküls von Danos et al. 1 basiert auf dem Einweg-Quantencomputer 2 : Ein Qubit wird bei der Messung zerstört, aber die Messung wirkt sich auf alle anderen Qubits aus, die damit verwickelt waren. Es hat einige theoretische und praktische Vorteile gegenüber den "schaltungsbasierten" Quantencomputern, wie sie vom photonischen Chip realisiert werden, aber das ist eine andere Diskussion.

Stellen Sie sich einen Quantencomputer mit nur fünf Befehlen vor: N, E, M, X und Z. Die "Assemblersprache" ähnelt der Ihres regulären Computers, nach Ausführung eines Befehls wird mit dem nächsten Befehl in der Sequenz fortgefahren. Jeder Befehl benötigt eine Ziel-Qubit-Kennung, wir verwenden hier nur eine Zahl und andere Argumente.

N 2          # create a new quantum bit and identify it as '2'
E 1 2        # entangle qubits '1' and '2', qubit 1 already exists and is considered input
M 1 0        # measure qubit '1' with an angle of zero  (angle can be anything in [0,2pi]
             # qubit '1' is destroyed and the result is either True or False
             # operations beyond this point can be dependent on the signal of '1'
X 2 1        # if the signal of qubit '1' is True, execute the Pauli-X operation on qubit '2'

Das obige Programm erzeugt somit eine Ancilla, verwickelt sie mit dem eingegebenen Qubit, misst die Eingabe und führt abhängig vom Messergebnis eine Operation an der Ancilla durch. Das Ergebnis ist, dass Qubit 2 jetzt den Zustand von Qubit 1 nach der Hadamard- Operation enthält.

Das oben Genannte ist natürlich so niedrig, dass Sie es nicht von Hand codieren möchten. Der Vorteil des Messkalküls besteht darin, dass es "Muster" einführt, eine Art zusammensetzbare Makros, mit denen Sie größere Algorithmen erstellen können, als Sie es mit Subroutinen tun würden. Sie beginnen mit 1-Anweisungsmustern und bauen von dort aus größere Muster auf.

Anstelle einer Assembler-ähnlichen Anweisungssequenz wird das Programm häufig auch als Graph notiert:

 input                .........
    \--> ( E ) ---> (M:0)     v
(N) ---> (   ) ------------> (X) ---> output

wobei volle Pfeile Qubitabhängigkeiten sind und der gepunktete Pfeil eine Signalabhängigkeit ist.

Das Folgende ist das gleiche Hadamard-Beispiel, das in einem kleinen Programmierwerkzeug ausgedrückt wird, wie ich es mir bei einem "Quantenprogrammierer" vorstellen würde.

Messberechnungs-Tool

Bearbeiten: (Hinzufügen von Relationen zu "klassischen" Computern) Klassische Computer sind immer noch sehr effizient, was sie am besten können. Die Vision ist daher, dass Quantencomputer verwendet werden, um bestimmte Algorithmen zu entladen GPU. Wie Sie oben gesehen haben, würde die CPU den Quantencomputer durch Senden eines Befehlsstroms steuern und die Messergebnisse aus den booleschen "Signalen" zurücklesen. Auf diese Weise haben Sie eine strikte Trennung zwischen klassischer Steuerung durch die CPU und dem Quantenzustand und den Auswirkungen auf den Quantencomputer.

Zum Beispiel werde ich meinen Quantencoprozessor verwenden, um einen zufälligen Booleschen Wert oder ein Cointoss zu berechnen. Klassische Computer sind deterministisch, daher ist es schlecht, eine gute Zufallszahl zurückzugeben. Quantencomputer sind von Natur aus probabilistisch. Alles, was ich tun muss, um eine zufällige 0 oder 1 zu erhalten, ist, ein gleichmäßig ausgeglichenes Qubit zu messen. Die Kommunikation zwischen der CPU und 'QPU' würde ungefähr so ​​aussehen:

 qrand()       N 1; M 1 0;
 ==>  | CPU | ------------> | QPU |  ==> { q1 } ,  []
                 start()
      |     | ------------> |     |  ==> { } , [q1: 0]
                 read(q1)         
      |     | ------------> |     |
                  q1: 0 
 0    |     | <-----------  |     |
 <==

Wo { ... }ist der Quantenspeicher der QPU, der Qubits enthält, und [...]sein klassischer (Signal-) Speicher, der Boolesche Werte enthält?


  1. Danos et al. Die Messrechnung. arXiv (2007) vol. quant-ph
  2. Raussendorf und Briegel. Ein Einweg-Quantencomputer. Physical Review Letters (2001) vol. 86 (22) S. 5188-5191
Rindfleisch
quelle
Ausgezeichnete Diskussion über das Thema, danke, Rindfleisch. Übrigens spricht das OP von "Ich habe Schwierigkeiten, den konzeptionellen Sprung von der traditionellen Programmierung zur Verstrickung usw. zu schaffen." Daher sollte etwas, das bei diesem Übergang hilft, willkommen sein.
Kris
Du hast Recht, schien ich verpasst zu haben tatsächlich , dass ein Teil, für die Scham: / ein paragraph.≈ Hinzufügen
Beef
"Stellen Sie sich einen Quantencomputer mit nur fünf Befehlen vor: N, E, M, X und Z." keine Erklärung der Anweisung Z :(
Fernando Gonzalez Sanchez
Z ist viel wie X;) de.wikipedia.org/wiki/Pauli_matrices Die X-Operation wandelt den Vektor [ab] in [ba] um, die Z-Operation wandelt ihn in [a -b] um.
Rindfleisch
21

Ich gehe davon aus, dass Cs Libquantum , Haskells Quantenmonaden oder Perls Quantum :: Entanglement alle getreue Quantenberechnungen darstellen. Sie könnten sich ihre Beispiele ansehen.

Im Allgemeinen beschreiben Sie einen Quantenalgorithmus als einen klassischen Algorithmus, der eine Reihe linearer Operatoren auf eine Superposition anwendet, die den Zustand Ihres Quantensystems darstellt. Zeitschriftenartikel zeigen oft eine Schaltung mit Linien für Quantenbits / -register und Kästen für lineare Operatoren.

Natürlich beschreibt der schwierige Teil nicht den Algorithmus, sondern versteht, warum er funktioniert, genau wie probabilistische Algorithmen. Ich habe immer gedacht, dass Grovers Algorithmus ziemlich verständlich ist. Sie könnten auch etwas über die von Shors Algorithmus verwendete Quanten-Fourier-Transformation lesen .

Jeff Burdges
quelle
11

Es sieht aus wie das: Bildbeschreibung hier eingeben

Auch Sie können auf einen echten Quantenprozessor zugreifen. Hier anmelden: http://www.research.ibm.com/quantum/

Es enthält auch einen Simulator, mit dem Sie ohne tatsächliche Hardware testen oder Credits (kostenlos) zum Ausführen auf tatsächlicher Hardware verwenden können.

Robert Lisiecki
quelle
3

Ich denke, die Antwort lautet "Sehr ähnlich wie bei einem einfachen klassischen Programm."

Wenn wir den einfach typisierten Lambda-Kalkül (mit Produkten) als das Herzstück der klassischen Programmierung betrachten, können wir ausnutzen, dass es die interne Typentheorie einer geschlossenen kartesischen Kategorie ist, die uns einen Hinweis gibt.

nk

Also, wenn die STLC zu kartesischen geschlossenen Kategorien gehört, was ist dann zu geschlossenen symmetrischen monoidalen Kategorien? Nun, wir wissen, dass die interne Logik einer symmetrischen monoidalen Kategorie MILL ist . Wir brauchen also eine Typentheorie, die MILL entspricht - eine lineare Typentheorie.

Was bekommen wir mit einer linearen Typentheorie, wenn wir uns vom abstrakten Unsinn entfernen? Linearität. Wir bekommen Linearität der Ressourcen. Und genau das wollen wir. Sie dürfen keine Quantenbits klonen. Sie dürfen nicht implizit messen. Und Linearität bedeutet, dass Sie während der Reduzierung keine dieser Aktionen ausführen können.

Es hat einige Arbeiten zu linearen Typentheorien gegeben, aber keine Tonne. Einige der Ideen in diesem Beitrag stammen aus diesem Artikel: Physik, Topologie, Logik und Berechnung: Ein Rosettastein von Mike Stay und John Baez, der viel detaillierter ist als meine Handbewegung.

Darius Jahandarie
quelle
0

Ich würde wahrscheinlich mit einer einfachen Implementierung des Zählers "Teilen durch kleines n" beginnen.

Beispiel: Erzeugen Sie bei einer 10-GHz-Quelle eine 5-GHz-Ausgabe (diese Zahlen sind jedoch willkürlich und dienen nur zur Veranschaulichung des Konzepts).

So können wir Probleme wie Speicher und Von Neumann-Architektur ignorieren und uns darauf konzentrieren, ob die Komponenten tatsächlich etwas Verständliches bewirken.

Das nächste Ziel wäre es dann, ein kleines Repertoire von "small n" aufzubauen (aber ich würde auch auf Rückschläge von meinen Forschern warten - wenn sie der Meinung wären, dass andere kleine Ziele sofort fruchtbarer wären, würde ich das sicherlich verstehen wollen was sie mir erzählten.)

Zu den langfristigen Zielen gehören Mechanismen, mit denen Informationen in das System und aus dem System gepumpt und lange genug gespeichert werden können, um sie nutzen zu können.

(Es ist wahrscheinlich erwähnenswert, dass frühe Computerprogramme alle "fest verdrahtet" waren. Erst nach langjähriger Erfahrung mit diesen Systemen konnten wir gespeicherte Programme implementieren.)

rdm
quelle
-6

Ich denke, die Programmierung eines Quantencomputers sollte aus einem anderen Blickwinkel gesehen werden als die normale objektorientierte Programmierung.

QC hat die gleiche Fähigkeit des Gehirns zu denken und zu entscheiden. Die Fähigkeit zu denken bedeutet, dass Data-Mining eine mögliche Datenquelle darstellt und entscheidet, welche aus den möglichen Zuständen ausgewählt werden soll.

Eine Software an diesem Punkt müsste so aufgebaut sein, dass die Qubits eine Datenquelle darstellen, die mit anderen Datengruppen abgetastet und verwickelt werden kann.

QC sollte einen Data-Miner haben, der das Lesen von Daten verarbeitet, verschiedene Optionen miteinander verknüpft, verschiedene Datenquellengruppen zusammenstellt, die Informationen wiedergeben, alle möglichen Zustände lesen und auswählen, welche weitergehen sollen.

So funktioniert unser Gehirn. Die QC ist in der Lage, das Gesetz der Quantenmechanik zu verstehen und dementsprechend zu handeln. Das heißt, Sie geben ein Problem an und die QC zeigt Ihnen alle möglichen Lösungen, um es zu lösen.

So mächtig könnte QC sein, stimmst du zu?

https://www.cs.rutgers.edu/~mlittman/papers/openhouse11.pdf Hier müssen Sie beginnen und dann einen Dataminer erstellen, um das Quantengerät mit Gattern usw., einem an den Dataminer angeschlossenen Lesegerät, zu lesen und zu erstellen Rückmeldung geben. Hostdaten der Quantum-Datenquellenkomponente und der Wissensumfang, in dem der Dataminer agiert.

Alex
quelle