Una máquina tiene acceso oracle a una función booleana aleatoria y dos espectros de Fourier y .
El espectro de Fourier de una función se define como :
Uno de o es el verdadero espectro de Fourier de y el otro es solo un espectro falso de Fourier que pertenece a una función booleana aleatoria desconocida.h f
No es difícil demostrar que una máquina de , ni siquiera puede aproximar para ningún .F ( s ) s
¿Cuál es la complejidad de la consulta de decidir con alta probabilidad de éxito cuál es la verdadera?
Es interesante para mí, ya que si este problema no está en , entonces se puede demostrar que existe un oráculo en relación con el cual no es un subconjunto de .B Q P P H
cc.complexity-theory
lg.learning
boolean-functions
fourier-analysis
Mirmojtaba Gharibi
fuente
fuente
Respuestas:
Lo siento, llego tarde, ¡es una pregunta maravillosa! Como otros ya han señalado, esa es exactamente la razón por la que hice la pregunta en mi documento BQP vs. PH , y por qué pasé 4 o 5 meses trabajando en ello sin éxito en 2008. Una forma de responder a la pregunta habría sido probar una declaración mucho más general que llamé la "Conjetura generalizada de Linial-Nisan", pero desafortunadamente, esa conjetura resultó ser falsa , al menos para los circuitos de profundidad 3 y superiores. (Todavía creo que probablemente sea cierto para los circuitos de profundidad 2, que al menos producirían una separación de oráculo entre BQP y AM). Para ideas más recientes (la última, hasta donde yo sé) hacia una separación de oráculo entre BQP y PH, vea el bonito artículo de seguimiento de Fefferman, Shaltiel, Umans,
fuente
Scott Aaronson puede ser la mejor persona del mundo para responder esta pregunta, tal vez tendrá una mejor respuesta después de que se publique esta. propuso el problema original en el que esta pregunta publicada parece ser una variante muy leve, el llamado problema de verificación de Fourier (más referencias sobre eso en los comentarios). El problema está estrechamente relacionado / es casi equivalente a la separación de dos clases de complejidad importantes PH y BQP, que es un problema abierto clave de la teoría de la complejidad QM, y presumiblemente es muy difícil. no parece que se haya realizado mucha investigación directa / adicional sobre el problema hasta ahora por alguien que no sea Aaronson y tal vez ni siquiera él (aparentemente solo tiene poco más de 2 años).
sin embargo, aquí hay al menos un artículo de alguien que no sea Aaronson que se enfoca / desarrolla en la conjetura / problema con algunos resultados nuevos.
Las aceleraciones exponenciales son genéricas por Fernando GSL Brandão y Michał Horodecki
fuente