Agnostic learning of qudit stabilizer states

Resumen Técnico: Aprendizaje Agnóstico de Estados Estabilizadores de Qudits

Planteamiento del Problema
El artículo aborda la tarea fundamental de aprender eficientemente una descripción clásica de un estado cuántico desconocido. Si bien el aprendizaje de estados arbitrarios sufre de la maldición de la dimensionalidad, el aprendizaje de estados estructurados (como los estados estabilizadores) es más tratable. Sin embargo, los algoritmos existentes para estados estabilizadores suelen operar en el entorno "realizable", asumiendo que el estado desconocido coincide exactamente con un estado estabilizador. En escenarios realistas, el ruido aleja al estado objetivo de esta estructura ideal. Esto motiva el problema del aprendizaje agnóstico: dado un conjunto de copias de un estado desconocido $|\psi\rangle$ que tiene una fidelidad $\tau$ con algún estado estabilizador desconocido, el objetivo es producir un estado estabilizador $|\phi\rangle$ tal que $F(|\psi\rangle, |\phi\rangle) \ge \max_{|\phi'\rangle \in \mathcal{C}} F(|\psi\rangle, |\phi'\rangle) - \varepsilon$, donde $\mathcal{C}$ es la clase de los estados estabilizadores.

Aunque Chen et al. [STOC '25] resolvieron recientemente esto para sistemas de qubits ($d=2$), el problema para sistemas de qudits (donde la dimensión local $d > 2$ es un número primo impar) permanecía en gran medida inexplorado. La generalización directa de las técnicas de qubits falla debido a diferencias estructurales fundamentales, particularmente respecto al comportamiento de los operadores de Weyl y la distribución de los resultados de las mediciones.

Metodología y Técnicas Clave
Los autores generalizan el marco de trabajo de stabilizer bootstrapping a sistemas de qudits superando tres desafíos técnicos primarios:

1. Fallo del Muestreo de Diferencia de Bell Estándar: En sistemas de qubits, el muestreo de diferencia de Bell produce muestras de la distribución de Weyl $q_\psi$. En sistemas de qudits, una generalización directa produce una distribución distorsionada que no logra concentrarse en el grupo estabilizador. Los autores emplean un muestreo de diferencia de Bell sesgado (skewed Bell difference sampling, introducido por Allcock et al. [23] para el entorno realizable). Este protocolo utiliza una unitaria entrelazante construida mediante residuos cuadráticos módulo $d$ para procesar cuatro copias del estado. Para manejar la complejidad de la distribución conjunta en el entorno agnóstico, los autores analizan la distribución marginal $B_\psi$ de una única cadena de salida.

2. Anti-concentración de la Distribución Marginal: Un requisito crucial para el bootstrapping es que la distribución de muestreo coloque masa suficiente en los elementos del grupo estabilizador fuera del subgrupo actualmente conocido (anti-concentración). Los autores demuestran que, para cualquier subespacio propio $T$ del grupo estabilizador objetivo $S$, la distribución marginal satisface $\sum_{x \in S \setminus T} B_\psi(x) \ge \Omega(\tau^6)$.

   • Idea Clave: La demostración evita una optimización multivariante compleja requerida para $d$ general al reducir el problema a un caso de un solo qudit. Establecen un límite inferior en la fidelidad del estabizador de cualquier estado de un solo qudit ($2/(d+1)$) aprovechando el hecho de que los estados estabilizadores de un solo qudit forman un 2-diseño proyectivo complejo y constituyen $d+1$ bases mutuamente no sesgadas.

3. No Hermiticidad de los Operadores de Weyl: En el entorno de qubits, los operadores de Weyl son hermíticos, lo que permite la estimación por lotes eficiente de correlaciones mediante la estimación de la media de Bernoulli. Para qudits ($d>2$), los operadores de Weyl son generalmente no hermíticos, lo que hace que $\langle \psi | W_x | \psi \rangle$ sea complejo. Los autores abordan esto estimando las correlaciones al cuadrado $|\langle \psi | W_x | \psi \rangle|^2$ de forma individual utilizando el test SWAP, en lugar de depender de observables hermíticos.

Marco Algorítmico
El algoritmo propuesto sigue un procedimiento iterativo de stabilizer bootstrapping:

1. Muestreo: Realizar un muestreo de diferencia de Bell sesgado para obtener cadenas de Pauli de la distribución marginal $B_\psi$.
2. Filtrado: Estimar la correlación al cuadrado de las cadenas muestreadas con el estado de trabajo actual. Retener las cadenas de "alta correlación" (aquellas con una correlación $> 1 - 1/(12d^2)$).
3. Construcción de la Base: Formar una base a partir de las cadenas de alta correlación que conmutan. Si la base está incompleta (no genera el grupo estabilizador completo), la propiedad de anti-concentración asegura que, con una probabilidad $\Omega(\tau^6)$, se muestree un nuevo elemento estabilizador fuera del espacio actual.
4. Bootstrapping: Si se encuentra un elemento estabilizador de baja correlación, medir el estado en su base propia y realizar post-selección. Esto amplifica la fidelidad con el estado estabilizador objetivo por un factor constante.
5. Iteración: Repetir el proceso con el estado amplificado hasta identificar el grupo estabilizador completo.

Además, para el régimen de alta fidelidad ($\tau > \cos^2(\pi/8)$), los autores presentan un algoritmo simplificado. Demuestran que en este régimen, las correlaciones al cuadrado de los operadores de Weyl dentro del grupo estabilizador están estrictamente separadas de las que están fuera. Esto permite un enfoque directo basado en umbrales que evita la maquinaria iterativa de bootstrapping, produciendo una complejidad polinómica.

Resultados y Complejidad
El artículo presenta el primer algoritmo cuántico eficiente para el aprendizaje agnóstico de estados estabilizadores de qudits puros ($d > 2$ primo).

• Régimen General: Dado un estado de $n$-qudits desconocido con fidelidad de estabilizador $\tau$, el algoritmo produce un estado estabilizador con una fidelidad de al menos $\tau - \varepsilon$ con alta probabilidad.

  • Complejidad de Muestreo: $O(n \log n) \cdot (d/\tau)^{O(d^2 \log(1/\tau))} + O(d/\varepsilon^2 \log^2(1/\tau))$.
  • Complejidad Temporal: $O(n^3/\varepsilon^2) \cdot (d/\tau)^{O(d^2 \log(1/\tau))}$.
  • La complejidad es cuasi-polinómica cuando $\tau = 1/\text{poly}(n)$, igualando los mejores resultados conocidos para qubits.

• Régimen de Alta Fidelidad ($\tau > \cos^2(\pi/8) + \gamma$):

  • Complejidad de Muestreo: $O(d^4 n \log n / \gamma^2)$.
  • Complejidad Temporal: $O(n^3 + n^2 d^4 \log n / \gamma^2)$.
  • Este régimen admite una solución de tiempo polinómico.

• Corolarios:

  • Estimación de la Magia: El algoritmo permite la estimación eficiente de la "magia" de un estado cuántico (cuantificada como la fidelidad del estabilizador) con un error aditivo $\varepsilon$.
  • Decodificación de Lista: El método puede extenderse para producir una lista de todos los estados estabilizadores con fidelidad $\ge \tau$.

Significancia y Reivindicaciones
Los autores afirman que este trabajo completa el panorama del aprendizaje agnóstico para estados estabilizadores al extender los resultados de qubits a qudits. La significancia radica en:

1. Cerrar la Brecha: Proporcionar la primera solución eficiente para el aprendizaje agnóstico en el entorno de qudits, que anteriormente estaba abierto debido a obstrucciones estructurales en la generalización del muestreo de diferencia de Bell.
2. Robustez: El algoritmo está diseñado para manejar el ruido (entorno agnóstico), lo que lo hace aplicable a sistemas cuánticos realistas donde los estados no son estabilizadores perfectos.
3. Herramientas Fundacionales: El artículo establece nuevos límites de anti-concentración para el muestreo de diferencia de Bell sesgado y demuestra límites inferiores en la fidelidad del estabilizador de un solo qudit usando propiedades de 2-diseño, lo cual puede tener utilidad independiente.
4. Cuantificación de la Magia: Al permitir la estimación eficiente de la magia cuántica, el trabajo proporciona una herramienta práctica para cuantificar la magia cuántica, un recurso clave para la ventaja cuántica.

Los autores señalan que sus resultados están actualmente restringidos a dimensiones de primos impares y que extenderlos a dimensiones compuestas o estados mixtos sigue siendo un desafío abierto. También destacan que la dependencia cuasi-polinómica de $1/\tau$ es una limitación compartida con los algoritmos de qubits, y mejorar esto a tiempo polinómico manteniendo una dependencia polinómica en $n$ y $1/\varepsilon$ es un problema abierto importante.