La complexité de l'échantillonnage (approximativement) de la transformée de Fourier d'une fonction booléenne

Une chose que les ordinateurs quantiques peuvent faire (peut-être même avec seulement des circuits quantiques BPP + log-depth) est d'échantillonner approximativement la transformée de Fourier d'une fonction booléenne évaluée en P.$\pm 1$

Ici et ci-dessous quand je parle d'échantillonner la transformée de Fourier, je veux dire choisir x selon . (Normalisé si nécessaire et approximativement).$|\hat f(x)|^2$

Peut-on décrire la classe de complexité, que l'on peut appeler P-FOURIER SAMPLING, des fonctions booléennes d'échantillonnage approximatif de P? Y a-t-il des problèmes qui sont complets pour cette classe?

Étant donné une classe X de fonctions booléennes, que peut-on dire de la complexité de calcul, que nous pouvons appeler SAMPLING-X pour approximer l'échantillonnage de la transformée de Fourier des fonctions dans X. (Je suppose que si X est BQP, alors X-SAMPLING est toujours au pouvoir des ordinateurs quantiques.)

Quels sont les exemples de X où SAMPLING-X est en P? Existe-t-il des exemples intéressants où SAMPLING-X est dur NP?

Il existe plusieurs variantes de ce problème qui peuvent également être intéressantes. Du côté de Fourier, plutôt que d'un échantillon approximatif, nous pouvons parler d'un problème de décision activé (de manière probabiliste) par échantillonnage approximatif. Du côté primal, nous pouvons commencer avec une classe X de distributions de probabilité et demander quelle est la relation entre la capacité d'échantillonner approximativement une distribution D dans X et d'échantillonner approximativement la transformée de Fourier (normalisée).

Bref, que sait-on de cette question.

Mise à jour: Martin Schwarz a souligné que si tous les coefficients de Fourier eux-mêmes sont concentrés uniquement sur un nombre d'entrées polynomiales, il est possible dans BPP d'approximer ces grands coefficients (et donc aussi approximativement d'échantillonnage). Cela remonte à Goldreich-Levin, et Kushilevitz-Mansour. Existe-t-il des classes de fonctions intéressantes où il existe un algorithme polynomial probabiliste pour échantillonner approximativement le côté de Fourier, où les coefficients de Fourier sont répartis sur plus de coefficients polynomialement nombreux?

Ajouté plus tard: Permettez-moi de mentionner quelques problèmes concrets.

1) Est-il difficile d'échantillonner approximativement la transformée de Fourier des fonctions booléennes dans P.

a) Une question que Scott Aaronson a mentionnée dans un commentaire ci-dessous est de montrer que ce n'est pas dans BPP. Ou quelque chose de plus faible dans le sens que si cette tâche est dans BPP, un effondrement se produit. (Scot suppose que c'est le cas.)

b) Une autre question est de montrer que cette tâche est difficile par rapport à une classe de complexité basée sur le quantum. Par exemple, pour montrer que si vous pouvez effectuer cette tâche, vous pouvez résoudre des problèmes de décision dans BPP assisté par des ordinateurs quantiques de profondeur de journal, ou quelque chose comme ça.

2) Quelles sont les classes de fonctions booléennes telles que l'échantillonnage approximatif de leur transformée de Fourler est en P. Ce que nous savons, c'est que c'est le cas lorsque les coefficients de Fourier sont concentrés sur de nombreux coefficients polynomiaux, mais cela semble très restreint.

3) Y a-t-il une classe de complexité X très haut dans le PH qu'une machine X peut approximativement échantillonner la transformée de Fourier de chaque fonction qu'une machine X peut calculer.

4) J'ai été particulièrement intéressé par le problème d'échantillonnage de la transformée de Fourier de l'événement de croisement pour percolation sur une grille hexagonale n par n.

$\hat{f}(x)$$O(poly(n))$$\Omega(1/poly(n))$$\sf{BPP}$$\mathbb{Z}_2$

$\Omega(2^{n/2})$