Resumen Técnico: El Problema del Hamiltoniano Local Conmutativo: Evidencia Relativizada Contra la Dureza de BQP

1. Planteamiento del Problema y Contexto

El problema del Hamiltoniano Local Conmutativo (CLH) pregunta si la energía del estado fundamental de un Hamiltoniano local, donde todos los términos locales conmutan entre sí, está por debajo de un umbral $\alpha$ o por encima de $\beta$. Si bien el problema general del Hamiltoniano Local es QMA-completo, la complejidad de la variante conmutativa sigue siendo una cuestión central abierta en la teoría de la complejidad cuántica.

Trabajos previos han demostrado que para familias específicas de Hamiltonianos conmutativos (por ejemplo, 2-locales, ciertos 3-locales, o aquellos en retículos específicos), el problema pertenece a NP. Sin embargo, no existía evidencia formal para descartar la posibilidad de que el problema CLH general sea QMA-completo.

La clase de complejidad QIMA (Merlin-Arthur Cuántico Interactivo con unidades conmutativas) fue introducida por Bostanci y Hwang para capturar el poder de los verificadores cuánticos cuyas unidades de prueba locales son reflexiones mutuamente conmutativas. El problema CLH es completo para QIMA. Por consiguiente, la cuestión de si CLH es QMA-completo es equivalente a preguntar si QIMA = QMA.

Este artículo investiga la relación entre QIMA y BQP (Tiempo Cuántico de Error Acotado en Polinomio) en un entorno relativizado. Específicamente, busca determinar si existe un oráculo clásico $O$ tal que BQP$^O \not\subseteq$ QIMA$^O$. Un resultado positivo proporcionaría evidencia relativizada contra la posibilidad de que el problema CLH general sea BQP-duro y, por ende, contra la posibilidad de que sea QMA-completo.

2. Metodología y Definiciones

2.1 El Modelo de Oráculo QIMA$^O$

Los autores definen un análogo relativizado de QIMA, denotado como QIMA$^O$, con restricciones específicas para asegurar que el modelo siga siendo una restricción no trivial de QMA$^O$:

• Estructura del Verificador: En la entrada $x$, el verificador realiza un preprocesamiento clásico (realizando consultas adaptativas a $O$) para generar un conjunto de "unidades" $W_1^O, \dots, W_m^O$ que actúan sobre un testigo cuántico.
• Conmutatividad: En las instancias prometidas, todas las unidades deben conmutar entre sí: $[W_i^O, W_j^O] = 0$.
• Requisito de Reflexión: Crucialmente, cualquier unidad $W_j^O$ que contenga al menos una consulta al oráculo debe ser una reflexión exacta (es decir, $(W_j^O)^\dagger = W_j^O$ y $(W_j^O)^2 = I$). Las unidades libres de oráculo pueden ser unitarias arbitrarias.
• Verificación: El verificador utiliza el test de Hadamard para comprobar si el testigo está en el espacio propio $+1$ de cada unidad.
• Sin Ancilla de Confianza: El verificador no posee un espacio de trabajo de confianza más allá de los cúbits de control frescos utilizados para los tests de Hadamard.

Los autores argumentan que el Requisito de Reflexión es esencial. Demuestran que relajar esto para permitir unidades conmutativas arbitrarias (incluso aquellas cercanas a las reflexiones) o permitir cúbits ancilla de confianza, colapsa la clase a QMA$^O$.

2.2 El Problema de Forrelation

La separación se basa en el problema de Forrelation, definido por Aaronson. Dado acceso a un oráculo a dos funciones booleanas $f, g: \{0,1\}^n \to \{-1, +1\}$, la tarea es distinguir entre:

• Sí: $f$ está altamente correlacionada con la transformada de Fourier de $g$ ($\Phi(f,g) \ge \alpha$).
• No: La correlación es pequeña ($|\Phi(f,g)| \le \beta$).

Forrelation es resoluble mediante un algoritmo BQP con un número constante de consultas cuánticas. El artículo pretende demostrar que cualquier verificador QIMA$^O$ para Forrelation requiere un número exponencial de consultas.

3. Contribuciones Clave y Resultados

3.1 Separación de Oráculo: BQP$^O \not\subseteq$ QIMA$^O$

El resultado principal es la construcción de un oráculo clásico $O$ tal que BQP$^O \not\subseteq$ QIMA$^O$. Esto se logra demostrando un límite inferior de consultas exponencial para el problema de Forrelation contra verificadores QIMA$^O$.

Teorema 1.7 (Informal): Cualquier verificador QIMA$^O$ que decida Forrelation para todos los pares prometidos $(f, g)$ debe satisfacer:
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
donde $C(n)$ es el número de consultas de preprocesamiento clásico y $T(n)$ es el número total de consultas al oráculo cuántico.

