The Complexity of Stoquastic Sparse Hamiltonians

Aquí se presenta un resumen técnico detallado del artículo "The complexity of Stoquastic Sparse Hamiltonians" de Alex B. Grilo y Marios Rozos.

Planteamiento del Problema

El artículo aborda la complejidad computacional del problema del Hamiltoniano Disperso Estocástico (StoqSH). Si bien la complejidad de los Hamiltonianos estocásticos locales está bien entendida (sabido que es StoqMA-completa), la complejidad de los Hamiltonianos estocásticos dispersos no había sido establecida directamente.

Los Hamiltonianos dispersos constituyen una clase más amplia que los Hamiltonianos locales; un Hamiltoniano $k$-local con $m$ términos es $2^{km}$-disperso. El problema StoqSH pregunta, dado un Hamiltoniano estocástico $d$-disperso $H$ (donde los elementos fuera de la diagonal son no positivos) y parámetros $\alpha, \beta$, si la energía del estado fundamental $\lambda_{\min}(H) \le \alpha$ o $\lambda_{\min}(H) \ge \beta$, con la promesa de que se cumple uno de los dos casos.

El desafío central es que las técnicas estándar para probar la contención en StoqMA para Hamiltonianos locales (que dependen de convertir términos locales en proyecciones específicas) no se extienden al entorno disperso. Además, los métodos estándar de verificación cuántica como la Estimación de Fase (utilizados para Hamiltonianos dispersos generales en QMA) son inherentemente cuánticos y no pueden ser simulados por los verificadores estocásticos restringidos, los cuales se limitan a circuitos reversibles clásicos y mediciones en la base de Hadamard.

Metodología

Los autores emplean un procedimiento de verificación que cierra la brecha entre la estructura del Hamiltoniano disperso y las limitaciones de los verificadores estocásticos. La metodología consta de tres componentes principales:

1. Descomposición Dispersa:
   Los autores utilizan una descomposición conocida (de [BCC+14]) donde cualquier Hamiltoniano $d$-disperso $H$ puede escribirse como una suma de $d^2$ términos 1-dispersos ($H = \sum H_j$). Crucialmente, si $H$ es estocástico, cada término $H_j$ en esta descomposición también es estocástico, y los elementos de matriz no nulos se asignan de manera única a términos específicos.

2. Verificadores StoqMA Generalizados (gStoqMA):
   Para manejar la verificación, los autores introducen una generalización del verificador StoqMA. Los verificadores StoqMA estándar miden un solo qubit en la base de Hadamard. Los autores definen gStoqMA, donde el verificador puede medir un número polinomial de qubits en las bases de Hadamard, $|0\rangle$ o $|1\rangle$.

   • Demuestran que esta generalización no aumenta el poder computacional de la clase; puede ser simulada por un verificador StoqMA estándar con una pérdida lineal en la brecha de completitud/salud (Teorema 1.2). Esto permite el uso de mediciones de múltiples qubits (específicamente pruebas de intercambio o Swap tests) dentro del marco estocástico.

3. Procedimiento de Verificación para StoqSH:
   La contribución central es un protocolo de verificación para StoqSH que acepta un estado testigo $|\psi\rangle$ con una probabilidad linealmente relacionada con la expectativa de energía $\langle \psi | H | \psi \rangle$. El verificador elige aleatoriamente entre dos sub-procedimientos ($V_1$ y $V_2$):

   • Procedimiento $V_1$: Utiliza el oráculo para los elementos de la matriz del Hamiltoniano para construir un estado dependiente de $|\psi\rangle$ y el término 1-disperso $H_j$. Realiza una prueba "tipo Hadamard" que implica una consulta de oráculo controlada y mediciones en las bases $X$ y $Z$. La probabilidad de aceptación se relaciona con los elementos fuera de la diagonal y la energía.
   • Procedimiento $V_2$: Un procedimiento complementario que mide el último qubit en la base $Z$.
   • Resultado Combinado: Al promediar las probabilidades de aceptación de $V_1$ y $V_2$, la probabilidad total de aceptación se convierte en $1/2 - \frac{1}{4d^2}\langle \psi | H | \psi \rangle$. Esta relación lineal permite al verificador distinguir entre instancias de baja energía (SÍ) y alta energía (NO).

