Was macht Quantencomputer konkret nützlich?

18

Ich weiß, dass Quantencomputer eine Überlagerung aller möglichen Zustände mit einem einzigen Durchlauf durch die Logik verarbeiten können.

Das scheint das zu sein, was die Leute als das bezeichnen, was Quantencomputer besonders oder nützlich macht.

Nachdem Sie die Überlagerungseingaben verarbeitet haben, haben Sie ein Überlagerungsergebnis, von dem Sie nur eine einzige Frage stellen können und das zu einem einzigen Wert zusammenfällt. Ich weiß auch, dass es (derzeit?) Nicht möglich ist, den Überlagerungszustand zu klonen, sodass Sie keine Antwort auf diese eine Frage bekommen.

In beiden Fällen sieht es so aus, als hätten Sie mit der Multi-Processing-Fähigkeit wirklich nichts erreicht, da es praktisch so aussieht, als ob nur ein Status verarbeitet wurde.

Bin ich falsch interpretiert, oder kommt der wahre Nutzen des Quantencomputers von etwas anderem?

Kann mir jemand erklären, was das noch ist?

Alan Wolfe
quelle
2
Einige Aufgaben können mit Quantencomputern schneller gelöst werden. Siehe einige Hinweise
Ran G.
Danke für den Link, ich werde es überprüfen. Ich weiß, dass sie in einigen Dingen schneller sind, aber ich versuche zu verstehen, wie und warum Sie dabei helfen können (:
Alan Wolfe
4
Der springende Punkt ist die Störung . Scott Aaronson hat mehrere populäre Essays darüber geschrieben; versuche sie online zu durchsuchen. Siehe auch sein Buch "Quantum Computing Since Democritus", das auf den Vorlesungsskripten basiert, die hier zu finden sind . Irgendwo in der Nähe von Kapitel 10 sollte man sich diesen Ort als Ausgangspunkt ansehen.
Ran G.
Ich habe einige dieser Artikel gelesen und bin einigen Links gefolgt. interessant! Ich mag es, wie Scott mit Bestimmtheit sagt, es sei BS, dass Quantencomputer alle Möglichkeiten auswerten und in einem Schritt die richtige Antwort finden können. Kann ich raten, was Störungen bewirken? Zerstört (oder kollabiert) es mögliche Zustände der Überlagerung, die keine gültigen Lösungen sind?
Alan Wolfe
1
"Ich weiß auch, dass es (derzeit?) Nicht möglich ist, den Überlagerungszustand zu klonen." Das No-Cloning-Theorem besagt, dass dies eher eine absolute Unmöglichkeit als eine Grenze der aktuellen Technologie ist. ("Absolut" in dem Sinne, dass, wenn es in Quantensystemen wirklich um einheitliche Transformationen von Hilbert-Räumen geht, Sie es nicht tun können; wenn sich einheitliche Transformationen von Hilbert-Räumen nur als Annäherungen herausstellen, dann können Sie es vielleicht doch tun .)
David Richerby

Antworten:

13

Zerstörerische Interferenzen sind das Wichtigste, was Quantencomputer leistungsfähiger macht. Bei einer klassischen probabilistischen Berechnung ist dieses Ergebnis immer wahrscheinlicher, wenn zwei Pfade zu einer Ausgabe vorliegen. In einem Quantencomputer kann dies das Ergebnis weniger wahrscheinlich machen.

Quantenalgorithmen werden sorgfältig entworfen, so dass falsche Antworten destruktiv beeinflusst werden und nur die gewünschten Lösungen als Messergebnisse übrig bleiben. Dies ist schwierig, und nicht jedes Problem lässt es zu. Grover Suchalgorithmus ist ein ausgezeichnetes Beispiel für diesen Effekt, also hier ist ein Anfänger-Level - Beitrag über Grover-Algorithmus .

Andere nützliche Eigenschaften, auf die Quantencomputer zugreifen können:

(Scott Aaronson sagt gern, dass alles, was an Quanten interessant ist, auf Überlagerungen zurückzuführen ist , bei denen die 2-Norm anstelle der 1-Norm beibehalten wird, wie es Wahrscheinlichkeitsverteilungen tun. Alle spezifischeren nützlichen Effekte, die ich erwähnt habe, stammen aus der zugrunde liegenden Mathematik.)

Craig Gidney
quelle
5

Einige Ihrer Fragen sind offene theoretische Fragen. Es gibt verschiedene Möglichkeiten, Ihre Frage zu beantworten. Ein allgemeiner Ansatz zum QM-Computing ist die Nutzung der Spintronik dh die Quanteneigenschaft des Spins, für die Berechnung zu nutzen. Es ist also ein logischer nächster Schritt bei der Miniaturisierung von Elektronik / Logik und der Berechnung im Allgemeinen. Es gibt theoretische Grenzen für die Gate-Breite, die in der aktuellen Fertigungstechnologie überschritten werden. Eine konsequente Verschiebung des Moores-Gesetzes und der Spintronik stellt die "nächste Grenze" dar.

2xxist die Anzahl der Qubits, dh der exponentielle Anstieg der Rechenfähigkeit für den linearen Anstieg der Qubits. Dies klingt fast wie aus Science-Fiction, ist aber, soweit bekannt, eine scheinbar "echte / intrinsische" Eigenschaft.

Ein entscheidender Durchbruch im Jahr 1996 ist Shors Algorithmus , der gezeigt hat, dass Factoring in "Quantenpolynomialzeit" gelöst werden kann, und der als Anreiz für großes Interesse am Quantencomputing gilt. Das Faktorisieren ist natürlich das Herzstück moderner kryptografischer Systeme im weit verbreiteten RSA-Algorithmus .

Es ist eine offene theoretische Frage, ob Quantencomputer andere wichtige Probleme in "schnellerer" Zeit lösen können. Dies ist bekannt als BPP =? BQP- Frage.

Ein umstrittener QM-Computer wird von gebaut DWave gebaut, der sich bei der Lösung einiger Probleme als "nützlich" erwiesen hat, und sie haben erfolgreich eine Form der Quantenskalierung an einem "etwas schwächeren" Typ von QM-System demonstriert, das als adiabatisches Computing bekannt ist . Es ist eine offene Frage, ob es jemals eindeutige Geschwindigkeitssteigerungen zeigen kann / wird, die derzeit von Google, Nasa, Lockheed usw. recherchiert werden.

Kurz gesagt, Quantencomputer sind nicht genau im gleichen Sinne wie klassische Computer "nützlich" , da die genaue Art ihrer Nützlichkeit aktiv erforscht wird und nur begrenzte / experimentelle / prototypische Systeme existieren. Es wird vermutet, dass sie bei ihrer Realisierung "mindestens genauso nützlich" sind wie herkömmliche Berechnungen und möglicherweise / hoffentlich auf bestimmte, nicht genau vorhersehbare Weise "nützlicher" sind.

vzn
quelle
1
Es ist kein klassischer Algorithmus bekannt, der Zahlen in der Polynomzeit faktorisiert, und es ist ein großes Problem der offenen Komplexitätstheorie, ob es möglich ist, vermutet wird, dass es unmöglich ist und die RSA-Sicherheit ("fast") davon abhängt.
VZN
5

Eine eher kontroverse Antwort, aber denken Sie trotzdem daran.

Ich würde sagen, nichts macht Quantencomputer nützlicher (zumindest derzeit)!

Sicher, die übliche theoretische Behandlung der Quantenmechanik zum Rechnen im Vergleich zu einer klassischen theoretischen Behandlung bietet tatsächlich neue Möglichkeiten (wie andere Antworten festgestellt haben). Also, was ist der Haken hier?

Der Haken dabei ist: Es ist nicht sicher, dass Quantencomputer tatsächlich leistungsstärker sind als gewöhnliche / klassische Computer (eine Tatsache, die mit dem in Verbindung steht)P vs NPProblem) und dass klassische Computer keine Quantencomputer simulieren können. Sicher " Quantentheorie " wird es Ihnen sagen. Warum Zitate in der " Quantentheorie "? Da es sich nicht um eine Quantentheorie handelt, handelt es sich eigentlich nur um eine spezifische " Interpretation der Quantentheorie ". Hoffe, all dies ist verstanden und klar.

Verwandte Referenzen:

  1. Gibt es einen formalen Beweis dafür, dass Quantencomputing schneller ist oder sein wird als klassisches Computing?
  2. Von einem klassischen System emulierter Quantencomputer ( IOP-Papier )
  3. Erster 'Quantum Computer' schneller als ein klassischer PC
  4. Können Quantenmessungen klassische Computer schlagen?
  5. Einen Quantencomputer durch Simulation der Quantenmechanik schlagen
Nikos M.
quelle
Ja, danke für die Antwort. Es ist eine gute Perspektive, die man sich merken sollte. Wenn wir in der Lage wären, eine L2-Normberechnung oder eine Überlagerungsberechnung auf einem Computer durchzuführen, der destruktive Interferenzen oder dergleichen zulässt, könnten wir algorithmisch das bekommen, was wir wollen, ohne einen Quantencomputer erstellen zu müssen. Gute Argumente!
Alan Wolfe
@AlanWolfe, yeap, such nach "klassischem Quantencomputer" und / oder "klassischem Emulationsquanten" und sieh, was du bekommst. Aktualisierte Antwort mit einigen Verweisen auf den Punkt
Nikos M.