¿Cuál es la complejidad de distinguir un verdadero espectro de Fourier de uno falso?

26

Una máquina PH tiene acceso oracle a una función booleana aleatoria f:{0,1}n{1,1} y dos espectros de Fourier g y h .

El espectro de Fourier de una función f se define como F:{0,1}nR :

F(s)=x{0,1}n(1)(sxmod 2)f(x)

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 fghf

No es difícil demostrar que una máquina de , ni siquiera puede aproximar para ningún .F ( s ) sPHF(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 HPHBQPPH

Mirmojtaba Gharibi
fuente
55
@Mirmojtaba: Si bien conozco el problema y la motivación, sería bueno que pudieras editar tu pregunta y definir "espectros de Fourier" y explicar la motivación para los lectores que no están familiarizados con este problema (o solo la terminología que has usado). Puede obtener más respuestas de la gente de esa manera. Además, generalmente se prefiere si edita la pregunta para agregar comentarios adicionales, en lugar de publicarlos en el hilo de comentarios. (Para que los lectores solo necesiten leer su pregunta y no los comentarios.)
Robin Kothari
44
Tal vez entendí mal el problema, pero parece que este problema es demasiado difícil. Si gyh están muy cerca (digamos que difieren en solo 1 bit), ¿cómo decide una máquina BQP cuál es el espectro de Fourier correcto de f? ¿No debería el límite inferior del problema de búsqueda implicar que esto es difícil para las computadoras cuánticas?
Robin Kothari
77
Tengo una pregunta más básica. Dada una función arbitraria, ¿es fácil saber si es realmente el espectro de Fourier de una función booleana?
Suresh Venkat
44
como comentario aparte, ya que esperó dos días antes de realizar la publicación cruzada, y eso también después de no recibir respuesta aquí, creo que está perfectamente bien hacerlo. Consulte también la resolución alcanzada aquí: meta.cstheory.stackexchange.com/questions/673/…
Suresh Venkat
2
¿Qué es una máquina de PH? De hecho, esto parece irrelevante si solo está interesado en la complejidad de la consulta, ¿verdad? En este caso, el problema parece reducirse a un simple problema de álgebra lineal, que probablemente da una complejidad de consulta exponencial.
domotorp

Respuestas:

10

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,

Scott Aaronson
fuente
1
¿Es la afirmación anterior de la pregunta de Gharibi idéntica o ligeramente diferente? ¿Es una versión relativizada tuya?
vzn
1
Es una ligera variante, pero creo que no es difícil demostrar el equivalente. Primero, ciertamente, si puede resolver la Comprobación de Fourier, también puede resolver el problema de Gharibi (solo ejecute el algoritmo FC por separado para g y h). Por el contrario, si puede resolver el problema de Gharibi, entonces, dada una instancia de FC, nombre la segunda función FC ya sea "g" o "h" de manera uniforme al azar, y configure la otra de las dos (respectivamente h o g) como Una función aleatoria. Si el algoritmo de Gharibi siempre elige la función original de la instancia de FC, eso es evidencia de que la instancia estaba relacionada en lugar de ser aleatoria.
Scott Aaronson el
1
¿Es más conocido cuando f está en P?
Gil Kalai el
Gil: En realidad no! Luego obtienes un problema de promesa no relativizada en BQP, que no sabemos que esté en PH. Ciertamente, podría simular el caso "aleatorio" del problema del oráculo reemplazando f y g por funciones pseudoaleatorias (calculadas a tiempo que es un polinomio más grande que el que tiene la máquina PH). La parte difícil es, ¿cómo simula el caso "relacionado" del problema del oráculo (donde f está cerca de la transformada de Fourier de g)? Es decir, ¿cómo se proporcionan pequeños circuitos para tales f y g que no "regalan todo el juego"? (Un problema similar ocurre con el problema de Simon.)
Scott Aaronson
1

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

En nuestro artículo [4] generalizamos el problema de la Comprobación de Fourier [1] y mostramos que la transformada de Fourier, tanto en la definición del problema como en el algoritmo cuántico que lo resuelve, puede ser reemplazado por una gran clase de circuitos cuánticos. Estos incluyen tanto la transformada de Fourier sobre cualquier grupo finito (posiblemente no abeliano) como casi cualquier circuito cuántico suficientemente largo a partir de una distribución natural en el conjunto de circuitos cuánticos. Obtenemos separaciones exponenciales de complejidades de consulta clásica cuántica y postseleccionada para todos estos circuitos.

vzn
fuente
Anexo: Aaronson formuló el problema de comprobación de Fourier específicamente como una ruta posible / plausible para resolver en la referencia [1] del documento Branda ~ o. BQPPH
vzn