Wie wird Quantencomputing die Programmierung verändern? [geschlossen]

33

Wie unterscheidet sich die Programmierung eines Quantenalgorithmus? Wie würde eine C-ähnliche Sprache aussehen, wenn sie für Qubits ausgelegt wäre? Würden sich die Typen ändern?

MaiaVictor
quelle
Hinweis: Ich bin mir nicht sicher, ob dies eine gültige Frage ist. Entschuldigung, wenn nicht.
MaiaVictor
4
Ich denke, es ist. Andererseits kenne ich die Regeln dieser Seite nicht sehr gut. Und ich habe keine wirklich gute Antwort auf diese Frage, aber ich kenne diesen Algorithmus, der verwendet werden könnte, um Ganzzahlen viel effizienter zu faktorisieren
John Davis,
3
Obwohl sich dieses Thema noch in der wissenschaftlichen Forschung befindet, sind die Grundlagen eines hypothetischen Quantencomputers AFAIK wohlbekannt, daher sollte die Frage von einem Domain-Experten beantwortet werden (was ich nicht bin). Also stimme ich nicht zu schließen.
Doc Brown

Antworten:

17

Als ich mich vor einiger Zeit damit befasste, war klar, dass Quantenalgorithmen, obwohl sie nicht besonders schnell sind, exponentiell massive Parallelität zulassen. Sie leuchten also in Fällen, in denen nach Räumen gesucht wird, die mit sequentieller Hardware nicht praktikabel sind, sogar mit massiv paralleler sequentieller Hardware.

Eine Eigenschaft von Quantenalgorithmen ist, dass sie reversibel sein müssen . Jeder gegebene Algorithmus kann in einen reversiblen Algorithmus übersetzt werden, indem genügend Aufzeichnungen hinzugefügt werden, damit er rückwärts ausgeführt werden kann.

Eine andere Eigenschaft ist, dass das Erhalten einer Antwort aus einem Quantenalgorithmus eine Hit-and-Miss-Angelegenheit ist, da das, was Sie am Ende einer Berechnung erhalten, mehrere Antworten sind, von denen jede ihre eigene Wahrscheinlichkeit hat. Es muss so ausgeführt werden, dass die gewünschte Antwort mit hoher Wahrscheinlichkeit vorliegt. Dies kann bedeuten, dass der Algorithmus mehrmals vorwärts und rückwärts ausgeführt wird.

Schauen Sie sich den Suchalgorithmus von Grover an .


INSERTED, um die grundlegende Funktionsweise von Grovers Algorithmus zu zeigen. Angenommen, es liegt ein Suchproblem vor. Die möglichen Antworten sind 0, 1, 2 und 3, aber die richtige Antwort ist 2. Der Quantencomputer wird also in eine Überlagerung aller vier Zustände versetzt und durchläuft eine Abfolge von Schritten, um festzustellen, welcher korrekt ist, und Kehrt die Amplitude um, wie die schwarzen Punkte und Pfeile unten:

Bildbeschreibung hier eingeben

Sie können sehen, dass Pfeil 2 innerhalb der Maschine invertiert wurde, aber es gibt keine Möglichkeit, dies außerhalb zu erkennen, da nur Wahrscheinlichkeiten außerhalb sichtbar sind, bei denen es sich um quadrierte Amplituden handelt und wenn sie quadriert sind, sind sie alle gleich.

Die Amplituden haben jedoch einen Mittelwert, der durch die rote Linie angezeigt wird, und der Computer kann eine Folge von Schritten durchlaufen, die jede Amplitude um den Mittelwert invertieren . Wenn das erledigt ist, übertragen sich die Amplituden und Wahrscheinlichkeiten auf Zustand 2, die richtige Antwort ! Wenn also die Maschine beobachtet wird, leuchtet Zustand 2 auf.

