Proof of hiding conjecture in Gaussian boson sampling

Technische Samenvatting: Bewijs van de Hiding-conjectuur in Gaussian Boson Sampling

1. Probleemstelling

Gaussian Boson Sampling (GBS) is een belangrijke kandidaat voor het demonstreren van kwantumcomputationele superioriteit. Het argument voor de klassieke hardheid van het simuleren van GBS rust op twee hoofdcomponenten: de veronderstelde gemiddelde-geval-hardheid van het benaderen van de hafnian van een matrix, en de hiding-conjectuur.

De hiding-conjectuur stelt dat een complexe Gaussische matrix (specifiek één met onafhankelijke elementen) als een submatrix "verborgen" kan worden binnen het symmetrische product van een Haar-willekeurige unitaire matrix, zodanig dat de twee distributies ononderscheidbaar zijn in de totale variatieafstand (TV-afstand). Deze eigenschap is cruciaal omdat het een mogelijk maakt om een specifieke moeilijke te berekenen matrix $Z$ in de GBS-outputdistributie te embedden, zonder dat een tegenstander (of een klassieke simulator) de locatie van $Z$ kan identificeren om de probabiliteitschatting te corrumperen.

Hoewel de hiding-eigenschap voor standaard (Fock) boson sampling is vastgesteld in ijle (sparse) regimes, bleef het regime dat relevant is voor recente grootschalige GBS-experimenten — waar alle $M$ input-modi gesqueezed zijn ($K=M$) — onbewezen. In dit regime is de relevante submatrix een $N \times M$ rechthoekige blok van een Haar-unitaire matrix, die bekend staat als niet Gaussisch te lijken in TV-afstand vanwege de rij-normalisatiebeperkingen. De openstaande vraag was of het symmetrische product van deze niet-Gaussische submatrix ($U_{N,M}U_{N,M}^T$) desondanks convergeert naar een complexe symmetrische Gaussische matrix in TV-afstand.

2. Methodologie

De auteurs leveren een rigoureus bewijs voor het geval waarin alle input-modi gesqueezed zijn ($K=M$). De kern van de methodologie omvat:

• Random Matrix Theory Formulering: Het probleem wordt gemapt naar het aantonen dat de linkerboven $N \times N$ submatrix $A$ van een $M \times M$ Circular Orthogonal Ensemble (COE) willekeurige matrix (verdeeld als $UU^T$ waarbij $U$ Haar-willekeurig is) convergeert naar een complexe symmetrische Gaussische matrix $G \sim \mathcal{G}^{\text{sym}}_N$ wanneer deze geschaald wordt met $\sqrt{M}$.
• Totale Variatieafstand via KL-divergentie: In plaats van directe koppeling, begrenzen de auteurs de TV-afstand via Pinsker's ongelijkheid, die de TV-afstand relateert aan de Kullback-Leibler (KL) divergentie tussen de twee distributies.
• Dichtheidsanalyse:
  • De waarschijnlijkheidsdichtheidsfunctie (PDF) van de COE-submatrix wordt afgeleid uit bestaande literatuur (Hua, 1963; Kieburg et al., 2013), inclusief een determinantterm $\det(I - Z^\dagger Z/M)^{(M-2N-1)/2}$.
  • De PDF van de doel-Gaussische matrix is de standaard complexe symmetrische Gaussische matrix.
• Afhandeling van Normalisatieconstanten: Een belangrijke technische innovatie is het vermijden van de expliciete berekening van de complexe normalisatieconstante voor de COE-dichtheid. In plaats daarvan introduceren de auteurs een schaalfactor $\zeta$ en bewijzen zij dat $\zeta \to 1$ als $M \to \infty$ met behulp van grenzen op de singuliere waarden van de matrices. Dit stelt hen in staat om de moeilijke asymptotische expansie van de normalisatieconstante te omzeilen terwijl de geldigheid van het convergentiebewijs behouden blijft.
• Momenten-grenzen: Het bewijs maakt gebruik van de Weingarten-calculus om de momenten van de singuliere waarden (eigenwaarden van $A^\dagger A$) te berekenen en gebruikt concentratie-ongelijkheden (subgaussische concentratie) om de waarschijnlijkheid van grote eigenwaarden te begrenzen, wat garandeert dat de Taylor-expansie van de log-dichtheidstermen geldig blijft.

