Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform

Resumen Técnico: Algoritmo HHL en el Peor Caso con QFT Correcta en Promedio

1. Planteamiento del Problema

La verificación de la corrección de los ordenadores cuánticos es un desafío crítico debido a la naturaleza probabilística de los sistemas cuánticos. En particular, la Transformada Cuántica de Fourier (QFT) es un componente fundamental en algoritmos clave como el de Shor y la estimación de fase.

El trabajo anterior de Linden y de Wolf (2022) demostró que es posible verificar el comportamiento de la QFT en el caso promedio (average-case) de manera eficiente y ligera, y que una buena performance en promedio es suficiente para garantizar una buena performance en el peor caso (worst-case) para tareas como la estimación de fase y la búsqueda de periodos.

Sin embargo, existe una limitación crucial al aplicar este resultado directamente al Algoritmo de Harrow-Hassidim-Lloyd (HHL) para resolver sistemas de ecuaciones lineales:

• El algoritmo HHL no solo necesita estimar autovalores (como en la estimación de fase estándar), sino que debe producir un estado cuántico final que dependa de los autovalores y autovectores de la matriz de entrada.
• Una QFT que es "correcta en promedio" según la definición original de Linden-de Wolf podría introducir fases locales incontrolables en el estado final. Si la QFT es $C = D F_N^{-1}$ (donde $D$ es una matriz diagonal unitaria desconocida), el estado resultante podría tener fases aleatorias ($e^{i\theta_k}$) que hacen que el estado final sea ortogonal o muy diferente del estado deseado, fallando en la tarea de HHL.

El problema central: ¿Cómo fortalecer el protocolo de verificación de promedio para garantizar que el algoritmo HHL funcione correctamente en el peor caso, incluso si la QFT solo es correcta en promedio?

2. Metodología

El autor propone un enfoque basado en el fortalecimiento del protocolo de verificación de Linden-de Wolf y el análisis de canales cuánticos bajo nuevas condiciones de fidelidad promedio.

A. Definición de Conjuntos de Canales Cuánticos:
Se definen tres conjuntos de canales cuánticos ($C$) que aproximan la inversa de la QFT ($F_N^{-1}$):

1. $S_1(\eta)$: Canales que son cercanos a $F_N^{-1}$ en la base de Fourier (definición original de Linden-de Wolf).
   $$\mathbb{E}_k [F(C(|\hat{k}\rangle\langle\hat{k}|), |k\rangle\langle k|)] \geq 1 - \eta$$
2. $S_2(\eta)$: Canales que son cercanos a $F_N^{-1}$ en la base computacional (equivalente a estar cerca de $F_N$ en la base de Fourier).
   $$\mathbb{E}_k [F(C(|k\rangle\langle k|), |-\hat{k}\rangle\langle-\hat{k}|)] \geq 1 - \eta$$
3. $S_3(\eta)$ (La contribución clave): Canales que son cercanos a $F_N^{-1}$ en términos de coherencia entre bases.
   $$\mathbb{E}_{k,l} [\langle k| C(|\hat{k}\rangle\langle\hat{l}|) |l\rangle] \geq 1 - \eta$$

B. Protocolos de Verificación Ligeros (TA1 y TA2):
El autor demuestra que verificar si un canal pertenece a $S_3(\eta)$ no requiere un costo exponencial. Basta con verificar si el canal pertenece a la intersección $S_1(\eta) \cap S_2(\eta)$ mediante dos algoritmos de prueba ligeros:

• TA1: Verifica la fidelidad en la base de Fourier (protocolo original).
• TA2: Verifica la fidelidad en la base computacional.
• Teorema 4: Si un canal pasa ambos tests (está en $S_1 \cap S_2$), entonces pertenece a $S_3$ (con un error sumado). Esto implica que el canal introduce principalmente una fase global y no fases locales descontroladas, lo cual es suficiente para HHL.