So einfach ist das nicht. Im Allgemeinen dauert es mehrere Vorwärts- und Rückwärtszyklen der Maschine, die am Ende jedes Zyklus invertiert werden, um die Wahrscheinlichkeit der richtigen Antwort zu maximieren. Außerdem muss man darauf achten, dass es nicht öfter als so oft gemacht wird, weil es sich genauso leicht selbst umkehren kann.

Warum sagen sie also, dass Quantencomputer so schnell sind ? Denn jedes Mal, wenn Sie die Anzahl der Qubits verdoppeln, quadrieren Sie die Parallelität, aber Sie quadrieren nicht die Zeitdauer, also gewinnt es schließlich.

Macht das nicht spaß


Ich war persönlich daran interessiert, wie dies zur Überprüfung der Software-Korrektheit angewendet werden kann. Jetzt testen wir Software, indem wir eine Reihe von Testeingaben auf sie werfen und (um zu einfach zu sein) sehen, ob sie auf einen Assert trifft. In einem Quantencomputer könnte es möglich sein, ihn parallel mit einer viel dichteren Menge von Eingaben zu betreiben und zu prüfen, ob einer dieser Fälle ein Assert trifft.

Als ob die Eingabe in den Algorithmus 128 Bytes oder 1024 Bits wäre, gibt es 2 ^ 1024 oder 10 ^ 308 mögliche verschiedene Eingaben. Es gibt keine Möglichkeit, so viele Eingaben auf einem herkömmlichen Computer zu testen, aber ein Quantencomputer könnte sie alle parallel testen.

Mike Dunlavey
quelle
2
Schauen Sie sich Grovers Suchalgorithmus an ... OH GOTT! Ich war nicht bereit dafür!
Philip,
1
@Philip: Ich weiß, dass die Mathematik ziemlich abstoßend ist, aber die Schlüsselidee ist die Rotation um den Mittelwert, wodurch die Wahrscheinlichkeit auf den Antwortstatus übertragen wird. Dann rennst du zurück zum Anfang und rennst vorwärts und machst es noch einmal, eine bestimmte Anzahl von Malen. Wenn Sie dann die Beobachtung durchführen, haben Sie die Wahrscheinlichkeit maximiert, den Antwortstatus zu sehen.
Mike Dunlavey
Sie sehen, es ist wirklich nicht so schlimm, wenn Sie es so sagen. Ich bin wahrscheinlich nicht mit der verwendeten Notation oder den Quantenschaltungen vertraut. Die Seite über Quantenalgorithmen ist ebenfalls einschüchternd. Ich glaube, dass Qubit der Ausgangspunkt ist. (Einfache Wikipedia hat eine Seite über Quantencomputer , aber es könnte etwas Arbeit gebrauchen)
Philip
@Philip: Angenommen, Sie haben eine Tabelle mit 1024 Einträgen, und es werden 10 Bits benötigt, um sie zu indizieren. Sie haben ein 10- (qu) Bit-Register und es hat 1024 mögliche Zustände. OK, Sie erstellen ein Universum, in dem das Register 0 ist, ein anderes, in dem es 1 ist, bis zu 1024 parallele Universen. Dann arbeiten die Quanten- "Befehle" an all diesen parallel. Jedes Universum hat einen "Amplitudenvektor", dessen Größe seine Wahrscheinlichkeit ist, aber er hat auch eine Richtung, und diese werden manipuliert. Da die Sammlung von 1024 Vektoren einen Nicht-Null-Durchschnittsvektor aufweist, wird durch die Drehung einer größer, der Rest kleiner.
Mike Dunlavey
Ich bin ein reformierter Physiker und habe diese Antwort abgelehnt, weil sie irreführend ist. 1) Quantenalgorithmen häufig sind besonders (asymptotisch) schnell - Grover Suchalgorithmus läuft in O (sqrt (n)) , während die besten ein klassischer Computer tun kann , ist O (n). Wenn Quantencomputer nicht asymptotisch schneller wären, wären sie nicht sehr interessant. Die Hardware ist momentan möglicherweise langsam, aber das ist nicht der Fehler des Algorithmus!
Benjamin Hodgson
7

