Wie leistungsfähig ist genaues „Quanten-Computing“, wenn Sie die Einheitlichkeit aufheben?

15

Kurze Frage.

Was ist die Rechenleistung von "Quanten" -Schaltungen, wenn wir nicht einheitliche (aber immer noch invertierbare) Gatter zulassen und vom Ausgang verlangen, dass er mit Sicherheit die richtige Antwort gibt?

Diese Frage handelt in gewissem Sinne davon, was mit der Klasse passiert, EQPwenn Sie zulassen, dass die Schaltkreise mehr als nur einheitliche Gatter verwenden. (Wir sind immer noch gezwungen, uns auf invertierbare Gatter über wenn wir in der Lage sein wollen, ein genau definiertes Rechenmodell zu haben.)C

(Diese Frage wurde im Lichte einiger Unklarheiten in Bezug auf die bekannten Ergebnisse in Bezug auf solche Schaltungen im einheitlichen Fall überarbeitet.)

Über "genaue" Quantenberechnung

dieser Frage willen definiere ich als die Klasse von Problemen, die durch eine einheitliche Quantenschaltungsfamilie exakt gelöst werden kann, wobei die Koeffizienten jeder Einheit durch polynomzeitbegrenzte Turingmaschinen (aus dem Eingabezeichenfolge ) für jede Eingabegröße n , und dass das Layout der Schaltung als gerichtetes Netzwerk auch in Polynomialzeit erzeugt werden kann. Mit "genau" gelöst meine ich, dass das Messen des Ausgangsbits | ergibt 0 mit Sicherheit für NO - Instanzen und | 1 mit Sicherheit für Ja - Instanzen.1 nEQ.P1nn|0|1

Vorsichtsmaßnahmen:

  • Dieser Begriff von beschränkt sich sogar auf unitäre Gatter und EQ.Punterscheidet sich von dem von Bernstein und Vazirani unter Verwendung von Quantenturing-Maschinen beschriebenen. Die obige Definition erlaubt es einer Schaltkreisfamilie {Cn} , im Prinzip eine unendliche Tormenge zu haben - jede einzelne Schaltung Cn verwendet natürlich nur eine endliche Teilmenge -, da die Tore tatsächlich aus den Eingängen berechnet werden. (Eine Quanten-Turing-Maschine kann jede beliebige endliche Gate-Menge simulieren, kann jedoch nur endliche Gate-Mengen simulieren, da sie nur eine endliche Anzahl von Übergängen aufweist.)

  • Dieses Rechenmodell trivialisiert alle Probleme in P , da die Einheit ein einzelnes Gatter enthalten könnte, das die Lösung eines Problems in fest codiert P(seine Koeffizienten werden schließlich durch eine Mehrfachzeitberechnung bestimmt). Daher ist die spezifische zeitliche oder räumliche Komplexität von Problemen für solche Schaltungen nicht unbedingt interessant.

Wir können diesen Vorbehalten die Beobachtung hinzufügen, dass praktische Implementierungen von Quantencomputern sowieso Rauschen aufweisen. Dieses Modell der Berechnung ist interessant , in erster Linie aus theoretischen Gründen , wie man sich mit unitären Transformationen nicht machbar Berechnung Komponieren, und auch als eine genaue Version von . Insbesondere trotz der Vorbehalte oben, haben wir PE Q PB Q P .BQPPEQPBQP

Der Grund für die Definition von ist, dass DISCRETE-LOG in E Q P eingefügt werden kann . Von [  Mosca + Zalka 2003  ] gibt es einen Polynom-Zeit-Algorithmus zum Aufbau einer Einheitsschaltung, die DISCRETE-LOG-Instanzen exakt löst, indem sie in Abhängigkeit vom Eingangsmodul exakte Versionen der QFT erzeugt. Ich glaube, dass wir dann DISCRETE-LOG wie oben definiert in E Q P setzen können, indem wir die Elemente der Schaltungskonstruktion in die Art und Weise einbetten, wie die Gate-Koeffizienten berechnet werden. (Das Ergebnis von DISCRETE-LOG E Q P ist also im Wesentlichen von fiat abhängig , setzt jedoch auf die Konstruktion von Mosca + Zalka.)EQPEQPEQPEQP

Unitarität aufheben

