Equivalence of non-local computation tasks beyond Clifford operations

Resumen Técnico: Equivalencia de Tareas de Computación No Local Más Allá de las Operaciones de Clifford

Planteamiento del Problema
La computación cuántica no local (NLQC, por sus siglas en inglés) investiga cómo dos partes espacialmente separadas, Alice y Bob, pueden implementar un canal cuántico conjunto sobre sistemas distribuidos utilizando únicamente una única ronda simultánea de comunicación cuántica y entrelazamiento compartido. Si bien se sabe que cualquier canal cuántico puede implementarse mediante NLQC, el costo de los recursos —específicamente la cantidad de entrelazamiento precompartido requerida— varía significativamente entre diferentes tareas.

Una motivación principal para estudiar la NLQC es su aplicación en la Verificación de Posición Cuántica (QPV). En la QPV, un probador intenta convencer a los verificadores de su ubicación física. Un probador tramposo, ubicado en otro lugar, debe simular las operaciones locales del probador honesto utilizando NLQC. La seguridad de un esquema de QPV depende de la dificultad de la tarea de NLQC: si un probador tramposo requiere una cantidad exponencialmente grande de entrelazamiento para simular la tarea, el esquema se considera seguro.

El problema central abordado en este trabajo es la falta de una comprensión unificada de la dificultad relativa de las diferentes tareas de NLQC. Específicamente, aunque la tarea de "f-routing" (enrutamiento controlado clásicamente de un sistema cuántico) ha sido ampliamente estudiada, no está claro si otras protocolos de QPV plausibles —particularmente aquellos que involucran mediciones cuánticas controladas o unitarios más allá del simple enrutamiento— ofrecen una seguridad mejorada. Los autores pretenden determinar si estas tareas, aparentemente distintas, son reducibles entre sí, estableciendo así si comparten el mismo costo de entrelazamiento asintótico.

Metodología
Los autores emplean un marco de reducciones entre familias de tareas de NLQC, análogas a las reducciones en la teoría de la complejidad computacional. Definen dos tipos de reducciones:

1. Reducción de Estado de Recurso: Una tarea $G$ se reduce a una tarea $F$ si $G$ puede implementarse utilizando un número pequeño de copias del estado de recurso requerido para $F$.
2. Reducción de Oráculo: Una tarea $G$ se reduce a una tarea $F$ si $G$ puede implementarse utilizando un número pequeño de llamadas a un oráculo de caja negra que implementa $F$, además de operaciones locales y una pequeña cantidad de recursos compartidos adicionales.

El artículo se centra en las tareas de 2→2 controladas por $f$, donde la operación realizada depende del valor de una función booleana $f(x, y)$ dada a Alice ($x$) y Bob ($y$). Los sistemas de entrada son típicamente de tamaño constante (O(1) qubits), mientras que las entradas clásicas pueden ser grandes ($n$ bits).

El enfoque técnico involucra:

• Teleportación de Puertas y Computación Cuántica Basada en Mediciones (MBQC): Los autores utilizan gadgets inspirados en la teleportación de puertas y en la MBQC no adaptativa para construir protocolos que transformen una tarea de NLQC en otra.
• Caracterización y Manipulación de Ángulos: Para mediciones de un solo qubit, los autores caracterizan las tareas mediante ángulos de rotación en la esfera de Bloch. Desarrollan técnicas para añadir, dividir y aproximar estos ángulos utilizando combinaciones de protocolos más simples (por ejemplo, combinar protocolos de $f$-medición con ángulos $\theta_1$ y $\theta_2$ para simular $\theta_1 + \theta_2$).
• Teleportación Basada en Puertos (Port-Based Teleportation): Utilizada en los apéndices para demostrar que la distribución espacial de los inputs cuánticos (ya sea en el lado de Alice, el lado de Bob, o divididos) no altera significativamente la dificultad de la tarea, siempre que el tamaño de la entrada sea constante.

Contribuciones Clave y Resultados