Wie würde eine C-ähnliche Sprache aussehen, wenn sie für Qubits ausgelegt wäre? Würden sich die Typen ändern?

Es wäre so drastisch anders, dass es so unverständlich wäre wie C.

Das Hauptproblem (so wie ich es verstehe) ist, dass Quanten-Computing nicht auf eine nette, zwingende Weise funktioniert: "Tu dies, dann das, dann das andere." Der Versuch, Cs Fähigkeit, dies zu tun, in den 'Prozessor' des Quantencomputers zu zwingen, wird, wenn nicht unmöglich, äußerst ineffizient sein.

Programmieralgorithmen für Quantencomputer (so wie ich sie verstehe) sind tendenziell näher an der funktionalen Programmierstil-Zuordnung / -Reduzierung, da Quantencomputer es allen Kandidaten im "Reduktions" -Teil ermöglicht, gleichzeitig zu existieren und aus dem Computer "herauszufallen" wenn beobachtet.

Beachten Sie, dass es einige Algorithmen für Quantencomputer gibt, obwohl die Geräte für deren Ausführung nicht vorhanden sind. Zum Beispiel Simons Algorithmus .

Telastyn
quelle
ELI5 für einen Quantenalgorithmus wäre großartig.
MaiaVictor
3

Um einen Quantencomputer möglichst effektiv nutzen zu können, muss man in der Lage sein, mit Ein- und Ausgängen umzugehen, die Zustände eines Quantenregisters sind, für das es eigentlich kein klassisches Analogon gibt. Aus einigen Jahren Erfahrung auf dem Gebiet der Quanteninformation muss ich Sie warnen, dass niemand über die abstrakte Mathematik der C * -Algebren hinaus wirklich eine gute Intuition dafür hat, und mir wurde gesagt, dass sich selbst diese Intuition als unzureichend herausstellt wenn Sie anfangen, sich über die Relativitätstheorie zu wundern.

Die Klasse von Problemen, die auf einem Quantencomputer effizient lösbar sind, wird als BQP für Bounded Quantum Polynomial bezeichnet. Dies ist die Quantenversion von BPP. Weitere Informationen finden Sie in diesem Artikel: http://www.scottaaronson.com/papers/bqpph.pdf

Mir wurde erst letzte Nacht von einem Quantenalgorithmusforscher gesagt, dass es ein sehr wichtiges Problem gibt, das BQP-vollständig ist: das Lösen eines linearen Systems von N Gleichungen. Klassischerweise ist dies in O (N) -Schritten mit Gauß-Eliminierung lösbar. Der Harrow-Hassidim-Lloyd-Algorithmus ( http://arxiv.org/abs/0811.3171 ) löst ihn in polylog (N) auf, sofern Sie bereit sind, eine Antwort zu akzeptieren, deren Lösung als Quantenzustand codiert ist. Wenn Sie einen Quantencomputer voll ausnutzen möchten, müssen Sie daher einen Typ haben, der dem Status eines Quantenregisters entspricht.

Obwohl ich mich momentan ein wenig von meinem Fachwissen distanziere, würde ich vermuten, dass Sie in der Lage sind, einen Quantencomputer zu programmieren, solange Sie Zugriff auf einen Typ haben, der magischen Zuständen entspricht. Das ist jedoch ein schwieriges Konzept, das eine gründliche Untersuchung des Themas erfordert.

Seien Sie gewarnt, dass wir noch lange keine Quantenprogrammiersprache haben, da wir uns in einem sehr primitiven Stadium der Quantencomputerforschung befinden. Nach einem Quantum C zu fragen, würde bedeuten, zu Alan Turing zu gehen und ihn zu bitten, Python zu entwerfen. Wir haben noch nicht einmal die Quantenversion der Vakuumröhre!

Kernel
quelle