Proof of hiding conjecture in Gaussian boson sampling

Resumen Técnico: Prueba de la Conjetura de Ocultamiento en el Muestreo de Bosones Gaussianos

1. Planteamiento del Problema

El Muestreo de Bosones Gaussianos (GBS, por sus siglas en la DIN) es un candidato principal para demostrar la ventaja computacional cuántica. El argumento para la dureza clásica de simular el GBS se basa en dos componentes principales: la conjetura de la dureza en el caso promedio de aproximar el hafian de una matriz, y la conjetura de ocultamiento.

La conjetura de ocultamiento afirma que una matriz gaussiana compleja (específicamente una con entradas independientes) puede ser "oculta" como una submatriz dentro del producto simétrico de una matriz unitaria de Haar, de tal manera que las dos distribuciones sean indistinguibles en distancia de variación total (TV). Esta propiedad es crucial porque permite embeber una matriz $Z$ específica y difícil de computar en la distribución de salida del GBS sin que un adversario (o un simulador clásico) pueda identificar la ubicación de $Z$ para corromper la estimación de la probabilidad.

Si bien la propiedad de ocultamiento para el muestreo de bosones estándar (Fock) se estableció para regímenes dispersos, el régimen relevante para los experimentos recientes de GBS a gran escala —donde todos los $M$ modos de entrada están comprimidos ($K=M$)— permanecía sin probar. En este régimen, la submatriz relevante es un bloque rectangular de $N \times M$ de una unitaria de Haar, la cual es conocida por no parecer una matriz gaussiana en distancia TV debido a las restricciones de normalización de filas. La pregunta abierta era si el producto simétrico de esta submatriz no gaussiana ($U_{N,M}U_{N,M}^T$) converge, no obstante, a una matriz gaussiana compleja simétrica en distancia TV.

2. Metodología

Los autores proporcionan una prueba rigurosa para el caso donde todos los modos de entrada están comprimidos ($K=M$). El núcleo de la metodología implica:

• Formulación de la Teoría de Matrices Aleatorias: El problema se mapea a demostrar que la submatriz superior izquierda $A$ de una matriz aleatoria del Conjunto Ortogonal Circular (COE) de $M \times M$ (distribuida como $UU^T$ donde $U$ es de Haar aleatoria) converge a una matriz gaussiana compleja simétrica $G \sim \mathcal{G}^{\text{sym}}_N$ cuando se escala por $\sqrt{M}$.
• Distancia de Variación Total vía Divergencia KL: En lugar de un acoplamiento directo, los autores acotan la distancia TV utilizando la desigualdad de Pinsker, que relaciona la distancia TV con la divergencia de Kullback-Leibler (KL) entre las dos distribuciones.
• Análisis de Densidad:
  • La función de densidad de probabilidad (PDF) de la submatriz COE se deriva de la literatura existente (Hua, 1963; Kieburg et al., 2013), involucrando un término determinante $\det(I - Z^\dagger Z/M)^{(M-2N-1)/2}$.
  • La PDF de la matriz gaussiana objetivo es la gaussiana compleja simétrica estándar.
• Manejo de Constantes de Normalización: Una innovación técnica clave es evitar el cálculo explícito de la constante de normalización compleja para la densidad del COE. En su lugar, los autores introducen un factor de escala $\zeta$ y demuestran que $\zeta \to 1$ cuando $M \to \infty$ utilizando cotas sobre los valores singulares de las matrices. Esto les permite sortear la difícil expansión asintótica de la constante de normalización mientras mantienen la validez de la prueba de convergencia.
• Cotas de Momentos: La prueba utiliza el cálculo de Weingarten para computar los momentos de los valores singulares (autovalores de $A^\dagger A$) y emplea desigualdades de concentración (concentración subgaussiana) para acotar la probabilidad de autovalores grandes, asegurando que la expansión de Taylor de los términos del logaritmo de la densidad permanezca válida.

