Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP

Resumen Técnico: Aprendizaje de Estabilizadores Conjugados por T y el Problema del Subgrupo Oculto de Estados (StateHSP) en el Grupo Dihedral de Múltiples Cuadrados

1. Introducción y Definición del Problema

El artículo aborda una generalización del Problema del Subgrupo Oculto (HSP) conocido como StateHSP (State Hidden Subgroup Problem). Mientras que el HSP clásico busca identificar un subgrupo oculto $H$ de un grupo $G$ mediante una función clásica que oculta el subgrupo, el StateHSP recibe como entrada copias de un estado cuántico $|\Psi\rangle$ que posee una simetría bajo una representación unitaria $\rho$ de $G$.

• Definición del Problema: Dado un grupo finito $G$, una representación unitaria $\rho$, y copias de un estado $|\Psi\rangle$, se promete que:

  1. Para todo $h \in H$, $\rho(h)|\Psi\rangle = |\Psi\rangle$ (el estado es un autoestado con autovalor 1).
  2. Para todo $g \notin H$, $|\langle\Psi|\rho(g)|\Psi\rangle| < 1 - \epsilon$.
     El objetivo es identificar el subgrupo oculto $H$.

• El Caso Específico: Los autores se centran en el StateHSP no abeliano sobre el producto directo de $N$ copias del grupo diédrico de orden 8 ($D_4$, las simetrías de un cuadrado), denotado como $D_4^N$. El problema se denomina "Multiple-Squares StateHSP".

  • El subgrupo oculto $H$ es generado por una involutión $h$ (un elemento tal que $h^2 = e$).
  • La representación utilizada es la representación duplicada ($U_2^N$) en $2N$ cúbits, donde los elementos del grupo actúan como operadores que combinan Paulis y puertas $T$ (puertas no Clifford).

2. Motivación y Aplicaciones

El trabajo conecta el StateHSP con problemas físicos y de aprendizaje cuántico relevantes:

1. Aprendizaje de Estabilizadores No-Pauli: Extiende el aprendizaje de estabilizadores de Pauli (que es un StateHSP abeliano) a estabilizadores que incluyen puertas $T$. Esto es crucial para códigos de corrección de errores no-Pauli y modelos topológicos no abelianos.
2. Espectroscopía de Hamiltonianos: Identificar simetrías de un Hamiltoniano permite reducir la complejidad del problema y preparar estados sonda ideales. El problema de encontrar la simetría oculta de un Hamiltoniano se puede formular como un StateHSP.
3. Desafío No Abeliano: A diferencia de los grupos abelianos, donde el muestreo de Fourier resuelve el problema, los grupos no abelianos (especialmente $D_4^N$) tienen representaciones irreducibles de dimensión exponencial, lo que hace que el muestreo de Fourier directo falle. Este trabajo demuestra que, bajo ciertas representaciones, el problema sigue siendo tratable.

3. Metodología y Algoritmo Propuesto

El algoritmo propuesto es polinomial en el número de muestras y el tiempo computacional, y requiere circuitos de profundidad constante. La estrategia central consiste en transformar el problema no abeliano en uno abeliano mediante un proceso de "abelianización" controlada.

Pasos del Algoritmo:

1. Detección de Estabilizadores de Pauli: Primero, se verifica si el elemento oculto es un estabilizador de Pauli puro (sin puertas $T$). Si es así, se resuelve usando técnicas estándar de muestreo de Bell. Si no, se continúa.
2. Determinación de la Clase de Conjugación ($w_{max}$):
   • Se realiza un muestreo de paridad transversal sobre los pares de cúbits para obtener un conjunto de resultados de paridad $\pi$.
   • Se construyen conjuntos resolubles de Bell (Bell-resolvable sets): colecciones de estados proyectados que permiten realizar muestreo de Fourier sobre un grupo abeliano cuociente ($Z_2^N \times Z_2^N$).
   • Se ejecuta una subrutina de resolución de Bell que mide en la base de Bell y en la base $X$ para obtener etiquetas de representaciones irreducibles (caracteres).
   • A partir de estas etiquetas, se construye el subespacio aniquilador $K^\perp$.
   • Se utiliza una subrutina de rotación máxima para extraer un vector $w_{max}$ que codifica la información sobre dónde se han aplicado las puertas $T$ (la clase de conjugación de las reflexiones ocultas).
