A complexity theory for non-local quantum computation

Resumen Técnico: Una Teoría de la Complejidad para la Computación Cuántica No Local

Planteamiento del Problema
La computación cuántica no local (NLQC, por sus siglas en inglés) reemplaza las interacciones locales entre dos sistemas con una única ronda de comunicación y entrelazamiento compartido. Una cantidad de interés central en la NLQC es el costo de entrelazamiento requerido para implementar computaciones específicas. Sin embargo, una caracterización completa de este costo enfrenta obstrucciones fundamentales: los límites inferiores de entrelazamiento para ciertas tareas de NLQC implicarían límites inferiores en medidas de complejidad establecidas (por ejemplo, complejidad de memoria o de comunicación), las cuales son notoriamente difíciles de probar. Por ejemplo, probar límites inferiores superpolinómicos para la tarea f-route para funciones en P separaría las clases de complejidad L y P.

Para sortear estas barreras directas de límites inferiores, los autores proponen un enfoque indirecto análogo a la teoría de la complejidad clásica: estudiar la dificultad relativa de diferentes tareas de NLQC mediante la identificación de reducciones eficientes de recursos entre ellas. El objetivo es establecer una "teoría de la complejidad" para la NLQC mapeando las relaciones entre diversas tareas, simplificando así las pruebas existentes y transfiriendo propiedades entre tareas equivalentes.

Metodología
El artículo introduce un marco formal para las reducciones de NLQC.

• Reducción de Estado de Recurso: Una tarea $G$ se reduce a $F$ si un estado de recurso suficiente para implementar $F$ (con un sobrecosto constante) puede utilizarse para implementar $G$.
• Reducción de Oráculo: Una forma más estricta donde el protocolo para $G$ utiliza el protocolo para $F$ como un oráculo (caja negra), lo que implica que las operaciones locales de $F$ pueden aplicarse directamente a $G$.
• Clases de Tareas: Los autores categorizan las tareas de NLQC en:
  1. Controladas Clásicamente: Protocolos donde una pequeña operación cuántica es controlada por una gran computación clásica (por ejemplo, f-route, f-measure, CDQS).
  2. Controladas Coherente mente: Protocolos que implementan unitarias controladas por entradas en superposición (por ejemplo, Cf-SWAP, Cf-PHASE, Cf-PAULI).
  3. Clases de Estado/Unitaria: Tareas definidas por transformaciones de estado en lugar de funciones booleanas (por ejemplo, Interchange y Distinguish).

La metodología consiste en construir reducciones explícitas (implicaciones) entre estas clases, aprovechando a menudo propiedades de la teoría de la información cuántica como la norma diamante, la fidelidad y las desigualdades de entropía (por ejemplo, la desigualdad CIT).

Contribuciones Clave y Resultados

1. Equivalencia de Tareas Controladas Clásicamente:
   El resultado principal es la prueba de que tres tareas importantes de NLQC controladas clásicamente son equivalentes bajo reducciones de sobrecosto $O(1)$:
   $$\text{f-route} \iff \text{f-measure} \iff \text{CDQS}$$

• f-route: Enrutamiento de un sistema cuántico $Q$ hacia Alice o Bob basado en una función booleana $f(x,y)$.
• f-measure: Alice y Bob producen un bit $b$ donde el estado de entrada es un estado BB84 determinado por $f(x,y)$.
• CDQS (Divulgación Condicional de Secretos): Una primitiva criptográfica donde un secreto se revela a un referente si y solo si $f(x,y)=1$.
• Implicación: Esta equivalencia simplifica significamente la literatura. Las propiedades previamente probadas por separado para f-route y f-measure ahora se aplican a ambas. Específicamente, f-measure hereda:
  • Un límite superior de $2^{O(\sqrt{n} \log n)}$ para todas las funciones.
  • Protocolos eficientes para funciones en la clase de complejidad $\text{Mod}_k\text{L}$.
  • Resultados de seguridad en el modelo de oráculo aleatorio y propiedades de repetición paralela.

2. Reducciones entre Operaciones Controladas Coherentemente:
   Los autores establecen una jerarquía y equivalencia entre tareas coherentes:

• Cf-SWAP $\implies$ Cf-PHASE: Implementar un intercambio coherente implica un desplazamiento de fase coherente.
• Cf-PHASE $\iff$ Cf-PAULI: Los autores prueban que las tareas de fase coherente son equivalentes a las tareas de Pauli coherentes (específicamente Cf-Z o Cf-PAULI) bajo sobrecosto constante.
• Coherente $\implies$ Clásico: Crucialmente, el artículo muestra que la primitiva coherente Cf-PHASE (y, por tanto, Cf-PAULI) es lo suficientemente fuerte como para implementar las tareas controladas clásicamente (f-route, f-measure, CDQS). Esto sugiere que los protocolos coherentes son al menos tan difíciles como, y potencialmente más difíciles que, los protocolos incoherentes.
• Composición: El artículo detalla cómo componer estas tareas coherentes (por ejemplo, añadiendo controles mediante operaciones AND) con solo un sobrecosto lineal en el número de controles.

3. Reducciones de Transformación de Estado:
   Los autores investigan tareas que no están definidas por funciones booleanas. Prueban que una NLQC eficiente para Interchange (intercambiar dos estados ortogonales $|\psi_0\rangle$ y $|\psi_1\rangle$) implica una NLQC eficiente para Distinguish (distinguir los estados de Fourier $|\phi_\pm\rangle = \frac{1}{\sqrt{2}}(|\psi_0\rangle \pm |\psi_1\rangle)$). Este resultado está inspirado en equivalencias similares en la complejidad de circuitos cuánticos estándar. La dirección inversa sigue siendo una pregunta abierta.

Significado y Reivindicaciones
El artículo sostiene que, al establecer estas reducciones, sienta las bases para una teoría de la complejidad más completa para la NLQC.

• Simplificación: La equivalencia de f-route, f-measure y CDQS unifica el estudio de estas tareas, permitiendo a los investigadores centrarse en una única primitiva representativa.
• Nuevas Propiedades: La transferencia de límites superiores (por ejemplo, de f-route a f-measure) proporciona nuevos protocolos eficientes y límites de complejidad para tareas previamente menos estudiadas.
• Perspectivas de la Teoría de la Complejidad: Los autores sugieren que estudiar estas reducciones puede, eventualmente, ofrecer una vía hacia nuevos límites inferiores en las medidas de complejidad. Dado que los costos de entrelazamiento en NLQC están acotados superiormente por las medidas de complejidad, probar límites inferiores para las tareas de NLQC podría producir límites inferiores para las clases de complejidad.
• Barreras: El artículo reconoce que probar límites inferiores lineales para estas tareas enfrenta la misma "barrera CDS" que la criptografía clásica, donde tales límites implicarían avances en la complejidad de comunicación clásica.
• Preguntas Abiertas: Los autores declaran explícitamente que no han probado que todas las tareas coherentes sean estrictamente más difíciles que todas las tareas incoherentes, ni han probado la dirección inversa de la reducción Interchange/Distinguish. También señalan que, aunque Cf-SWAP implica Cf-PHASE, la implicación inversa aún no se ha establecido.

En resumen, el artículo desplaza el enfoque de la estimación directa del costo de entrelazamiento hacia un análisis estructural de las tareas de NLQC, demostando que muchas tareas distintas son computacionalmente equivalentes y que el control coherente ofrece un marco poderoso y, potencialmente, más difícil para la computación no local.