Qual é a complexidade de distinguir um verdadeiro espectro de Fourier de um falso?

Uma máquina $PH$ recebe acesso Oracle a uma função booleana aleatória $f:\{0,1\}^n \to \{ -1,1 \}$ e dois espectros de Fourier $g$ e $h$ .

O espectro de Fourier de uma função $f$ é definido como $F:\{0,1\}^n \to R$ :

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

Um de $g$ ou $h$ é o verdadeiro espectro de Fourier de $f$ eo outro é apenas um espectro falso de Fourier pertencente a uma função booleana aleatória desconhecida.

Não é difícil mostrar que uma máquina $PH$ nem consegue aproximar $F(s)$ para qualquer $s$ .

Qual é a complexidade da consulta de decidir com alta probabilidade de sucesso qual é o verdadeiro?

É interessante para mim, pois, se esse problema não está no $PH$ , pode-se mostrar que existe um oráculo em relação ao qual o $BQP$ não está em um subconjunto do $PH$ .

Desculpe o atraso - é uma pergunta maravilhosa! Como outros já apontaram, foi exatamente por isso que fiz a pergunta no meu artigo BQP vs. PH e por que passei 4 ou 5 meses trabalhando sem sucesso em 2008. Uma maneira de responder à pergunta seria provar uma afirmação muito mais geral que chamei de "Conjectura Linial-Nisana Generalizada" - mas, infelizmente, essa conjectura acabou sendo falsa , pelo menos para circuitos de profundidade 3 e superior. (Eu ainda acho que provavelmente é verdade para circuitos de profundidade 2, o que produziria pelo menos uma separação de oráculo entre BQP e AM.) Para idéias mais recentes (a mais recente, até onde eu sei) em relação a uma separação de oráculo entre BQP e PH, veja o belo artigo de acompanhamento de Fefferman, Shaltiel, Umans,

Scott Aaronson pode ser a melhor pessoa do mundo para responder a essa pergunta; talvez ele tenha uma resposta melhor depois que ela for publicada. ele propôs o problema original no qual essa pergunta postada parece ser uma variante muito pequena, o chamado problema de verificação de fourier (mais referências a isso nos comentários). o problema está intimamente relacionado / quase equivalente a separar duas importantes classes de complexidade PH e BQP, que é um problema-chave em aberto da teoria da complexidade da GQ, e presumivelmente é muito difícil. não parece que muita pesquisa direta / posterior tenha sido feita sobre o problema até agora por alguém que não seja Aaronson e talvez nem mesmo ele (aparentemente, tem apenas pouco mais de dois anos).

no entanto, aqui está pelo menos um artigo de alguém que não seja Aaronson que foca / constrói a conjectura / problema com alguns novos resultados.

As acelerações exponenciais são genéricas por Fernando GSL Brandão e Michał Horodecki

Em nosso artigo [4], generalizamos o problema da verificação de Fourier [1] e mostramos que a transformada de Fourier, tanto na definição do problema quanto no algoritmo quântico que o resolve, pode ser substituída por uma grande classe de circuitos quânticos. Isso inclui tanto a transformada de Fourier sobre qualquer grupo finito (possivelmente não abeliano) quanto quase qualquer circuito quântico suficientemente longo de uma distribuição natural no conjunto de circuitos quânticos. Obtemos separações exponenciais das complexidades de consulta clássica quântica e pós-selecionadas para todos esses circuitos.