1. Equivalencia de Protocolos de $f$-Medición de un Solo Qubit:
   Los autores demuestran que todos los protocolos de $f$-medición de un solo qubit no triviales (donde la base de medición se elige entre dos bases arbitrarias $U$ y $V$ basadas en $f(x,y)$) son equivalentes bajo reducciones de oráculo de O(1).

   • Específicamente, cualquier $f$-medición($U, V$) puede reducirse al caso canónico $f$-medición($I, H$) (medición en las bases computacional o de Hadamard).
   • Esto implica que ningún protocolo de medición proyectiva de un solo qubit ofrece una ventaja de seguridad sobre el caso más simple, ya que todos heredan los mismos límites superiores de entrelazamiento sub-exponenciales conocidos para el $f$-routing.

2. Reducción de Operaciones de Clifford Controladas:
   El artículo demuestra que las unitarias de Clifford controladas por $f$ y las mediciones en bases relacionadas con Clifford pueden reducirse a $f$-medición($I, H$).

   • Al establecer una equivalencia entre $f$-medición($I, H$) y $f$-medición de Bell (medición en la base de Bell), los autores muestran que las operaciones de Clifford controladas pueden implementarse mediante estrategias de teleportación de puertas utilizando oráculos de $f$-Bell.
   • Esto extiende la clase de tareas reducibles al $f$-routing, confirmando que incluso las operaciones de Clifford controladas por múltiples qubits no requieren inherentemente más entrelazamiento que la tarea básica de routing.

3. Extensión a Unitarios Diagonales Controlados:
   Un resultado significativo es la reducción de unitarios controlados por $f$ de la forma $U = C_1 D C_0$, donde $C_0, C_1$ son circuitos de Clifford y $D$ es un unitario diagonal arbitrario.

   • Los autores muestran que $f$-unitary($I, U$) puede reducirse por oráculo a $f$-medición($I, H$) con un exceso de O($n_Q$) (donde $n_Q$ es el número de qubits).
   • Esto es sorprendente porque $D$ puede tener una profundidad-T alta, lo que hace que $U$ sea altamente no-Clifford. Sin embargo, el costo de implementación sigue ligado a la tarea de $f$-medición basada en Clifford más simple.
   • La construcción se basa en "gadgets de inyección de rotación-Z" que relacionan las rotaciones-X controladas de un solo qubit (implementables vía $f$-medición) con las rotaciones-Z multiqubit controladas mediante puertas CZ.

Significancia y Reivindicaciones
El artículo afirma que el panorama de los protocolos de QPV factibles está más restringido de lo que se pensaba anteriormente. Al establecer una rica estructura de reducciones, los autores demuestran que:

• Limitaciones de Seguridad: Muchos de los esquemas de QPV propuestos que involucran mediciones controladas de un solo qubit, operaciones de Clifford e incluso ciertos unitarios diagonales no-Clifford, no ofrecen una seguridad mejorada sobre la tarea básica de $f$-routing. Todos comparten la misma escala asintótica para el costo de entrelazamiento (sub-exponencial en el tamaño de la entrada clásica).
• Dificultad Unificada: La dificultad relativa de estas tareas está unificada; si existe un ataque sub-exponencial para el $f$-routing, este se extiende a estas clases más amplias de tareas a través de las reducciones establecidas.
• Avance de Técnicas: El trabajo introduce nuevas estrategias para NLQC, tales como gadgets específicos de teleportación de puertas y técnicas de división de ángulos, que pueden ser de interés independiente para construir límites superiores de los costos de entrelazamiento para otras tareas de NLQC.

Los autores se mantienen modestos respecto al alcance de estos resultados, señalando que, si bien cubren una amplia clase de protocolos "factibles" (entrada clásica grande, entrada cuántica pequeña), sigue siendo una pregunta abierta si dos capas de puertas diagonales u otras estructuras unitarias más complejas podrían proporcionar niveles de seguridad más altos que evadan estas reducciones. Los resultados no pretenden probar límites inferiores super-lineales, sino más bien aclarar que muchas extensiones intuitivas del $f$-routing no escapan a los límites superiores conocidos.