Sei die Rechenklasse, die wir erhalten, wenn wir die Einschränkung aufheben, dass Gatter einheitlich sind, und ihnen erlauben, sich über invertierbare Transformationen zu erstrecken. Können wir diese Klasse in andere traditionelle nicht deterministische Klassen C einordnen (oder sie sogar charakterisieren) ?EQPGLC

Einer meiner Gründe zu fragen: ob die Klasse von Problemen ist , die durch einheitliche "uneinheitliche Quanten" -Schaltungsfamilien effizient mit beschränktem Fehler lösbar sind - wobei JA-Instanzen eine Ausgabe von | ergeben 1 mindestens mit der Wahrscheinlichkeit 2/3, und keine Instanzen mit Wahrscheinlichkeit höchstens 1/3 (nach dem Stand Vektor Normalisieren) - , dann [Aaronson 2005] zeigt , dass B Q P G L = P P . Das heißt: Die Aufhebung der Einheitlichkeit ist in diesem Fall gleichbedeutend mit der Ermöglichung eines unbegrenzten Fehlers.BQPGL|1BQPGL=PP

Erhalten Sie ein ähnliches Ergebnis oder ein eindeutiges Ergebnis für ?EQPGL

Niel de Beaudrap
quelle
2
Intuitiv würde ich als C o C = P erraten . CCoC=P
Tayfun Pay
Es ist keine schlechte Vermutung, da die unbegrenzte (einseitige) Fehlerversion von E Q P ist, ebenso wie P P die unbegrenzte Fehlerversion von B Q P ist ; und P P enthält sowohl C = P als auch sein Komplement, da P P unter Schnitt und Komplement geschlossen ist. coC=P=NQPEQPPPBQPPPC=PPP
Niel de Beaudrap
Ist es offensichtlich, dass NP in dieser Klasse enthalten ist? (Und ist diese Klasse die gleiche wie EQP mit Nachauswahl?)
Robin Kothari
2
@RobinKothari: Beides würde ich aufgrund der Null-Fehler-Bedingung nicht als offensichtlich ansehen. Die zweite Frage scheint wahrscheinlicher als die erste. Meine Übereinstimmung mit Tayfun, dass (... und daher auch C = P ) eine vernünftige Annahme ist, dass, wenn es sich um eine zuvor definierte Klasse handelt, diese eine Primzahl ist verdächtig, aber natürlich, wenn es wahr wäre, wäre es keine triviale Beobachtung. EQPGL=coC=PC=P
Niel de Beaudrap
Kennst du ein Problem in dieser Klasse, das nicht in P ist?
Robin Kothari

Antworten:

6

Kurze Antwort. Es stellt sich heraus, dass das Aussetzen der Anforderung einheitlicher Transformationen und das Erfordernis, dass jede Operation invertierbar ist, zu exakten lückendefinierbaren Klassen führt. Die fraglichen spezifischen Klassen sind und eine "neue" Unterklasse L P W P P , die beide zwischen S P P und C = P liegen . Diese Klassen haben ziemlich technische Definitionen, die im Folgenden kurz beschrieben werden. Diese Definitionen können nun im Prinzip durch Definitionen für nicht einheitliche "quantenähnliche" Algorithmen ersetzt werden.LWPPLPWPPSPPC=P

Die Zählklasse enthält GRAPH ISOMORPHISM. Es enthält auch die gesamte Klasse U P , so dass wir nicht erwarten würden, dass exakte einheitliche Quantenalgorithmen so leistungsfähig sind wie die nicht-einheitlichen Klassen (da wir sonst N P B Q P zeigen könnten ).SPPUPNPBQP

