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

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?

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:

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.

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 .

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!