C. Aplicación al Algoritmo HHL:
Se analiza la ejecución del algoritmo HHL reemplazando $F_N^{-1}$ por un canal $C \in S_3(\eta_1)$ y $F_N$ por un canal $P \in T_3(\eta_2)$ (definido análogamente para la QFT directa).

• Se introduce una variable aleatoria $l$ (ruido en los autovalores) para promediar sobre el espacio de entrada, similar a la técnica de Linden-de Wolf.
• Se demuestra que, bajo estas condiciones, el estado final $\rho_{7,l}$ tiene una alta fidelidad promedio con el estado ideal $|\phi_{7,l}\rangle$.

3. Contribuciones Clave

1. Fortalecimiento del Protocolo de Verificación: Se extiende el trabajo de Linden-de Wolf para incluir la verificación de la coherencia de fase (condición $S_3$), resolviendo el problema de las fases locales incontrolables en el algoritmo HHL.
2. Reducción Peor Caso/Promedio para HHL: Se demuestra que el algoritmo HHL puede ejecutarse con garantías de rendimiento en el peor caso, asumiendo únicamente que la QFT es correcta en promedio bajo el nuevo protocolo de verificación.
3. Protocolos de Verificación Eficientes: Se proponen algoritmos de prueba (TA1 y TA2) que requieren un número de ejecuciones polinomial ($O(\eta^{-2} \log(1/\delta))$) para verificar la condición necesaria.
4. Análisis de Canales Unitarios y No Unitarios: Se proporcionan resultados tanto para canales cuánticos generales (Kraus) como para canales unitarios, ofreciendo cotas de error más estrictas en el caso unitario.

4. Resultados Principales

• Teorema 10 (Caso Ideal): Si los autovalores de la matriz $A$ están representados exactamente por $n$ bits, y se utilizan canales $C \in S_3(\eta_1)$ y $P \in T_3(\eta_2)$, la fidelidad promedio del estado final cumple:
  $$\mathbb{E}_l [F(\rho_{7,l}, |\phi_{7,l}\rangle\langle\phi_{7,l}|)] \geq 1 - \sqrt{\eta_1} - \sqrt{\eta_2}$$
  Esto garantiza que el error es pequeño si los canales son buenos en promedio.

• Teorema 13 (Caso General): Para el caso general donde los autovalores no son exactos (requieren más de $n$ bits), se establece una cota inferior para la fidelidad que depende de los parámetros de error $\eta$ y un parámetro de truncamiento $K$. El error total se mantiene acotado y pequeño.

• Teoremas 14-18 (Caso Unitario): Se presentan versiones simplificadas y con mejores cotas de error para el caso donde los canales son unitarios. En particular, si se tiene acceso a $C$ y $C^{-1}$ (o se verifica que $C \circ P$ es cercano a la identidad), el algoritmo HHL funciona con alta precisión.

5. Significado e Impacto

• Viabilidad de Algoritmos Cuánticos en Hardware Ruidoso: Este trabajo es fundamental para la implementación práctica de algoritmos cuánticos complejos como HHL en dispositivos actuales (NISQ), donde la QFT perfecta es difícil de lograr. Permite confiar en el algoritmo incluso si los componentes individuales (QFT) solo funcionan bien "en promedio".
• Reducción de Costos de Verificación: Cambia el paradigma de requerir verificación de peor caso (exponencialmente difícil) a verificación de caso promedio (eficiente), sin sacrificar la corrección del resultado final en tareas críticas como la resolución de sistemas lineales.
• Generalización: Sugiere que esta metodología de "reducción de peor caso a promedio" puede aplicarse a otros algoritmos basados en QFT, como la tomografía cuántica o algoritmos de aprendizaje automático cuántico, ampliando el horizonte de aplicaciones verificables en computación cuántica.

En conclusión, Changpeng Shao demuestra que, mediante un protocolo de verificación ligeramente más estricto pero aún eficiente, es posible mitigar los efectos de las fases locales indeseadas, permitiendo que el algoritmo HHL sea robusto y funcional incluso con componentes de QFT imperfectos pero estadísticamente correctos.