Gibt es Beweise dafür, dass Quantencomputer effizienter sind als klassische Computer?

Shors Algorithmus wird oft als Argument verwendet. Es kann das Faktorisierungsproblem schneller lösen als jeder bekannte Algorithmus für klassische Computer. Wir haben jedoch keinen Beweis dafür, dass klassische Computer Ganzzahlen nicht effizient berücksichtigen können.

Gibt es tatsächlich Beweise dafür, dass Quantencomputer einige Probleme schneller lösen können als klassische Computer?

algorithms efficiency quantum-computing MaiaVictor
quelle

Ein Teil davon wird formal in offenen Komplexitätsklassentrennungen wie BPP =? BQP (1. klassisch, 2. QM-orientiert) erfasst. Es gibt auch das Problem der Implementierung, dass (im Gegensatz zu klassischen Maschinen) nicht bekannt ist, ob QM wirklich physikalisch machbar ist. etc ... kann einiges davon in eine Antwort umwandeln.

vzn

Eng verwandt: Warum und wie ist ein Quantencomputer schneller als ein normaler Computer?

Gilles 'SO - hör auf böse zu sein'

Antworten:

Ja, der Grover-Algorithmus zeigt, dass Sie einen Quantenalgorithmus verwenden können, um ein Element in einer ungeordneten Datenbank der Größe mit hoher Wahrscheinlichkeit zu finden, indem Sie nur die Datenbank abfragen $N$ mal. Jede klassische Lösung, die mit hoher Wahrscheinlichkeit erfolgreich ist, erfordert-Abfragen an die Datenbank. $O(\sqrt{N})$ $\Omega (N)$

Ran G.
quelle

Erwähnenswert ist auch der Deutsch-Jozsa-Algorithmus. Bei Zugriff auf das Orakel einer Booleschen Funktion

, die bekanntermaßen einheitlich oder konstant ist (mit einheitlich meinen wir, dass sie für genau die Hälfte der möglichen Eingaben

ist ). Natürlich würde jeder klassische Algorithmus mindestens

Abfragen erfordern (in einer deterministischen Umgebung). Quantencomputer können dies mit einer Abfrage entscheiden.

f : {0, 1}^{n} \to {0, 1}

$f: \{0,1\}^n\rightarrow \left\{0,1\right\}$

0

$0$

2^{n - 1} + 1

$2^{n-1}+1$

Ariel

"Datenbank abbauen" - Ich denke, Sie nehmen den Ausdruck "Data Mining" möglicherweise etwas zu wörtlich. :-)

David Richerby