Contribuciones y Resultados Clave

1. Completitud StoqMA de StoqSH
El resultado principal es el Teorema 1.1, que establece que el problema del Hamiltoniano Estocástico Disperso es StoqMA-completo.

• Dureza: Sigue inmediatamente porque los Hamiltonianos estocásticos locales son un caso especial de los Hamiltonianos estocásticos dispersos y ya se sabe que son StoqMA-difíciles.
• Contención: Establecida mediante el procedimiento de verificación descrito anteriormente, demostrando que StoqSH $\in$ StoqMA.

2. Hamiltonianos Estocásticos Dispersos Separables y StoqMA(2)
Los autores extienden su análisis al problema del Hamiltoniano Estocástico Disperso Separable (SepStoqSH), donde el testigo está restringido a ser un estado producto $|\psi\rangle = |\chi_A\rangle \otimes |\chi_B\rangle$.

• Definen StoqMA(k), el análogo estocástico de QMA(k), que involucra $k$ probadores no entrelazados.
• Teorema 1.4 (Simplificado): Muestran que, para ciertos parámetros de completitud y sonido, $k$ probadores pueden ser simulados por 2 probadores ($StoqMA(k) \subseteq StoqMA(2)$). La prueba adapta el protocolo de "Prueba de Producto" de [HM13] al entorno estocástico, aprovechando la capacidad de los verificadores estocásticos para realizar mediciones de múltiples qubits (mediante la generalización gStoqMA).
• Teorema 4.5: El problema SepStoqSH es StoqMA(2)-completo. La prueba de dureza adapta la construcción de circuito-a-Hamiltoniano para Hamiltonianos dispersos separables [CS12] al entorno estocástico, utilizando la teoría de perturbaciones para manejar la falta de amplificación de errores en StoqMA(2).

3. Generalización de StoqMA
El artículo introduce gStoqMA y demuestra que permitir mediciones de tamaño polinomial no aumenta el poder de la clase más allá de un cambio de parámetro (Teorema 3.5). Esta propiedad se destaca como potencialmente de interés independiente para el estudio de sistemas de prueba estocásticos.

Significado y Afirmaciones

El artículo afirma avanzar en la comprensión de la clase de complejidad StoqMA, que se sitúa entre las clases aleatorizadas MA y AM ($NP \subseteq MA \subseteq StoqMA \subseteq AM$).

• Completitud: Al identificar StoqSH como un problema completo para StoqMA, los autores proporcionan un problema natural más general para esta clase, yendo más allá de los modelos locales restringidos.
• Pruebas Separables: El trabajo sitúa a StoqMA(2) como un modelo intermedio interesante entre la verificación estocástica de un solo probador y la verificación cuántica general de múltiples probadores. Proporciona un problema completo natural (SepStoqSH) para StoqMA(2), análogo al papel de los Hamiltonianos dispersos separables para QMA(2).
• Robustez: Los resultados sugieren que el poder de los verificadores estocásticos es robusto incluso cuando el testigo está restringido a ser separable, siempre que el Hamiltoniano sea disperso.

Los autores señalan que, aunque muestran que StoqMA(k) colapsa a StoqMA(2) para parámetros específicos, la robustez de este colapso bajo límites de error más estrictos sigue siendo una pregunta abierta. Además, la complejidad del problema del Hamiltoniano Estocástico Local Separable permanece abierta, ya que las técnicas actuales para la consistencia de matrices de densidad locales no se aplican directamente al entorno estocástico.

En resumen, el artículo establece la dureza computacional de los Hamiltonianos estocásticos dispersos, introduce una nueva técnica de verificación que utiliza mediciones de múltiples qubits y caracteriza el poder de los sistemas de prueba estocásticos con múltiples probadores no entrelazados.