Problemas NP-intermedios con soluciones cuánticas eficientes

27

Peter Shor mostró que dos de los problemas NP-intermedios más importantes, la factorización y el problema de registro discreto, están en BQP. Por el contrario, el algoritmo cuántico más conocido para SAT (búsqueda de Grover) solo produce una mejora cuadrática sobre el algoritmo clásico, lo que sugiere que los problemas de NP completo aún no se pueden resolver en las computadoras cuánticas. Como señalan Arora y Barak, también hay un problema en BQP que no se sabe que está en NP, lo que lleva a la conjetura de que las dos clases son incomparables.

¿Hay algún conocimiento / conjetura de por qué estos problemas intermedios NP están en BQP, pero por qué SAT (hasta donde sabemos) no lo está? ¿Otros problemas NP-intermedios siguen esta tendencia? En particular, ¿es el isomorfismo gráfico en BQP? (Este no google bien).

Huck Bennett
fuente
44
Supongo que debería abordar la pregunta de por qué ciertos problemas NP-intermedios están en BQP, y otros no son conocidos. Lo único que realmente puedo decir con confianza es que los problemas conocidos en BQP se dividen en varias clases, y dentro de cada clase, generalmente se utilizan las mismas técnicas en la solución. Vea los dos enlaces en mi comentario anterior
Peter Shor
1
Cualquier problema de BQP completo sirve como ejemplo de un problema en BQP que no se sabe que está en NP.
Robin Kothari
2
Con respecto a un algoritmo de isomorfismo de gráfico cuántico: tuvalu.santafe.edu/~moore/qip-slides.pdf .
Huck Bennett
1
BQP-complete? ¿Alguien puede citar un problema de BQP completo por favor?
Cem Say

Respuestas:

32

No se sabe que el isomorfismo gráfico esté en BQP. Se ha trabajado mucho para tratar de ponerlo. Una observación muy interesante es que el isomorfismo gráfico podría resolverse si las computadoras cuánticas pudieran resolver el problema del subgrupo oculto no abeliano para el grupo simétrico (la factorización y el registro discreto se resuelven mediante utilizando el problema del subgrupo oculto abeliano, que a su vez se resuelve aplicando la transformada cuántica de Fourier en grupos abelianos).

Una de las formas en que las personas intentaron resolver el isomorfismo gráfico fue aplicando la transformada cuántica de Fourier para grupos no abelianos. Existen algoritmos para la transformación cuántica de Fourier para muchos grupos no abelianos, incluido el grupo simétrico. Desafortunadamente, parece que puede no ser posible usar la transformada cuántica de Fourier para el grupo simétrico para resolver el isomorfismo gráfico; Se han escrito bastantes artículos sobre esto que muestran que no funciona, dados varios supuestos sobre la estructura del algoritmo. Estos documentos son probablemente lo que encuentras cuando buscas en Google.

Peter Shor
fuente
1
Supongo que los problemas que pregunté caen en la categoría 2 (QFT / HSP) en la pregunta de MathOverflow, y esa es la clave común. ¡Gracias!
Huck Bennett
10
Esta es una buena encuesta sobre todo lo que Peter dijo arxiv.org/abs/0812.0380
Marcos Villagra
Con el resultado del profesor Babai sobre isomorfismo gráfico, ¿qué hay de la complejidad del algoritmo informático Quantum en GI?
XL _At_Here_There
No tenemos ningún algoritmo cuántico que funcione mejor que los algoritmos clásicos en este momento.
Peter Shor
20

La respuesta del folklore es que la factorización está "estructurada" de una manera que los problemas generales de NP no lo son, y es por eso que solo hemos podido encontrar una ventaja cuántica para problemas intermedios.

Podría decirse que una versión más simple de su pregunta es analizar no la complejidad computacional, sino la complejidad de la consulta de las funciones booleanas. Aquí podemos decir algunas cosas de manera demostrable, como el hecho de que las aceleraciones superpolinomiales son posibles solo para funciones parciales (probadas en http://arxiv.org/abs/quant-ph/9802049 ) y no para funciones que son simétricas en sus entradas y resultados (probado en http://arxiv.org/abs/0911.0996 ).

Estos resultados no arrojan luz sobre la pregunta BQP vs NP, pero creo que son pasos significativos para determinar dónde hay una ventaja cuántica.

Aram Harrow
fuente