@ DavidRicherby verdammt Autokorrektur? (;

Ran G.

@ariel Ich denke, das verdient eine zusätzliche Antwort! warum fügst du es nicht hinzu? (Sie können auch erwähnen, dass dies die Ideen für Simons Algorithmus liefert, die sich wiederum auf Shors Algorithmus beziehen)

Ran G.

"Jede klassische Lösung, die mit hoher Wahrscheinlichkeit erfolgreich ist, erfordert Ω (N) -Abfragen an die Datenbank" - Gilt dies auch für Nicht-Black-Box-Modelle? Ist das bewiesen?

user976850

Es kommt darauf an, was Sie als tatsächlichen Beweis betrachten und was Sie unter "schneller" verstehen. Aus komplexitätstheoretischer Sicht lautet die Antwort nein - wir haben keinen solchen Beweis. BQP (die Klasse von Problemen, die von einem Quantencomputer effizient gelöst werden können) ist in PSPACE enthalten. Die Möglichkeit, eine Trennung zwischen BQP und PSPACE nachzuweisen, würde auch eine Trennung zwischen P und PSPACE bedeuten, die nicht bekannt ist.

Beachten Sie, dass der Grover-Algorithmus nur eine Quadratwurzel-Beschleunigung liefert, sodass kein Widerspruch besteht.

Norbert Schuch
quelle

Herzlich willkommen! Leider scheint sich Ihre Antwort zu widersprechen. Sie sagen, "aus komplexitätstheoretischer Sicht ist die Antwort nein", aber dann geben Sie ein komplexitätstheoretisches Argument an, dass die Antwort "wir wissen nicht" lautet, und ein anderes, dass die Antwort "ja" lautet. Wie ist die Antwort nein?

David Richerby

\neq

$\ne$

Die Frage lautet, ob es einen "tatsächlichen Beweis gibt, dass Quantencomputer einige Probleme schneller lösen können als klassische Computer". Der Grover-Algorithmus ist nachweislich schneller als jeder klassische Algorithmus, daher lautet die Antwort eindeutig "Ja".

David Richerby

Der Algorithmus von @DavidRicherby Grover basiert auf einem Orakel (dies ist eine Black Box), auf das Sie bei echten Problemen nicht stoßen . Sobald Sie die Struktur des Problems im Orakel betrachtet haben (z. B. Überprüfung einer Lösung für ein NP-vollständiges Problem), ist (afaik) nicht klar, ob die Beschleunigung anhält.

Norbert Schuch

Diese Antwort ist etwas verwirrend zu lesen. Ich denke, es wäre hilfreich, die Antwort zu bearbeiten, um diese Punkte zu klären und genau zu überlegen, welche Behauptungen Sie aufstellen möchten und welche Argumentation Sie zur Unterstützung dieser Behauptungen anbieten können. Ich denke, es gibt zwei Punkte, die zur Klärung beitragen: (a) den Unterschied zwischen einer Beschleunigung in Polynomzeit und einer größeren Beschleunigung, (b) den Unterschied zwischen einem Algorithmus mit einem Orakel und einem gewöhnlichen Algorithmus. Verwenden Sie diese, um zu erklären, warum der Grover-Algorithmus eine Beschleunigung aufweist, was Ihren anderen Aussagen jedoch nicht widerspricht.

-1

Sie fragen nach "Beweisen", die möglicherweise auf eine mathematische Ebene beschränkt sind, aber die grundlegende Frage geht viel tiefer. Theoretiker werden anerkennen, dass es im Grunde immer noch eine offene Frage im Allgemeinen zur relativen Leistung von Quanten- und klassischen Algorithmen ist, und es gibt wahrscheinlich keine einfache / allgemeine Antwort, aber mit einem gewissen Konsens der Experten scheint der Shors-Algorithmus "ungewöhnlich schnell im Vergleich zur erwarteten besten klassischen Geschwindigkeit" zu sein . " Durch schnelles Factoring in einem klassischen Computer werden weit verbreitete kryptografische Sicherheitsannahmen wie das RSA- System verletzt .

Ein Teil davon wird formal in der offenen Komplexitätsklassenfrage BPP =? BQP Frage. Dies sind die analogen klassischen und Quantenklassen und die Trennung ist unbekannt und ein aktives Forschungsgebiet.
Eine eng verwandte Frage ist, ob physikalisch QM-Computer gebaut werden können, die den theoretischen Spezifikationen entsprechen, und einige / eine Minderheit von Wissenschaftlern (auch bekannt als "Skeptiker") argumentieren, dass es möglicherweise Rausch- oder Skalierungsgesetze gibt, die die in der Theorie vorgesehene QM-Skalierung verhindern. In gewissem Sinne muss der ultimative "Beweis" für die Geschwindigkeit eines QM-Computers eine physische Implementierung sein. (Dies ähnelt der Art und Weise, wie die Church-Turing-These theoretisch ist, scheint aber letztendlich mit einer Behauptung über physikalische Implementierungen verbunden zu sein.) Einige Forscher sprechen über Church-Turing-Analoga im QM-Computing. siehe zB Church Turing These in einer Quantenwelt von Montanaro.
Relevant für diese Frage / Debatte sind fortlaufende substanzielle / "hitzige" (wissenschaftliche) Versuche, den aktuellen "größten" Quantencomputer der Welt von DWave zu bewerten. Dies ist ein großes Thema mit viel verwandtem Material, aber für einen relativ aktuellen Überblick versuchen Sie, die D-Wave-Benchmark-Studie zu bestreiten, die einen trägen Quantencomputer / das Register zeigt

vzn
quelle