Wie komplex ist es, echte Fourier-Spektren von gefälschten Spektren zu unterscheiden?

A $PH$ Maschine Oracle Zugriff auf eine zufällige Boolesche Funktion gegeben $f:\{0,1\}^n \to \{ -1,1 \}$ , und zwei Fourier - Spektren $g$ und $h$ .

Die Fourier-Spektren einer Funktion $f$ sind definiert als $F:\{0,1\}^n \to R$ :

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

Eines von oder ist das wahre Fourierspektrum von und das andere ist nur ein falsches Fourierspektrum, das zu einer unbekannten zufälligen Booleschen Funktion gehört.$g$$h$$f$

Es ist nicht schwer zu zeigen, dass eine Maschine für keine annähern kann .$PH$$F(s)$$s$

Was ist die Komplexität der Abfrage, wenn mit hoher Erfolgswahrscheinlichkeit entschieden wird, welche die wahre ist?

Es ist interessant für mich, da, wenn dieses Problem nicht in , man zeigen kann, dass es ein Orakel gibt, in Bezug auf das in keiner Teilmenge von .$PH$$BQP$$PH$

Entschuldigung, ich bin spät dran - es ist eine wundervolle Frage! Wie andere bereits ausgeführt haben, habe ich die Frage in meinem BQP vs. PH-Artikel genau deshalb gestellt und 2008 vier oder fünf Monate lang erfolglos daran gearbeitet. Eine Möglichkeit zur Beantwortung der Frage wäre gewesen, dies zu beweisen eine viel allgemeinere Aussage, die ich die "Generalisierte Linial-Nisan-Vermutung" nannte - aber leider stellte sich diese Vermutung als falsch heraus , zumindest für Schaltkreise der Tiefe 3 und höher. (Ich denke immer noch, dass es wahrscheinlich für Schaltkreise der Tiefe 2 gilt, die zumindest eine Orakeltrennung zwischen BQP und AM ergeben würden.) Für neuere Ideen (die neuesten, soweit ich weiß) zu einer Orakeltrennung zwischen BQP und PH, siehe das nette Folgepapier von Fefferman, Shaltiel, Umans,

Scott Aaronson ist möglicherweise der beste Mensch auf der Welt, der diese Frage beantwortet. Vielleicht hat er eine bessere Antwort, nachdem diese Frage veröffentlicht wurde. Er schlug das ursprüngliche Problem vor, für das diese gestellte Frage eine sehr geringfügige Variante zu sein scheint, das sogenannte Fourier-Überprüfungsproblem (mehr dazu in den Kommentaren). Das Problem ist eng verwandt / fast gleichbedeutend mit der Trennung von zwei wichtigen Komplexitätsklassen PH und BQP, die ein offenes Schlüsselproblem der QM-Komplexitätstheorie darstellt, und es ist vermutlich sehr schwierig. es scheint nicht so, als ob eine Menge direkter / weiterer Forschungen zu diesem Problem bisher von jemand anderem als Aaronson und vielleicht nicht einmal von ihm durchgeführt wurden (es ist anscheinend erst etwas älter als 2 Jahre).

Hier ist jedoch mindestens ein Artikel von jemand anderem als Aaronson, der sich auf die Vermutung / das Problem mit einigen neuen Ergebnissen konzentriert / darauf aufbaut.

Exponential Speedups sind von Fernando GSL Brandão und Michał Horodecki generisch

In unserer Arbeit [4] verallgemeinern wir das Fourier-Checking-Problem [1] und zeigen, dass die Fourier-Transformation sowohl in der Definition des Problems als auch in dem sie lösenden Quantenalgorithmus durch eine große Klasse von Quantenschaltungen ersetzt werden kann. Dazu gehören sowohl die Fourier-Transformation über eine beliebige (möglicherweise nicht abelsche) endliche Gruppe als auch nahezu jede ausreichend lange Quantenschaltung aus einer natürlichen Verteilung auf der Menge von Quantenschaltungen. Für alle diese Schaltungen erhalten wir exponentielle Trennungen von quantalen und postselektierten klassischen Abfragekomplexitäten.