3. Belangrijkste Bijdragen en Resultaten

Stelling 1.1 / Stelling 1.2 (Hoofdresultaat):
De auteurs bewijzen de hiding-conjectuur voor GBS met alle gesqueezde input-modi ($K=M$). Specifiek tonen zij aan dat voor $N = o(\sqrt{M})$, de totale variatieafstand tussen de geschaalde COE-submatrix $\sqrt{M}A$ en de complexe symmetrische Gaussische matrix $G$ verdwijnt als $M \to \infty$:
$$d_{\text{TV}}(\sqrt{M}A, G) \leq O\left(\frac{N}{\sqrt{M}}\right)$$
Dit vestigt dat de symmetrische product $U_{N,M}U_{N,M}^T$ goed benaderd wordt door een complexe symmetrische Gaussische matrix in het experimenteel relevante regime.

Corollary 1.1:
De auteurs demonstreren dat de complexe symmetrische Gaussische matrix $G$ (met onafhankelijke elementen) en het symmetrische product van rechthoekige Gaussische matrices $GG^T$ dicht bij elkaar liggen in de entrywise maximumnorm (en dus in TV-afstand voor voldoende kleine $N$). Dit impliceert dat de hardheid van het benaderen van $\text{Haf}(G)$ essentieel gelijkwaardig is aan het benaderen van $\text{Haf}(GG^T)$ in het relevante regime.

Stelling 1.3 (Multiplicatieve Schatting):
Het artikel biedt een multiplicatieve grens op de dichtheidsfuncties: $f(Z) \leq (1 + O(N^3/M))g(Z)$. Dit resultaat is noodzakelijk voor de "instance generating" methode die gebruikt wordt in hardheidsbewijzen, waardoor de generatie van een willekeurige unitaire matrix die een specifieke verborgen Gaussische matrix bevat, mogelijk wordt gemaakt.

Stelling 1.5 & 1.6 (Extensie naar het ijle regime):
Het artikel breidt de hiding-eigenschap uit naar het ijle (sparse) regime ($NK = o(M)$), waarmee wordt bevestigd dat de hiding-conjectuur standhoudt voor $K < M$ in dit regime, en verbetert de bekende grenzen voor Fock boson sampling naar de maximale grootte $N = o(\sqrt{M})$.

4. Betekenis en Claims

Het artikel claimt het eerste rigoureuze bewijs te leveren voor de hiding-eigenschap van Gaussian boson sampling in het experimenteel relevante regime waar het aantal gesqueezde modi $K$ proportioneel is aan het totaal aantal modi $M$ (specifiek $K=M$).

• Hardheidsargument: Door de hiding-conjectuur te bewijzen, plaatsen de auteurs het argument voor de klassieke hardheid van het simuleren van GBS met maximaal aantal gesqueezde input-modi op een "vergelijkbaar niveau" met het hardheidsargument voor conventionele Fock boson sampling (Aaronson en Arkhipov, 2013).
• Experimentele Relevantie: Het resultaat ondersteunt direct de complexiteit-theoretische rechtvaardiging voor recente grootschalige GBS-experimenten (bijv. Madsen et al., Nature 2022) die gebruikmaken van volledig gesqueezde input-toestanden.
• Theoretische Nuance: De auteurs benadrukken dat het bewijs berust op de distributie van het symmetrische product van de submatrix, en niet op de submatrix zelf. De submatrix $U_{N,M}$ is verre van Gaussisch in TV-afstand, maar het symmetrische product $U_{N,M}U_{N,M}^T$ convergeert naar een Gaussische matrix. Dit onderscheid is cruciaal, aangezien eerdere pogingen om GBS-hardheid af te leiden uit de hiding-eigenschappen van Fock boson sampling faalden in dit dichte regime.

Het artikel concludeert door op te merken dat hoewel de $K=M$ casus is opgelost, de hiding-conjectuur voor tussenliggende gevallen ($K=cM$ met $c<1$) open blijft in dit specifieke werk (hoewel de auteurs opmerken dat dit in later vervolgwerk [47] is opgelost). Het werk houdt zich strikt aan het collision-free regime ($N \ll M$) en steunt op standaard complexiteit-theoretische conjecturen betreffende de gemiddelde-geval-hardheid van de hafnian-benadering.