Rechenmodelle, die hinsichtlich der Komplexität von Abfragen streng zwischen Klassik und Quanten liegen

18

Es ist bekannt, dass Quantencomputer hinsichtlich der Komplexität von Abfragen strikt leistungsfähiger sind als ihre klassischen Gegenstücke .

Gibt es andere (natürliche oder künstliche) Modelle, die in Bezug auf die Komplexität von Abfragen streng zwischen dem Quanten- und dem Klassischen liegen?

Die Trennung kann eingeschaltet sein

  • Spezifische Probleme: Modell X berechnet Funktion mit streng mehr Abfragen als Quanten, aber weniger Abfragen als die untere Grenze für Klassiker oderf
  • Unterschiedliche Probleme: Modell X berechnet die Funktion mit streng mehr Abfragen als die Quantenfunktion, berechnet die Funktion f 2 jedoch mit weniger Abfragen als die klassische Funktion.f1f2

In beiden Fällen wollen wir für jede Funktion haben Q 2 ( f ) ≤ X ( f ) ≤ R 2 ( f ) Beispiele zu vermeiden , die (wie die Quanten zu vergleichen sind hart Zertifikat Komplexität von nicht-determinis Abfragen). Hier ist Q 2 ( f ) (und R 2 ( f ) ) die zweiseitige 1 / 3- Fehlerquanten- (und klassisch randomisierte) Abfragekomplexität, und die Ungleichungen liegen innerhalb konstanter Faktoren.fQ2(f)≤X(f)≤R2(f)Q.2(f)R2(f)1/3

cc.complexity-theory quantum-computing query-complexity Artem Kaznatcheev
quelle

Antworten:

8

Eine einfache Möglichkeit, ein solches Modell zu entwickeln, besteht darin, zunächst ein eingeschränktes Modell für die Quantenberechnung zu erstellen, das immer noch etwas Nicht-Klassisches ausführen kann, und es dann einfach kostenlos für die klassische Berechnung bereitzustellen.

Ein Beispiel für diese Strategie ist das One-Clean-Qubit-Modell (zusammen mit einer BPP-Maschine). Einige Referenzen: Die Potenz von einem Bit Quanteninformation , die Berechnung mit Unitaries und einem reinen Qubit und die Schätzung von Jones-Polynomen ist ein komplettes Problem für ein sauberes Qubit .

Ein anderes Beispiel wäre eine Log-Tiefen- (oder Polylog-Tiefen-) Quantenschaltung mit Zugang zu einem klassischen Computer. Dies wird so etwas wie ergeben .BPPBQ.NC

Robin Kothari
quelle
Dies funktioniert zwar für die Komplexität von Berechnungen, funktioniert es jedoch für die Komplexität von Abfragen? Ich sehe nicht sofort ein Problem, für das das One-Clean-Qubit-Modell + BPP eine bessere Abfragekomplexität ergibt als eine klassische Maschine. Außerdem kann diese Technik im Allgemeinen versagen, da eine klassische Berechnung einer Clifford-Gruppe oder eines Match-Gate-Computers sie zu einer universellen Quantenberechnung anregt.
Joe Fitzsimons
@JoeFitzsimons: Ich kann mir kein Problem vorstellen, aber ich denke, Dan Shepherd zeigt eine Orakel-Trennung zwischen BPP und dem einen sauberen Qubit-Modell in seiner Arbeit. Ihr zweiter Punkt ist natürlich gültig.
Robin Kothari
Aber eine Orakeltrennung impliziert sicherlich nicht notwendigerweise eine Abfragekomplexitätstrennung.
Joe Fitzsimons
Ich stimme @JoeFitzsimons zu, obwohl das DQC1-Modell interessant ist, habe ich keine Trennung der Abfragekomplexität dafür gesehen. Die natürlichen Probleme wie die Spurenschätzung oder Peter Shors Variante des Jones-Polynomproblems scheinen im Abfragemodell schwer darzustellen zu sein.
Artem Kaznatcheev
7

X(f)≤D(f)R2(f)

Joe Fitzsimons
quelle
2
P⊕LPL
2

Vielleicht ist das klarere Beispiel für diese Art von Rechenmodellen DQC1, das von @RobinKothari in seiner Antwort erklärt wurde. Siehe die Referenzen in seiner Antwort für eine gute Einführung in das Modell.

Außerdem gab es vor kurzem einen schönen Artikel im Nature-Magazin über Quantum Discord. Quantendiskord ist ein informationstheoretisches Maß für nicht-klassische Korrelationen, das die Verstrickung verallgemeinert. Hier ist der Link . Sie werden dort sehen, dass es Beispiele für Berechnungen gibt, bei denen Verschränkung keine grundlegende Rolle spielt, dh andere nicht-klassische Korrelationen sorgen für eine Beschleunigung der Berechnung. Dies geschieht in DQC1, um die Spur einer Matrix zu berechnen (siehe Artikel von Datta, Shaji und Caves ). Der Artikel wirft die Frage nach "Quantendiskord-basierten Algorithmen" auf, dh Algorithmen, bei denen keine Verschränkung für die Quantenbeschleunigung erforderlich ist. Das ist etwas zwischen vollständiger Quantenberechnung und klassischer.

Ein weiteres Modell, das möglicherweise in diese Kategorie fällt (zwischen Vollquanten- und klassischem Modell), ist das lineare optische Modell von Arkhipov und Aaronson. Siehe diese Frage für eine nette Erklärung.

Ich weiß nicht, wo diese Modelle in Bezug auf die Komplexität von Abfragen hinpassen, könnte aber ein guter Ausgangspunkt sein.

Marcos Villagra
quelle