IQP circuits for 2-Forrelation

Resumen Técnico: Circuitos IQP para 2-Forrelation

1. El Problema: 2-Forrelation

El problema central de este trabajo es el 2-Forrelation, una tarea de decisión introducida por Aaronson y desarrollada posteriormente por Aaronson y Ambainis.

• Definición: Dado acceso a oráculos cuánticos para dos funciones $f, g: \{0, 1\}^n \to \{-1, +1\}$, el objetivo es determinar si la "forrelation" $\Phi(f, g)$ es grande o pequeña en valor absoluto.
  $$\Phi(f, g) = \frac{1}{2^{3n/2}} \sum_{x,y \in \{0,1\}^n} (-1)^{x \cdot y} f(x)g(y)$$
• Importancia: Este problema ofrece la separación óptima conocida entre la complejidad de consultas clásica y cuántica ($\Theta(2^{n/2})$ vs $O(1)$). Además, fue utilizado por Raz y Tal para demostrar la separación entre la clase de complejidad cuántica BQP y la Jerarquía Polinómica (PH) relativa a un oráculo.
• La Pregunta Abierta: Aunque BQP puede resolverlo fácilmente, ¿cuáles son los recursos cuánticos mínimos necesarios? Específicamente, ¿pueden resolverlo modelos restringidos como los circuitos IQP (Instantaneous Quantum Polynomial-time), donde todas las puertas conmutan? Girish planteó recientemente esta cuestión como un problema abierto.

2. Metodología y Construcción

Los autores demuestran que el problema 2-Forrelation puede resolverse utilizando computaciones IQP (circuitos donde las puertas son diagonales en la base X, o equivalentemente, de la forma $H^{\otimes m} D H^{\otimes m}$, donde $D$ es diagonal en la base Z).

Estrategia Principal:

1. Absorción del Oráculo: Dado que el oráculo combinado $O_{f,g}$ es diagonal en la base computacional, puede ser absorbido en la capa diagonal $D$ de un circuito IQP.
2. Identidad Algebraica Clave: El núcleo de la construcción es una identidad algebraica para la función cuadrática $Q(x) = \sum_{i<j} x_i x_j$ sobre $\mathbb{F}_2$:
   $$Q(x) + Q(y) + Q(x+y) = x \cdot y + |x||y| \pmod 2$$
   Donde $|x|$ es el peso de Hamming.
   • Si $|x+y|$ es impar, entonces $|x||y| \equiv 0 \pmod 2$, simplificando la identidad a $Q(x) + Q(y) + Q(x+y) = x \cdot y$.
   • Esto permite "linealizar" el producto interno $x \cdot y$ dentro del circuito, corrigiendo con un término de paridad.

Construcción del Circuito:

• Caso $n$ impar: Se construyen dos circuitos IQP distintos basados en la paridad de $|x+y|$:
  • Un circuito que acepta con probabilidad $1/2 + \frac{1}{\sqrt{2}}\Phi_{odd}(f, g)$.
  • Otro circuito que acepta con probabilidad $1/2 + \frac{1}{\sqrt{2}}\Phi_{even}(f, g)$.
  • Se ejecuta uno de ellos aleatoriamente (pre-procesamiento clásico) para obtener una probabilidad de aceptación dependiente de $\Phi(f, g)$.
• Caso $n$ par: Se utiliza un argumento de "relleno" (padding) añadiendo una variable dummy para reducir el problema al caso impar, con un costo constante en la ventaja.
• Variante de Valor Absoluto: Para resolver la variante donde se busca $|\Phi(f, g)|$, se ejecutan dos copias independientes del circuito y se acepta si ambos dan el mismo resultado. Esto eleva la probabilidad a depender de $\Phi^2(f, g)$.

3. Contribuciones Clave