3. Corrección de T (Abelianización):
   • Utilizando $w_{max}$, se aplican puertas $T$ (o $T^\dagger$) conjugadas en los cúbits específicos indicados por el vector.
   • Esta operación transforma el estado original $|\Psi\rangle$ en un nuevo estado $|\Psi_T\rangle$ que es estabilizado por un elemento del subgrupo central de $D_4^N$, el cual es isomorfo a un grupo abeliano ($Z_2^N \times Z_2^N$).
   • Matemáticamente, esto convierte el estabilizador oculto $U(h)$ en un operador de Pauli puro.
4. Aprendizaje Final:
   • Una vez que el problema se ha reducido a un StateHSP abeliano (aprendizaje de estabilizadores de Pauli), se aplica el algoritmo estándar de muestreo de Fourier para identificar los parámetros restantes del subgrupo oculto ($t_h, v_h$).
   • Finalmente, se reconstruye el vector completo $h$ combinando la información obtenida.

4. Contribuciones Clave

• Algoritmo Polinomial para un Caso No Abeliano: Presentan el primer algoritmo eficiente (polinomial en muestras y tiempo) para un StateHSP no abeliano específico ($D_4^N$) con una representación física relevante (duplicada).
• Profundidad Constante: A diferencia de métodos anteriores que requerían control coherente complejo o profundidad logarítmica, este algoritmo solo requiere operaciones de dos cúbits y circuitos de profundidad constante, haciéndolo viable para dispositivos cuánticos actuales (NISQ).
• Reducción de Complejidad de Muestras: Mejoran la complejidad de muestras respecto a algoritmos previos para el HSP en grupos diédricos (de $O(N^3)$ a $O(N^2)$ en el caso regular).
• Generalización: Demuestran que el método se puede extender a representaciones arbitrarias de $D_4^N$ asumiendo la disponibilidad de una transformada de Fourier parcial eficiente.

5. Resultados Teóricos y Pruebas

• Teorema Principal: El algoritmo resuelve el Multiple-Squares StateHSP con probabilidad $> 1-\delta$ utilizando $O(\epsilon^{-2}(N^2 + \log(N/\delta)))$ copias del estado.
• Lemas de Espacios Nulos "Buenos": Demuestran que no es necesario encontrar el subespacio nulo único exacto. Basta con encontrar un "espacio nulo bueno" que contenga suficiente información para determinar la corrección de puertas $T$ necesaria.
• Concentración de Probabilidad: Utilizan propiedades de anti-concentración en las distribuciones de paridad para garantizar que se pueden obtener conjuntos resolubles de Bell con un número polinomial de muestras.

6. Significado e Impacto

Este trabajo es significativo por varias razones:

1. Puente entre HSP y Aprendizaje Cuántico: Establece un vínculo directo entre la teoría del HSP y problemas prácticos de aprendizaje de estados cuánticos y espectroscopía.
2. Viabilidad Experimental: Al requerir solo profundidad constante y operaciones locales, ofrece una ruta realista para demostrar ventajas cuánticas en problemas de simetría en hardware actual, superando las limitaciones de los algoritmos teóricos que requieren recursos masivos.
3. Nuevas Direcciones para HSP No Abeliano: Sugiere que, aunque el HSP general no abeliano es difícil, existen representaciones específicas (como las conjugadas por $T$) donde el StateHSP es tratable. Esto abre la puerta a estudiar la relación entre la estructura de las representaciones y la eficiencia de la solución del StateHSP.

En conclusión, el artículo proporciona una solución directa y eficiente para un problema de simetría cuántica no abeliana, demostrando que la combinación de muestreo de paridad, resolución de Bell y correcciones de puertas no-Clifford permite "abelianizar" problemas complejos y resolverlos con recursos cuánticos modestos.