Quelle est la complexité de distinguer un vrai spectre de Fourier d'un faux?

Une machine $PH$ accès oracle à une fonction booléenne aléatoire $f:\{0,1\}^n \to \{ -1,1 \}$ , et deux spectres de Fourier $g$ et $h$ .

Le spectre de Fourier d'une fonction $f$ est défini comme $F:\{0,1\}^n \to R$ :

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

L'un de ou est le véritable spectre de Fourier de et l'autre n'est qu'un faux spectre de Fourier appartenant à une fonction booléenne aléatoire inconnue.h $g$$h$$f$

Il n'est pas difficile de montrer qu'une machine ne peut même pas approcher pour n'importe quel .F ( s ) $PH$$F(s)$$s$

Quelle est la complexité de la requête pour décider avec une probabilité de réussite élevée laquelle est la vraie?

C'est intéressant pour moi, car si ce problème n'est pas en , alors on peut montrer qu'il existe un oracle par rapport auquel n'est pas un sous-ensemble de .B Q P P $PH$$BQP$$PH$

Désolé, je suis en retard - c'est une merveilleuse question! Comme d'autres l'ont déjà souligné, c'est exactement pourquoi j'ai posé la question dans mon article BQP vs. PH , et pourquoi j'ai passé 4 ou 5 mois à travailler dessus sans succès en 2008. Une façon de répondre à la question aurait été de prouver une déclaration beaucoup plus générale que j'ai appelée la "Conjecture généralisée Linial-Nisan" --- mais malheureusement, cette conjecture s'est avérée fausse , au moins pour les circuits de profondeur 3 et plus. (Je pense toujours que c'est probablement vrai pour les circuits de profondeur 2, ce qui entraînerait au moins une séparation d'oracle entre BQP et AM.) Pour des idées plus récentes (les dernières, pour autant que je sache) vers une séparation d'oracle entre BQP et PH, voir le joli papier de suivi de Fefferman, Shaltiel, Umans,

Scott Aaronson est peut-être la meilleure personne au monde pour répondre à cette question, il aura peut-être une meilleure réponse une fois celle-ci publiée. il a proposé le problème d'origine sur lequel cette question postée semble être une très légère variante, le problème dit de vérification de Fourier (plus de références à ce sujet dans les commentaires). le problème est étroitement lié / presque équivalent à la séparation de deux classes de complexité importantes PH et BQP qui est un problème ouvert clé de la théorie de la complexité QM, et il est vraisemblablement très difficile. il ne semble pas que beaucoup de recherches directes / approfondies sur le problème aient été faites jusqu'à présent par quelqu'un d'autre qu'Aaronson et peut-être même pas lui (il ne semble que remonter à un peu plus de 2 ans).

cependant, voici au moins un article d'une personne autre qu'Aaronson qui se concentre / s'appuie sur la conjecture / le problème avec de nouveaux résultats.

Les accélérations exponentielles sont génériques par Fernando GSL Brandão et Michał Horodecki

Dans notre article [4], nous généralisons le problème de vérification de Fourier [1] et montrons que la transformée de Fourier, à la fois dans la définition du problème et dans l'algorithme quantique le résolvant, peut être remplacée par une grande classe de circuits quantiques. Celles-ci incluent à la fois la transformée de Fourier sur tout groupe fini (éventuellement non abélien) et presque tout circuit quantique suffisamment long à partir d'une distribution naturelle sur l'ensemble des circuits quantiques. Nous obtenons des séparations exponentielles de la complexité des requêtes classiques quantiques et post-sélectionnées pour tous ces circuits.