3. Contribuciones Clave y Resultados

Teorema 1.1 / Teorema 1.2 (Resultado Principal):
Los autores prueban la conjetura de ocultamiento para GBS con todos los modos de entrada comprimidos ($K=M$). Específicamente, muestran que para $N = o(\sqrt{M})$, la distancia de variación total entre la submatriz COE escalada $\sqrt{M}A$ y la matriz gaussiana compleja simétrica $G$ desaparece cuando $M \to \infty$:
$$d_{\text{TV}}(\sqrt{M}A, G) \leq O\left(\frac{N}{\sqrt{M}}\right)$$
Esto establece que el producto simétrico $U_{N,M}U_{N,M}^T$ es bien aproximado por una matriz gaussiana compleja simétrica en el régimen experimentalmente relevante.

Corolario 1.1:
Los autores demuestran que la matriz gaussiana compleja simétrica $G$ (con entradas independientes) y el producto simétrico de matrices gaussianas rectangulares $GG^T$ son cercanos en la norma máxima elemento a elemento (y, por tanto, en distancia TV para $N$ suficientemente pequeño). Esto implica que la dureza de aproximar $\text{Haf}(G)$ es esencialmente equivalente a aproximar $\text{Haf}(GG^T)$ en el régimen relevante.

Teorema 1.3 (Estimación Multiplicativa):
El artículo proporciona una cota multiplicativa sobre las funciones de densidad: $f(Z) \leq (1 + O(N^3/M))g(Z)$. Este resultado es necesario para el método de "generación de instancias" utilizado en las pruebas de dureza, permitiendo la generación de una unitaria aleatoria que contiene una matriz gaussiana específica como una submatriz oculta.

Teorema 1.5 y 1.6 (Extensión al Régimen Disperso):
El artículo extiende la propiedad de ocultamiento al régimen disperso ($NK = o(M)$), confirmando que la conjetura de ocultamiento se cumple para $K < M$ en este régimen e incrementando los límites conocidos para el muestreo de bosones Fock hasta el tamaño máximo $N = o(\sqrt{M})$.

4. Significado y Reivindicaciones

El artículo afirma proporcionar la primera prueba rigurosa de la propiedad de ocultamiento para el muestreo de bosones gaussianos en el régimen experimentalmente relevante donde el número de modos comprimidos $K$ es proporcional al número total de modos $M$ (específicamente $K=M$).

• Argumento de Dureza: Al probar la conjetura de ocultamiento, los autores sitúan el argumento para la dureza clásica de simular el GBS con modos de entrada máximamente comprimidos en un "nivel comparable" al argumento de dureza para el muestreo de bosones Fock convencional (Aaronson y Arkhipov, 2013).
• Relevancia Experimental: El resultado respalda directamente la justificación teórico-computacional de experimentos recientes de GBS a gran escala (ej. Madsen et al., Nature 2022) que utilizan estados de entrada totalmente comprimidos.
• Matiz Teórico: Los autores enfatizan que la prueba depende de la distribución del producto simétrico de la submatriz, no de la submatriz misma. La submatriz $U_{N,M}$ está lejos de ser gaussiana en distancia TV, pero su producto simétrico $U_{N,M}U_{N,M}^T$ converge a una matriz gaussiana. Esta distinción es crítica, ya que los intentos previos de derivar la dureza de GBS a partir de las propiedades de ocultamiento de Fock fallaron en este régimen denso.

El artículo concluye señalando que, si bien el caso $K=M$ queda resuelto, la conjetura de ocultamiento para casos intermedios ($K=cM$ con $c<1$) permanece abierta en este trabajo específico (aunque los autores señalan que ha sido resuelta en un trabajo de seguimiento posterior [47]). El trabajo se adhiere estrictamente al régimen libre de colisiones ($N \ll M$) y se basa en conjeturas de complejidad teórica estándar respecto a la dureza en el caso promedio de la aproximación del hafian.