1. Resolución de 2-Forrelation con IQP:

   • Se demuestra que 2-Forrelation puede resolverse con un solo circuito IQP y una consulta cuántica (para la variante con signo) o dos consultas (para la variante de valor absoluto), acompañadas de pre y post-procesamiento clásico eficiente.
   • Esto define la clase BPPIQP (BPP con acceso a oráculos IQP) como suficiente para resolver el problema.

2. Separación de Oráculos (BPPIQP vs PH):

   • Utilizando la construcción anterior, los autores extienden el resultado de Raz y Tal. Demuestran que, relativo a un oráculo $O$, la clase BPPIQP no está contenida en PH ($(\text{BPPIQP})^O \not\subseteq \text{PH}^O$).
   • Esto es significativo porque IQP es un modelo estrictamente más débil que BQP, lo que implica que la separación entre PH y modelos cuánticos restringidos es más fuerte de lo que se pensaba.

3. Límites de Crecimiento de Fourier para IQP:

   • Los autores establecen límites superiores para el crecimiento de Fourier de la probabilidad de aceptación $p$ de circuitos IQP.
   • Demuestran que para un circuito de una consulta con conjunto de aceptación $F$, la norma $\ell_1$ de los coeficientes de Fourier satisface: $\|\hat{p}\|_1 \leq \sqrt{\min\{|F|, 2^n\}}$.
   • Esto implica que cualquier circuito IQP que resuelva 2-Forrelation con ventaja constante debe tener un conjunto de aceptación exponencialmente grande ($|F| = \Omega(2^n)$). Su construcción es óptima en este sentido ($|F| = 2^n$).

4. Resultados Cuantitativos

• Probabilidad de Aceptación (n impar, variante con signo):
  $$P_{acc} = \frac{1}{2} + \frac{1}{2\sqrt{2}}\Phi(f, g)$$
• Probabilidad de Aceptación (n par, variante con signo):
  $$P_{acc} = \frac{1}{2} + \frac{1}{4}\Phi(f, g)$$
• Probabilidad de Aceptación (Variante $|\Phi|$):
  $$P_{acc} = \frac{1}{2} + \Theta(\Phi^2(f, g))$$
• Separación de Oráculos: Un algoritmo BPPIQP puede distinguir entre la distribución uniforme y la distribución estructurada de Raz-Tal con ventaja polinómica usando $O(n^4)$ consultas, mientras que cualquier algoritmo en PH requiere un número exponencial de consultas.

5. Significado e Implicaciones

• Potencia de los Modelos Conmutativos: El trabajo demuestra que la potencia cuántica necesaria para problemas "duros" como 2-Forrelation no requiere la complejidad completa de BQP (puertas no conmutativas). Los circuitos IQP, que son estructuralmente más simples y potencialmente más fáciles de implementar físicamente (menor tiempo de coherencia, corrección de errores más sencilla), son suficientes.
• Ventaja Cuántica Verificable: A diferencia de las tareas de muestreo (como BosonSampling), que son difíciles de verificar clásicamente, 2-Forrelation es un problema de decisión. Esto abre una nueva ruta para demostrar ventaja cuántica con circuitos IQP que sea verificable clásicamente, evitando los cuellos de botella de verificación asociados a las tareas de muestreo.
• Límites de la Jerarquía Polinómica: Al mostrar que incluso un modelo tan restringido como IQP (dentro de BPPIQP) supera a PH, se fortalecen las evidencias de que la computación cuántica reside en un nivel de complejidad fundamentalmente distinto y superior a la jerarquía polinómica clásica.
• Limitaciones: Los autores aclaran que IQP no puede resolver 3-Forrelation (basado en resultados previos de Girish), lo que indica que, aunque potente, IQP sigue siendo estrictamente inferior a BQP completo.

En conclusión, este artículo cierra una brecha teórica importante al demostrar que la "ventaja cuántica" para problemas de decisión óptimos puede lograrse con recursos cuánticos mínimos (circuitos conmutativos), proporcionando al mismo tiempo herramientas teóricas (límites de Fourier) para analizar la potencia de estos modelos restringidos.