Esquema de la Prueba:

1. Método Polinomial: La probabilidad de aceptación del verificador se expresa como un polinomio en las entradas de la tabla de verdad del oráculo.
2. Conmutatividad y Reflexiones: Debido a que las unidades que contienen el oráculo son reflexiones exactas y conmutan, su operador de aceptación combinado es un producto de proyectores ortogonales. Esto permite a los autores definir un único proyector $P_f$ que representa la intersección de todos los subespacios de aceptación.
3. Límite de Grado: El grado del polinomio que representa la probabilidad de aceptación está acotado por el número total de consultas cuánticas $T(n)$.
4. Pares de Forrelation Perfectos: Los autores utilizan "pares de Forrelation perfectos" (funciones bent) donde $\Phi(g, h) = 1$. Muestran que perturbar $h$ por $k$ bits cambia el valor de Forrelation linealmente: $\Phi(g, f) = 1 - 2k/N$.
5. Simetrización: Al fijar la transcripción clásica y promediar sobre funciones con una distancia de Hamming fija de un par perfecto, construyen un polinomio univariante $q(k)$.
6. Conteo de Raíces: El polinomio $q(k)$ debe ser cero para todas las instancias "No" (un rango amplio de $k$) y no nulo para la instancia "Sí" ($k=0$). Un polinomio no nulo no puede tener más raíces que su grado, lo que obliga al grado (y por tanto al conteo de consultas) a ser exponencial.

3.2 Robustez de la Separación

El artículo demuestra que la separación se mantiene incluso bajo ligeras relajaciones del modelo:

• Desviaciones Despreciables: Si se permite que las unidades que contienen el oráculo sean despreciablemente cercanas (en norma de operador) a reflexiones exactas, la clase sigue siendo QIMA$^O$ y el límite inferior se mantiene.
• Soporte de Dirección Restringido: Los autores extienden el límite inferior a unidades que no son reflexiones pero realizan una sola consulta, siempre que los circuitos libres de oráculo que rodean la consulta actúen de forma no trivial solo en un pequeño número de cúbits de dirección ($k$). Si $n - k(n) = \omega(\log n)$, el límite inferior de consultas sigue siendo superpolinómico.

3.3 Ajuste del Modelo (Resultados de Colapso)

Para justificar las restricciones específicas de QIMA$^O$, los autores demuestran que relajar estas restricciones colapsa la clase a QMA$^O$:

• Desviaciones Inversamente Polinómicas: Si se permite que las unidades estén a una distancia inversamente polinómica de una reflexión (en lugar de despreciable), la clase colapsa a QMA$^O$. Esto se demuestra mediante una variación del gadget de amplificación de Marriott-Watrous, construyendo una única unidad que simula un verificador QMA.
• Consulta Única sin Reflexión: Si se elimina el requisito de reflexión pero se restringen las unidades a una sola consulta, la clase también colapsa a QMA$^O$. Esto utiliza una construcción de reloj cíclico (similar a Feynman-Kitaev) para codificar una simulación de múltiples consultas en una sola consulta.
• Ancilla de Confianza: Permitir al verificador un único cúbit ancilla de confianza (inicializado en $|0\rangle$) colapsa QIMA a QMA y QIMA$^O$ a QMA$^O$. Esto se basa en el problema del "Hamiltoniano Local Conmutativo con Posesión Fija" (Pinned Commuting Local Hamiltonian), que es QMA-completo.

4. Significado y Reivindicaciones

El artículo afirma proporcionar evidencia relativizada contra la posibilidad de que el problema CLH general sea BQP-duro. Dado que BQP está contenido en QMA, si CLH fuera BQP-duro, esto implicaría propiedades estructurales fuertes sobre QMA. La separación $BQP^O \not\subseteq QIMA^O$ sugiere que la restricción de conmutatividad en QIMA (y por extensión en CLH) es una restricción significativa que impide que la clase capture todo el poder de BQP, incluso en presencia de oráculos.

Además, el trabajo clarifica la precisión de la definición de QIMA. Los autores argumentan que la combinación específica de conmutatividad, el requisito de reflexión para las consultas al oráculo y la ausencia de ancillas de confianza es necesaria para definir una clase que sea estrictamente más débil que QMA. Relajar cualquiera de estas condiciones recupera inmediatamente todo el poder de QMA, sugiriendo que la "cuanticidad" de QIMA es frágil y depende precisamente de estas restricciones estructurales.

Los resultados no resuelven la cuestión no relativizada de si CLH es QMA-completo, pero establecen que cualquier prueba de tal completitud requeriría técnicas no relativizantes, ya que la afirmación falla respecto al oráculo construido.