Längere Antwort.

  • In meiner Frage schlug ich vor, zu definieren, um Probleme zu berücksichtigen, die durch einheitliche Schaltkreisfamilien lösbar sind, die Gates verwenden, die effizient berechenbar sind, aber nicht notwendigerweise aus einem endlichen Gatesatz gezogen werden. Ich bin mir nicht mehr so ​​sicher, dass es eine gute Idee ist, E Q P auf diese Weise neu zu definieren , obwohl ich glaube, dass es sich lohnt, solche Schaltkreisfamilien zu studieren. Wir können diese Klasse stattdessen so etwas wie U n i t a r y P C nennen .EQP EQPUnitaryPC

    Es ist möglich , zu zeigen , daß , das bis vor kurzem wurde die gebundene für bekannte besten E Q P . Die Klasse L W P P entspricht mehr oder weniger Problemen, für die es einen randomisierten Algorithmus gibt, bei dem NO-Instanzen mit einer Wahrscheinlichkeit von genau 0,5 ein Ergebnis von 1 erzeugen und YES-Instanzen mit einer gewissen Wahrscheinlichkeit ein Ergebnis von 1 erzeugen, das effizient sein kann und genau berechnet in rationaler Form, die größer als (aber möglicherweise exponentiell nahe bei) 0,5 ist. Die technische Definition von L W PUnitaryPCLWPPEQPLWPP wird in nichtdeterministischen Turingmaschinen dargestellt, leuchtet aber nicht mehr.LWPP

    Definieren wir als das Invertible-Gate-Äquivalent von U n i t a r y P C , so dass es die Menge von Problemen ist, die von invertierbaren Schaltkreisfamilien mit effizient berechenbaren Gate-Koeffizienten genau lösbar sind , dann G L P C = L W P P .GLPCUnitaryPCGLPC=LWPP

  • Wenn wir uns auf endliche Gatesätze beschränken, ist es möglich zu zeigen, dass einheitliche Schaltkreisfamilien in einer Teilmenge von simuliert werden können , die wir L P W P P nennen könnten . (Unter Verwendung der obigen Beschreibung von L W P P entspricht dies randomisierten Algorithmen, bei denen die Wahrscheinlichkeit, eine Ausgabe von 1 für JA-Instanzen zu erhalten , für einige Polynome p , einige genau m t ( x ) / 2 p ( | x | ) beträgt ganze Zahl mLWPPLPWPPLWPPmt(x)/2p(|x|)pmund einige effizient berechenbare Polynome .)t

    Wenn wir definieren , zu sein , die invertierbaren-Gate - Äquivalent von E Q P , wie es in der Regel definiert ist, können wir zeigen , daß E Q P G LL P W P P .EQPGLEQPEQPGLLPWPP

Eine Korrektur bezüglich DISCRETE LOG.

Die obigen Ergebnisse beruhen auf Standardtechniken zur Darstellung algebraischer Koeffizienten in einer Art und Weise, die von der Eingabe unabhängig ist (jedoch von der Eingabegröße abhängen kann). In der Beschreibung der ursprünglichen Frage habe ich behauptet, dass [ Mosca + Zalka 2003 ] zeigt, dass DISCRETE LOG durch ein Gate-Set mit effizient berechenbaren Koeffizienten genau lösbar ist. Die Wahrheit scheint komplizierter zu sein. Wenn es um die exakte Lösbarkeit geht, halte ich die exakte Darstellung der Koeffizienten für wichtig: Mosca und Zalka bieten jedoch keine Möglichkeit, dies eingabeabhängig zu tun. Es ist also nicht offensichtlich, dass DISCRETE LOG tatsächlich in oder in der neuen Klasse U n i t a r y P istEQP .UnitaryPC

Referenz.

  • de Beaudrap, Über genaues Zählen und Quasi-Quanten-Komplexität , [ arXiv: 1509.07789 ].
Niel de Beaudrap
quelle
Sehr schön!!! Eine naive Frage: Was ist die Leistung von Schaltkreisen, die Sie beschrieben haben (beliebig invertierbar; genau oder ungefähr), wenn Sie die Komplexität der Stichprobe berücksichtigen. (Nämlich die Klasse der Wahrscheinlichkeitsverteilungen, die sie geben können.)
Gil Kalai
@GilKalai: Wenn Sie den Verteilungen, die diese Schaltkreise berechnen, keine Invariante auferlegen (dh indem sie die 1-Norm oder die 2-Norm beibehalten), müsste man genau definieren, wie man die Tensoren abbilden möchte welche solche Schaltungen zu Wahrscheinlichkeitsverteilungen beschreiben. Wenn man sich vorstellt, dass es sich bei diesen Verteilungen eher um geheime Quantenzustände als um Pseudowahrscheinlichkeitsverteilungen handelt, könnte man sich auf die übliche Weise, die ein Physiker wählen könnte, neu normieren, aber diese Wahl ist uns nicht aufgezwungen.
Niel de Beaudrap
Abgesehen davon: Welche Einschränkung man auch auferlegt, ich weiß nicht sofort, wie ich die Frage beantworten soll. Aber aus Aaronsons Arbeit an PostBQP wissen wir, dass die ungefähre Stichproben-Klasse mindestens PP- hart ist.
Niel de Beaudrap