Ist BQP gleich BPP mit Zugang zu einem Orakel der verborgenen Abelschen Untergruppe?

complexity-classes quantum-computing Jason
quelle

Tatsächlich gibt es eine Menge Arbeit über nicht-abelsche Probleme versteckter Untergruppen in der Forschung mit Quantenalgorithmen, daher hoffe ich, dass dies nicht der Fall ist!

Joe Fitzsimons

@Joe: Ich dachte, der Großteil der Arbeit an nicht-abelianischen HSPs war für Gruppen gedacht, die irgendwie "nah an Abelian" sind - aber bitte korrigieren Sie mich, wenn ich falsch liege, da ich kein Experte auf diesem Gebiet bin. Wenn dies jedoch tatsächlich der Fall ist, kann eine positive Antwort auf die Frage den Werken, auf die Sie sich beziehen, nicht widersprechen.

Joshua Grochow

Antworten:

Wie bei vielen Trennungen von Komplexitätsklassen lautet unsere Vermutung, dass BPP ^ {HSP}! = BQP ist, aber wir können dies nur in Bezug auf Orakel rigoros beweisen. Diese Trennung wurde von Scott Aaronson in diesem Blogbeitrag beobachtet, in dem er feststellte, dass die Beschleunigung der Schweißbäume von Childs, Cleve, Deotto, Farhi, Gutmann und Spielman nicht in der SZK enthalten war.

Auf der anderen Seite, BPP ^ {HSP} ist in SZK, zumindest enthalten ist, wenn das Ziel , die Größe der verborgenen Untergruppe zu bestimmen ist. Dies schließt sogar die abelsche HSP ein, obwohl ich nicht sicher bin, wie man die Generatoren einer willkürlich versteckten Untergruppe in SZK genau findet. Der Grund, warum wir die Größe der versteckten Untergruppe bestimmen können, ist, dass wenn f: G-> S die versteckte Untergruppe H hat und wir g gleichmäßig zufällig aus G auswählen, f (g) gleichmäßig zufällig über eine Menge von Größe | G ist | / | H |. Insbesondere hat f (g) ein Entropielog | G | - log | H |. Und die Entropieschätzung erfolgt in SZK.

Aram Harrow
quelle

Ich wusste, dass ich irgendwo einen Blog-Post darüber gesehen hatte!

Joe Fitzsimons

Ich habe keine Ahnung, wie man eine solche Behauptung widerlegen würde, aber ich bezweifle, dass es wahr ist. Wir haben andere exponentielle Beschleunigungen durch Quantenalgorithmen, die nicht auf dem abelschen HSP beruhen. Darüber hinaus ist nicht bekannt, dass Abelian HSP BQP-vollständig ist.

Andererseits sind Probleme, von denen bekannt ist, dass sie BQP-vollständig sind, Probleme wie das Berechnen von Knoteninvarianten, anderen mannigfaltigen Invarianten, Partitionsfunktionen und das Durchführen einer Hamilton-Simulation. Mit einem Orakel für eines dieser Probleme wäre BPP so mächtig wie BQP.

Schließlich bin ich sicher, dass man eine Orakeltrennung zwischen den beiden von Ihnen genannten Klassen konstruieren kann, aber das wäre kein fairer Vergleich, da eine Klasse Quantenabfragen stellen kann und die andere nicht, sodass die Trennung nur diese Tatsache widerspiegeln würde .

Robin Kothari
quelle

Was sind die Hinweise auf Probleme mit Superpolynom-Beschleunigungen, die nicht auf dem abelschen HSP beruhen?

Marcos Villagra

Eine genauere Frage lautet: "Was sind die Hinweise auf Probleme mit Superpolynom-Beschleunigungen, die sich überhaupt nicht auf den HSP stützen?"

Marcos Villagra

Der Quantenalgorithmus-Zoo ( its.caltech.edu/~sjordan/zoo.html ) hat eine große Liste von Algorithmen und Referenzen für jede.

Robin Kothari

@Joshua: Diese Orakeltrennungen sind in Ordnung, weil sie versuchen, die Kraft von Quantenabfragen aufzuzeigen. Lassen Sie mich ein Beispiel geben, was ich meine. Wenn es einen Polytime-Algorithmus für 3SAT gäbe und dieser Algorithmus X heißen würde. Offensichtlich enthält P ^ X NP. Wir können jedoch eine Orakeltrennung zwischen P ^ X und NP konstruieren, da im ersten Fall nur die P-Maschine auf das Orakel zugreifen kann und die Trennung lediglich die Tatsache widerspiegelt, dass nicht deterministische Abfragen besser sind als deterministische Abfragen. Auch wenn BPP ^ AHSP BQP enthielte, konnten wir sie ziemlich leicht mit einem Orakel trennen.

Robin Kothari

Danke für alle Antworten. Insbesondere danke, dass Sie mich an die Jones- und HOMFLY-Polynome erinnert haben, die nichts mit HSPs zu tun haben. Die Bewertung des Jones-Polynoms genau an der fünften Wurzel der Einheit ist # P-schwer, die Approximation auf einen Bruchteil Epsilon mit einer gewissen Wahrscheinlichkeitsgenauigkeit erfolgt jedoch in BQP.

Jason

Ich muss Robin zustimmen, dass dies nicht unbedingt eine einfache Behauptung ist, obwohl es mit ziemlicher Sicherheit falsch ist. Ein unmittelbarer Grund, den ich bezweifle, ist, dass die nachgewählte Quantenberechnung gleich PP ist, und dies scheint darauf hinzudeuten, dass die Statistik schwierig wiederherzustellen wäre. Scott Aaronson hat in einer Arbeit bei STOC aufgezeigt, dass es ein Orakel-Beziehungsproblem gibt, das in BQP, aber nicht in PH lösbar ist.

$BPP^{NP} = P^{\#P}$

Joe Fitzsimons
quelle

P ^ {# P} = P ^ {PP}, also könnten Sie das stattdessen verwenden.

Robin Kothari

Ja, das wäre klug gewesen!

Joe Fitzsimons