Probleme in BQP, aber vermutet, außerhalb von P zu sein

Wikipedia listete vier Probleme auf, die in jedoch vermutet wird, dass sie außerhalb von : Ganzzahlfaktorisierung; Diskreter Logarithmus; Simulation von Quantensystemen; Berechnung des Jones-Polynoms an bestimmten Wurzeln der Einheit.$BQP$$P$

Gibt es noch andere solche Probleme?

Eine Liste solcher Probleme finden Sie in der Liste der Superpolynom-Geschwindigkeitsverbesserungen im Quantenalgorithmus zoo (QAZ). Die folgende Liste basiert darauf (siehe QAZ für genaue Definitionen und Verweise. Dies ist eine andere Art zu sagen, dass ich nicht einmal vorgebe, viele der Probleme dieser Liste zu verstehen!)

Algebraische und zahlentheoretische Probleme

Wenn ich mich nicht irre, sind alle Probleme, die vor dem Problem mit den versteckten Abelschen Untergruppen aufgeführt sind, Spezialfälle davon.

• Faktorisierung
• Diskreter Logarithmus
• Pells Gleichung . Faktorisierung reduziert sich auf Pells Gleichung.
• Hauptideal Ideales Problem. Pells Gleichung reduziert sich auf dieses Problem, das daher mindestens so schwer ist wie Factoring.
• Einheitsgruppenproblem
• Klasse Gruppenproblem
• Gauß Summenschätzung
• Matrixelemente von Gruppendarstellungen
• Gruppenreihenfolge und Mitgliedschaft
• Das Abelsche versteckte Untergruppenproblem
• Einige (aber nicht alle) nicht-abelianischen Probleme mit versteckten Untergruppen
• Einige (aber nicht alle) Probleme wurden als Spezialfälle des Problems der versteckten Schicht formuliert
• Einige (aber nicht alle) Probleme mit versteckten nichtlinearen Strukturen
• Erkundung einiger Graphen (geschweißte Bäume)
• Gruppenisomorphismus für abelsche und einige nicht-abelsche Gruppen
• Hier finden Sie einige Eigenschaften von endlichen Ringen und Idealen

Approximation und Simulation

• Quantensimulation. Offensichtlich vollständig$BQP$
• Berechnung einiger Knoteninvarianten, einschließlich des HOMFLY-Polynoms, von denen das Jones-Polynom ein Sonderfall ist. Einige von ihnen sind vollständig$BQP$
• Berechnung einiger dreifacher Invarianten. Einige von ihnen sind vollständig.$BQP$
• Abschätzung der thermodynamischen Verteilungsfunktion einiger klassischer Systeme
• Berechnen von Zeta-Funktionen über endliche Felder
• Ein Problem beim Umschreiben von Zeichenfolgen ist -complete$\mathit{PromiseBQP}$
• Approximation von Matrixelementen von Potenzen exponentiell großer, spärlicher Matrizen.

Algorithmus, den ich nicht wirklich verstehe.

Dies sind hauptsächlich Algorithmen, bei denen QAZ eine Superpolynomzunahme behauptet, aber ich verstehe nicht, warum das ursprüngliche Problem außerhalb von . Das heißt, ich wette viel Geld darauf, dass QAZ Recht hat und ich falsch liege .$P$

• Mustererkennung für ausreichend große ( ) Muster$>\log(n)$
• Einige lineare Systemprobleme, in , sondern eine mit p o l y l o g Quantenalgorithmus , wenn das lineare System als Oracle gegeben.$P$$\mathrm{polylog}$
• Berechnen der elektrische Widerstand eines Graphen, hat eine Quantenalgorithmus , wenn die elektrische Schaltung als Oracle gegeben ist$\mathrm{polylog}$
• Problem mit Gewichtsaufzählern. Etwas im Zusammenhang mit Code- und Partitionsfunktionen, aber ich verstehe nicht, worum es geht.

Probleme 1. erwies sich als in B Q P und dann in$P$$BQP$$P$

Hier sind einige Probleme, bei denen ein effizienter Quantenalgorithmus vor einem klassischen veröffentlicht wurde. Mit anderen Worten, es wurde einmal vermutet, dass sie sich in aber nicht in P , aber diese Vermutung ist jetzt ungültig.$BQP$$P$

• Befriedigend mehr als (aber weniger als($(\tfrac12-\tfrac{\text{constant}}{D})N$) Zwänge des Max E3LIN2 Problem. Juan Berego Vega hat in den Kommentaren darauf hingewiesen: Es gibt jetzt einen klassischen Algorithmus für($\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$, das durch das Quantenergebnis motiviert wurde. (BlogPost auf diesem Ergebnis,Papier 1,paper2)$(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$
• $m×n$$k$$m$$n$$k$$\mathrm{poly}(k)\mathrm{polylog}(mn)$Quantenalgorithmus zur Ermittlung von Stichproben der unbekannten Elemente der Matrix im Jahr 2016 ( Papier ). Während Ewin Tang 2018 zu beweisen versuchte, dass diese Skalierung mit einer klassischen Maschine nicht zu erreichen ist, fand er tatsächlich einen klassischen Algorithmus, der unter den gleichen Bedingungen die gleiche Leistung erbringt (Papier hier und hier erhältlich ).