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

26

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

Die Fourier-Spektren einer Funktion f sind definiert als F:{0,1}nR :

F(s)=x{0,1}n(1)(sxmod 2)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.ghf

Es ist nicht schwer zu zeigen, dass eine Maschine für keine annähern kann .PHF(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 .PHBQPPH

Mirmojtaba Gharibi
quelle
5
@Mirmojtaba: Obwohl ich das Problem und die Motivation kenne, wäre es schön, wenn Sie Ihre Frage bearbeiten und "Fourier-Spektren" definieren und die Motivation für Leser erläutern könnten, die mit diesem Problem nicht vertraut sind (oder nur die von Ihnen verwendete Terminologie). Auf diese Weise erhalten Sie möglicherweise mehr Antworten von Personen. Außerdem ist es normalerweise vorzuziehen, wenn Sie die Frage bearbeiten, um zusätzliche Kommentare hinzuzufügen, anstatt sie im Kommentarthread zu veröffentlichen. (Damit die Leser nur Ihre Frage und nicht die Kommentare lesen müssen.)
Robin Kothari
4
Vielleicht habe ich das Problem falsch verstanden, aber es scheint, dass dieses Problem zu schwer ist. Wenn g und h sehr nahe beieinander liegen (sagen wir, sie unterscheiden sich nur um 1 Bit), wie entscheidet eine BQP-Maschine, welches das richtige Fourierspektrum von f ist? Sollte die untere Schranke des Suchproblems nicht bedeuten, dass dies für Quantencomputer schwierig ist?
Robin Kothari
7
Ich habe eine grundlegendere Frage. Ist es bei einer beliebigen Funktion leicht zu erkennen, ob es sich tatsächlich um das Fourierspektrum einer Booleschen Funktion handelt?
Suresh Venkat
4
Abgesehen davon, da er zwei Tage vor dem Crossposting gewartet hat und auch, nachdem er hier keine Antwort erhalten hat, denke ich, dass es vollkommen in Ordnung ist, dies zu tun. Siehe auch die hier erreichte Resolution: meta.cstheory.stackexchange.com/questions/673/…
Suresh Venkat
2
Was ist ein PH-Gerät? In der Tat scheint dies irrelevant, wenn Sie nur an der Komplexität von Abfragen interessiert sind, oder? In diesem Fall scheint sich das Problem auf ein einfaches lineares Algebra-Problem zu beschränken, das wahrscheinlich eine exponentielle Abfragekomplexität ergibt.
Domotorp

Antworten:

10

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
quelle
1
ist die obige Aussage der Frage von Gharibi identisch oder leicht unterschiedlich? ist es eine relativierte Version von dir?
vzn
1
Es ist eine leichte Variante, aber ich glaube, es ist nicht schwer, das Äquivalent zu beweisen. Erstens, wenn Sie Fourier Checking lösen können, können Sie auch Gharibis Problem lösen (führen Sie einfach den FC-Algorithmus getrennt für g und h aus). Umgekehrt, wenn Sie Gharibis Problem lösen können, geben Sie bei gegebener Instanz von FC der zweiten FC-Funktion entweder "g" oder "h" einen einheitlichen zufälligen Namen und setzen Sie die andere der beiden (bzw. h oder g) auf eine zufällige Funktion. Wenn der Gharibi-Algorithmus immer die ursprüngliche Funktion aus der FC-Instanz auswählt, ist dies ein Beweis dafür, dass die Instanz nicht zufällig, sondern forrelated war.
Scott Aaronson
1
Ist mehr bekannt, wenn f in P ist?
Gil Kalai
Gil: Nicht wirklich! Sie erhalten dann ein nicht-relatives Versprechen-Problem in BQP, von dem wir nicht wissen, dass es in PH ist. Sicherlich könnten Sie den "zufälligen" Fall des Orakelproblems simulieren, indem Sie f und g durch Pseudozufallsfunktionen ersetzen (berechnet in einer Zeit, die ein größeres Polynom ist, als das PH-Gerät zur Verfügung hat). Der schwierige Teil ist, wie simuliert man den "for-related" Fall des Orakelproblems (wobei f nahe an der Fourier-Transformation von g liegt)? Dh, wie stellt man kleine Schaltkreise für solche f und g zur Verfügung, die nicht "das ganze Spiel verraten"? (Ein ähnliches Problem tritt bei Simons Problem auf.)
Scott Aaronson
1

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.

vzn
quelle
BQPPH