PCP cuántica y dureza de simulación de hamiltonianos

8

Tengo algunas preguntas sobre la conjetura de Quantum PCP:

  1. ¿Cuál es la declaración de la conjetura de PCP cuántica?

  2. ¿Qué implicaciones tendría el teorema de PCP Quantum para la simulación de hamiltonianos?

  3. ¿Se cree que la adopción de la prueba de Irit Dinur del teorema clásico de PCP puede conducir a una prueba de la conjetura de Quantum PCP?

  4. ¿Qué antecedentes se necesitan para leer artículos sobre el problema?

La copia de la pregunta sobre MO

cc.complexity-theory quantum-computing approximation-hardness pcp physics Comunidad
fuente
1
Pregunta relacionada: ¿cuáles son buenas referencias para comprender la prueba del teorema de PCP?
Kaveh
12
No existe un teorema de PCP cuántico. La gente está tratando de demostrarlo, pero si existe tal teorema (y tal vez exactamente qué forma tomaría) es una de las grandes preguntas abiertas en la computación cuántica.
Peter Shor el
77
Noah Rahman: Por favor, enlácese a la pregunta original cuando realice una publicación cruzada. De lo contrario, no todos se darían cuenta de que ya recibió una muy buena respuesta de Peter Shor. mathoverflow.net/questions/45106/quantum-pcp-theorem
Tsuyoshi Ito el
3
Desearía saber cuál es el mejor enfoque para probar o refutar un teorema de PCP cuántico. El problema es que si lo supiera, ya lo habría probado o refutado.
Tsuyoshi Ito
2
Lo siento, cerraré la pregunta. Alguien me dijo que lo publicara aquí. pero para responder a la pregunta de Robin, mi investigación tiene que ver con la aplicabilidad de estos llamados algoritmos DMRG, y así es como me encontré con la conjetura de QPCP (habiendo presentado a una clase de seminario anteriormente sobre los diversos problemas de QMA-completa de Kitaev)

Respuestas:

8

Como dijo Shor, no existe un teorema de QPCP (¡todavía!). Una conjetura (llamémosla conjetura QPCP) es esta: considere una gráfica de N vértices, de grado O (1). Asocia un qudit con cada vértice, con la dimensión espacial O de Hilbert (1). Deje que el hamiltoniano sea una suma de términos para cada borde, cada uno de esos términos actúa solo sobre los qudits en los vértices, con la norma del operador de cada uno de esos términos delimitada por O (1), de modo que la norma del operador del hamiltoniano es O (N ) Entonces, la conjetura es que hay algo de épsilon> 0, de modo que es difícil QMA aproximar la energía del estado fundamental del problema a una precisión épsilon N.

Una conjetura ligeramente más fuerte es considerar el caso en el que cada uno de esos términos que actúan sobre un borde es un proyector para que la energía del estado fundamental no sea negativa, y la conjetura es que es difícil determinar si la energía del estado fundamental es 0 dada la promesa de que si no es cero, entonces es al menos épsilon N.

También hay otras versiones de la conjetura, pero esas son dos interesantes con la relación más natural con la física. Una conjetura aún más fuerte (por lo tanto, probablemente una más fácil de refutar si cree que estas conjeturas son falsas) es considerar el caso en el que el hamiltoniano es una suma de proyectores de conmutación.

hastings mate
fuente
66
El teorema clásico de PCP dice que todas estas preguntas son al menos NP-difíciles.
Peter Shor
6

Básicamente, todo lo que se sabe sobre la conjetura de Quantum PCP ha sido recopilado en esta encuesta por Dorit Aharonov, Itai Arad y Thomas Vidick:

La conjetura de PCP cuántica

Vea también la publicación del blog de Thomas sobre el tema.

Alessandro Cosentino
fuente