Circuit complexity lower bounds for quantum spin glasses

Resumen Técnico: Cotas Inferiores de Complejidad de Circuitos para el Vidrio de Espín Cuántico

Planteamiento del Problema
Este artículo investiga la complejidad de circuito de la preparación de estados cercanos al estado fundamental para vidrios de espín cuánticos $p$-spin. Estos son Hamiltonianos aleatorios donde los términos de interacción actúan sobre $p$-tuplas de qubits mediante cadenas de Pauli. Una cuestión central en la teoría de la información cuántica es si familias de estados físicamente naturales, como los estados fundamentales de Hamiltonianos descritos de forma sucinta, requieren una alta complejidad de circuito (específicamente, una alta profundidad) para ser preparados.

Trabajos recientes establecieron que el óptimo de energía para los vidrios de espín cuánticos $p$-spin está estrictamente separado del mejor valor de energía alcanzable por estados no entrelazados (estados producto). Sin embargo, permanecía sin resolver si los circuitos poco profundos (por ejemplo, de profundidad constante o logarítmica) podrían generar la entrelazación suficiente para cerrar esta "brecha de estado producto". Este artículo aborda si tales circuitos poco profundos pueden preparar estados con una energía cercana al óptimo del estado fundamental.

Metodología
Los autores emplean un enfoque probabilístico, reformulando las cotas inferiores de preparación de estados como el control uniforme de procesos gaussianos indexados por circuitos cuánticos poco profundos. La estrategia técnica central consiste en descomponer la energía de un estado preparado por un circuito en dos componentes:

1. Un Término de Tipo Producto ($X_0$): Determinado únicamente por los marginales de un solo qubit del estado. Este término está acotado superiormente por el óptimo del estado producto, independientemente de la profundidad del circuito.
2. Un Término Residual ($R$): Captura las correlaciones de $p$-puntos no producto y entrelazadas.

Los autores argumentan que, para circuitos poco profundos, el término residual es asintóticamente despreciable en comparación con la escala de energía del estado fundamental. La demostración se basa en tres pilares técnicos principales:

• Soportes hacia Atrás y Grafos de Dependencia: Los autores definen el "soporte hacia atrás" (backward support) de un qubit de salida como el conjunto de qubits de entrada que pueden influir en él al rastrear el circuito hacia atrás. Construyen un grafo de dependencia donde los vértices son qubits y existen aristas si sus soportes hacia atrás se traslapan. Una observación clave es que, si los qubits involucrados en una interacción $p$-spin forman un conjunto independiente en este grafo de dependencia, la esperanza matemática de $p$-puntos se factoriza, causando que el coeficiente residual se anule.
• Reducción de Varianza: Debido a la localidad de los circuitos poco profundos, la varianza del proceso residual es significativamente menor que la de la energía bruta. Específicamente, mientras que la energía normalizada bruta tiene una varianza de orden $1/n$, el residual normalizado tiene una varianza de orden $2^D/n^2$ (donde $D$ es la profundidad del circuito).
• Entropía y Límites de Cobertura: Para controlar el supremo del proceso residual sobre todos los circuitos posibles, los autores derivan límites de entropía uniforme para la clase de circuitos de profundidad $D$. Crucialmente, manejan la presencia de un número arbitrario de qubits ancilla ($r$) mediante la "poda" (pruning) del circuito hacia el soporte hacia atrás conjunto de los qubits de salida físicos y el reetiquetado de los ancillas activos en un bloque canónico. Esto asegura que los números de cobertura sean independientes de $r$.

Estos límites se aplican a través de tres regímenes del Hamiltoniano aleatorio:

1. Campo Medio (Mean-Field): Todas las posibles $p$-tuplas están presentes.
2. Grado Promedio Creciente Diluido: Un hipergrafo disperso donde el grado promedio crece con $n$.
3. Grado Promedio Acotado Diluido: Un hipergrafo disperso donde el grado promedio es acotado (número lineal de términos).

Contribuciones Clave y Resultados
El artículo establece cotas inferiores de profundidad de circuito para la preparación de estados cercanos al estado fundamental en los tres regímenes, de manera uniforme respecto al número de qubits ancilla:

1. Cota Inferior de Profundidad Logarítmica (Campo Medio y Grado Promedio Creciente):
   Para un $p$ fijo suficientemente grande, cualquier circuito que prepare un estado de $n$ qubits con energía normalizada dentro de una constante positiva fija del óptimo debe tener una profundidad de al menos $\Omega_p(\log n)$. Esto se mantiene incluso si el circuito utiliza un número arbitrario de ancillas. La demostración muestra que para profundidades $D \leq \delta \log n$, la energía residual es demasiado pequeña para cerrar la brecha entre la energía del estado producto y la energía del estado fundamental.

2. Obstrucción de Profundidad Fija (Grado Promedio Acotado):
   En el régimen donde el grado promedio es acotado (número lineal de términos), el artículo demuestra una obstrucción de profundidad fija. Para cada profundidad $D$ fija, existe un factor de grado $\zeta$ suficientemente grande tal que ningún circuito de profundidad $D$ (incluso con ancillas arbitrarias) puede preparar un estado cercano al estado fundamental con alta probabilidad. La probabilidad de éxito tiende a cero en el límite iterado $n \to \infty$ seguido de $\zeta \to \infty$.

3. Uniformidad sobre las Ancillas:
   Una contribución técnica significativa es la demostración de que estas cotas inferiores se mantienen uniformemente para cualquier número de qubits ancilla. Los argumentos de conteo previos a menudo fallaban al no proporcionar cotas de profundidad significativas cuando el número de ancillas era grande en relación con el tamaño del sistema; la técnica de poda y reetiquetado supera esta limitación.

Significado y Conexión con NLTS
Los autores posicionan sus resultados como una ruta probabilística hacia el problema de No Low-Energy Trivial States (NLTS).

• Contraste con NLTS Basado en Códigos: Avances previos (por ejemplo, Anshu, Breuckmann y Nirkhe [6]) demostraron NLTS para Hamiltonianos construidos a partir de códigos cuánticos LDPC. Estas construcciones dependen de términos locales conmutativos, espacios fundamentales libres de frustración y estructuras específicas de la teoría de códigos (propiedades isoperimétricas).
• Entorno Aleatorio y No Conmutativo: En contraste, los Hamiltonianos estudiados aquí son aleatorios, generalmente no conmutativos y carecen de un procedimiento de preparación eficiente conocido. La obstrucción surge de la interacción entre el desorden del vidrio de espín y los conos de luz limitados de los circuitos poco profundos, en lugar de la geometría del código.
• Implicaciones: Los resultados proporcionan una obstrucción de tipo NLTS completa (en lugar de meramente combinatoria) para los Hamiltonianos de vidrios de espín cuánticos en los regímenes de campo medio y de grado promedio creciente. En el régimen de grado promedio acotado, proporcionan una obstrucción de profundidad fija que se aproxima a la propiedad completa de NLTS a medida que el factor de grado aumenta.

El artículo concluye con la conjetura de que los estados cercanos al estado fundamental de los vidrios de espín cuánticos $p$-spin no pueden ser preparados por circuitos de tamaño polinomial, incluso con ancillas arbitrarias, aunque demostrar esto requeriría técnicas más allá del alcance actual, potencialmente relacionadas con la separación de BQP y QMA.