Quantum Approximation Complexity of Classical Optimization Problems

Título: Complejidad de Aproximación Cuántica de Problemas de Optimización Clásica
Autor: Stuart Hadfield

Planteamiento del Problema

El artículo aborda la falta de garantías rigurosas de rendimiento en el peor de los casos para los algoritmos de optimización cuántica. Aunque muchos métodos cuánticos (por ejemplo, QAOA, DQI) demuestran puntuaciones altas en instancias específicas o proporcionan límites sobre valores esperados (medias decodificadas), a menudo carecen de algoritmos uniformes que garanticen un ratio de aproximación específico para cada entrada con un error acotado. El trabajo busca definir formalmente los análogos cuánticos de las clases de complejidad de aproximación clásica (APX, PTAS, FPTAS) y determinar si la computación cuántica puede mejorar estrictamente sobre los algoritmos clásicos aleatorizados en términos de la calidad de la solución garantizada o el tiempo requerido para alcanzar una precisión solicitada.

Metodología

El autor extiende el marco de los problemas de Optimización NP (NPO) para incluir algoritmos cuánticos de error acotado.

1. Definición de Clases Cuánticas: El artículo define BQ-APX, BQ-PTAS y BQ-FPTAS. La pertenencia a estas clases requiere un algoritmo cuántico uniforme que, en cada entrada, devuelva una solución clásica factible que logre el ratio de aproximación pretendido con una probabilidad de al menos $2/3$. Crucialmente, el tiempo de ejecución incluye todos los pasos: selección de parámetros, preparación del estado, medición, decodificación y repetición. La puntuación de la solución debe ser computable eficientamente de forma clásica.
2. Transferencia de Media-Decodificada a Salida: Una herramienta técnica clave es el Lema 6 y el Corolario 7, que establecen una relación entre la puntuación esperada de una solución decodificada y una garantía de salida clásica de error acotado. Esto permite la traducción de los análisis basados en la esperanza (comunes en la literatura cuántica) hacia las estrictas garantías de salida requeridas para la pertenencia a una clase.
3. Separaciones Condicionales: El artículo construye problemas específicos para demostrar inclusiones estrictas entre clases cuánticas y clásicas bajo supuestos de complejidad estándar (por ejemplo, $NP \not\subseteq BQP$ y $Factor \notin FBPP$). Estas construcciones se basan en el "relleno de búsqueda" (search padding) y la dureza criptográfica.

Contribuciones Clave y Resultados

1. Jerarquía Formal de Clases de Aproximación Cuántica
El artículo establece una jerarquía estricta para las clases de aproximación cuántica bajo el supuesto de que $NP \not\subseteq BQP$:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
Esta jerarquía es testimoniada por problemas clásicos:

• Max-E3SAT: Tiene una aproximación de ratio constante determinista (en APX) pero no posee un PTAS cuántico.
• Vertex Cover Planar: Tiene un PTAS determinista pero no posee un FPTAS cuántico.
  Estos resultados muestran que las clases cuánticas son distintas entre sí, aunque todavía no separan lo cuántico de lo clásico aleatorizado para estos problemas específicos.

2. Orden Máximo Certificado (CMO): Una Fuerte Separación Cuántica–Clásica
El artículo introduce el problema del Orden Máximo Certificado (CMO), donde el objetivo es encontrar el orden multiplicativo de un elemento módulo $N$ que esté certificado por una factorización de primos del orden.

• Resultado Cuántico: Un algoritmo cuántico de error acotado puede encontrar el óptimo exacto (la función de Carmichael $\lambda(N)$) en tiempo polinómico utilizando factorización y búsqueda de periodos. Por lo tanto, $CMO \in BQ\text{-}FPTAS$.
• Barrera Clásica: Cualquier algoritmo de tiempo polinómico aleatorizado que garantice incluso un ratio de aproximación de factor polinómico para CMO implicaría un algoritmo de factorización aleatorizado en tiempo polinómico.
• Conclusión: Asumiendo que $Factor \notin FBPP$, $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. Esto establece una separación condicional donde los algoritmos cuánticos proporcionan soluciones exactas mientras que los algoritmos clásicos aleatorizados ni siquiera pueden lograr aproximaciones de factor polinómico.

3. Ajuste de Logaritmo Discreto (DLog-Fit): Una Separación de Umbral
El artículo define DLog-Fit, un problema que implica predecir etiquetas en una muestra basada en logaritmos discretos.

• Línea Base Clásica: Un algoritmo determinista logra una aproximación de $1/2$ (prediciendo la etiqueta mayoritaria).
• Ventaja Cuántica: Un algoritmo cuántico puede encontrar un ajuste perfecto (el óptimo exacto).
• Barrera Clásica: Cualquier mejora fija sobre el ratio de $1/2$ por parte de un algoritmo clásico aleatorizado resolvería el problema del logaritmo discreto en un subgrupo de primo seguro.
• Conclusión: Bajo el supuesto de que el logaritmo discreto de primo seguro no está en $FBPP$, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. Esto demuestra una brecha en el umbral de aproximación de $1/2$.

4. Relleno de Búsqueda General (Teorema 8)
El artículo proporciona una construcción genérica que muestra cómo cualquier problema de búsqueda con testigos verificables eficientemente puede transformarse en un problema NPO con un umbral de aproximación de $1/2$. Si existe un resolvedor cuántico para la búsqueda pero un resolvedor clásico aleatorizado no, el problema de optimización resultante reside en $BQ\text{-}FPTAS$ pero fuera de $R\text{-}PTAS$.

5. Análisis de Métodos Cuánticos Existentes
El artículo aplica estas definiciones a algoritmos existentes:

• QAOA: Para un QAOA de profundidad fija en MaxCut 3-regular, el artículo utiliza la transferencia de media-decodificada para mostrar que la repetición puede producir una garantía de salida de error acotado (por ejemplo, excediendo $2/3$ del óptimo), situando a esta familia de grafos específica en $BQ\text{-}APX$.
• Interferometría Cuántica Decodificada (DQI): El artículo señala que, si bien el DQI muestra puntuaciones esperadas mejoradas en familias específicas (como OPI plegado), establecer una separación en el modelo de tiempo de entrada explícito requiere probar que los algoritmos clásicos aleatorizados no pueden lograr el mismo ratio, lo cual sigue siendo un desafío abierto para problemas sin restricciones.

Significancia y Reivindicaciones

El artículo afirma proporcionar las primeras definiciones rigurosas para las clases de aproximación cuántica de error acotado y demostrar que, bajo supuestos de complejidad explícitos, la computación cuántica puede mejorar estrictamente las garantías de aproximación en el peor de los casos comparado con la computación clásica aleatorizada.

• Alcance Modesto: El autor establece explícitamente que para problemas comunes y sin restricciones como MaxCut o MaxSAT, una brecha cuántica-clásica en los ratios de aproximación en el peor de los casos sigue siendo un problema abierto. Las separaciones establecidas dependen de construcciones de problemas específicos, a menudo criptográficos (CMO, DLog-Fit), o familias de grafos restringidas.
• Marco Teórico: El trabajo cierra la brecha entre el rendimiento cuántico heurístico (a menudo medido por valores de esperanza) y la teoría de la complejidad rigurosa (garantías de salida de error acotado). Clarifica que las puntuaciones altas en los benchmarks por sí solas no establecen la membresía de una clase de aproximación sin uniformidad y límites de tiempo de ejecución.
• Dirección Futura: El artículo identifica la búsqueda de un algoritmo cuántico uniforme que garantice un ratio mejor que el umbral de dureza clásica para problemas estándar (como MaxCut sin restricciones) como el problema central en el campo.