Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.01008

Uniform Hiding and Two Routes to Relative Accuracy in Gaussian Boson Sampling

Hongru Zhao

quant-phSubmitted Sep 1, 2026• Announced Sep 2, 2026• 0 citations• Revised Sep 11, 2026 (v2)
v1 · Sep 1, 2026v2 · Sep 11, 2026
arXivHTMLPDF

Abstract

Gaussian boson sampling requires control of how closely finite optical matrices follow Gaussian reference laws. We prove an explicit total variation bound of order $N^2/M$ between a rescaled Haar transpose Gram block and its Gaussian transpose Gram counterpart, where $N$ is the detected photon count and $M$ is the number of optical modes. The bound establishes quantitative product hiding uniformly over every number of squeezed inputs. The proof combines Stiefel recursion, centered circular orthogonal ensemble scores, and a rectangular entropy estimate. Applications combine hiding with local hafnian bounds to obtain relative probability guarantees and connect them to sampler error through exact photon-sector normalization.

Comments
49 pages, 5 figures, 4 tables

Related papers

Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes

Laura Shou, Alexey V. Gorshkov, Victor Galitski +1 more

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

quant-pharXiv:2608.19314•Aug 21, 2026•0 citations

Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry

Hongru Zhao

Local anticoncentration controls the conversion of additive output probability estimates to relative estimates in Gaussian boson sampling. We prove a center-uniform quadratic small-ball bound for hafnians of complex Gaussian transpose Gram matrices for $2n$ selected modes, with an explicit finite coefficient that is polynomial when the number of Gaussian rows is at least of order $n^2/\log n$. Letting the Gaussian row count tend to infinity yields anticoncentration for the independent complex symmetric Gaussian ensemble. For the transpose Gram hafnian bound, the proof compresses dependent hafnian cofactors by Fourier interpolation and controls their self-coupled variance through a conditional Wishart identity that preserves the transpose Gram coordinate. Independent perturbations satisfy related bounds, and a positive mixture density shows that the local quadratic power is exact. Together with the uniform hiding theorem in the companion paper, the result gives local anticoncentration for finite Haar interferometers.

math.PRCross-listedarXiv:2610.00112•Sep 10, 2026•0 citations

Proof of hiding conjecture in Gaussian boson sampling

Laura Shou, Sarah H. Miller, Victor M. Galitski

Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps in the argument for classical hardness of GBS is the so-called “hiding conjecture'', which asserts that one can “hide'' a complex Gaussian matrix as a submatrix of the symmetric product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with all input modes squeezed, which is a setup that has recently been realized experimentally \cite{madsen2022}. In this setting, the hiding conjecture states that a o ( M ) × o ( M ) submatrix of an M × M circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as M → ∞ . This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with the maximum number of squeezed input modes on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)] \cite{aa}.

arXiv:2508.00983•Quantum•Oct 27, 2026•0 citations

Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime

Youngrong Lim

Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number $N$ of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan $P$ representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the state exactly between detections and, after each detection, replaces the conditional state by a Gaussian with the same covariance. For every interferometer its total variation error is $O(Nη^3)$ at polynomial expected cost, where $η$ is the photon survival probability. The mean surviving photon number can therefore grow as $N^{2/3}$ at fixed accuracy. A separate pair construction reaches $N^{3/4}$ when every input mode is equally squeezed.

quant-pharXiv:2610.06526•Oct 6, 2026•0 citations

Near-Optimal Mode Scaling for Finite-Dimensional Boson Sampling via Lie-Algebraic Leakage Bounds

Chon-Fai Kam, En-Jui Kuo

Boson sampling demonstrates quantum advantage through the interference of indistinguishable particles, with output probabilities governed by matrix permanents. Realizing it on deterministic, matter-based platforms requires encoding the bosonic modes in finite-dimensional local Hilbert spaces, which introduces a leakage channel absent in linear optics: multi-particle bunching beyond the local truncation $d$. We develop a unified framework for non-interacting sampling on the irreducible representations of compact Lie groups, in which the transition amplitude is the immanant of a submatrix of the single-particle transition matrix, recovering the permanent in the bosonic case. Within this framework we bound the bunching leakage through a Dyson-series analysis: decomposing the correlated many-body leakage operator into independent random matrices and applying non-commutative concentration inequalities, we prove, in a Gaussian model of the transition matrix, that its spectral norm concentrates at $\tilde{O}(\sqrt{n})$ rather than the $O(n)$ worst-case of prior spin-based emulations; the passage to the physical Haar ensemble is reduced to a single submatrix-comparison input, verified at leading order. Exact numerics across local dimensions $d=2$--$5$ indicate that the bound is tight, the Haar-ensemble norm matching the closed form $\sqrt{d(n-d+1)}$ to sub-percent accuracy. This tightens the required mode number from $m=Ω(n^4)$ to the near-optimal $m=\tildeΩ(n^{1+2/(d-1)})$; for a spin-1 representation ($d=3$) the overhead falls to $m=\tildeΩ(n^2)$, matching the collision-free threshold. The result is independent of particle statistics and applies across finite-dimensional Lie-symmetric architectures, quantifying the spatial resources needed to preserve sampling hardness.

quant-pharXiv:2607.11708•Jul 14, 2026•0 citations

Boson sampling is fragile to loss

Youngrong Lim

Boson sampling experiments aim to demonstrate quantum computational advantage with increasing numbers of interfering photons. A central question is whether their computational hardness survives under photon loss. We show that even an arbitrarily small nonzero uniform loss rate permits efficient classical sampling in the average case when the rate remains fixed as the system grows. We exploit how loss suppresses correlations involving many photons to approximate the full output distribution using low correlation orders. The resulting samplers run in time polynomial in system size and inverse total variation error, with the error averaged over Haar random interferometers. The results apply to Fock state boson sampling with single-photon states in distinct input modes and arbitrary additional vacuum inputs, and to Gaussian boson sampling with equal squeezing of bounded strength in every input mode. Classical sampling is efficient even when the mean detected photon number grows linearly with system size, showing that large photon counts alone do not ensure computational hardness.

•Oct 21, 2026•0 citations
Gaussian boson sampling requires control of how closely finite optical matrices follow Gaussian reference laws. We prove an explicit total variation bound of order N2/MN^2/MN2/M between a rescaled Haar transpose Gram block and its Gaussian transpose Gram counterpart, where NNN is the detected photon count and MMM is the number of optical modes. The bound establishes quantitative product hiding uniformly over every number of squeezed inputs. The proof combines Stiefel recursion, centered circular orthogonal ensemble scores, and a rectangular entropy estimate. Applications combine hiding with local hafnian bounds to obtain relative probability guarantees and connect them to sampler error through exact photon-sector normalization.
Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on MMM optical modes, with KKK equally squeezed input modes and NNN observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers KKK, which is a part of the argument for classical hardness of GBS. In particular, we show that for any KKK and N=o(K)N=o(\sqrt{K})N=o(K​), the symmetric product MK−1/2UNKUNKTMK^{-1/2}U_{NK}U_{NK}^TMK−1/2UNK​UNKT​, for UNKU_{NK}UNK​ the top left N×KN\times KN×K submatrix of an M×MM\times MM×M Haar random unitary UUU, is close in total variation distance to both an N×NN\times NN×N symmetric complex Gaussian matrix G\mathbf GG with independent entries, and the symmetric product GGT/KGG^T/\sqrt{K}GGT/K​ for GGG an N×KN\times KN×K matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with K=cMK=cMK=cM if c<1/2c<1/2c<1/2. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.
Local anticoncentration controls the conversion of additive output probability estimates to relative estimates in Gaussian boson sampling. We prove a center-uniform quadratic small-ball bound for hafnians of complex Gaussian transpose Gram matrices for 2n2n2n selected modes, with an explicit finite coefficient that is polynomial when the number of Gaussian rows is at least of order n2/log⁡nn^2/\log nn2/logn. Letting the Gaussian row count tend to infinity yields anticoncentration for the independent complex symmetric Gaussian ensemble. For the transpose Gram hafnian bound, the proof compresses dependent hafnian cofactors by Fourier interpolation and controls their self-coupled variance through a conditional Wishart identity that preserves the transpose Gram coordinate. Independent perturbations satisfy related bounds, and a positive mixture density shows that the local quadratic power is exact. Together with the uniform hiding theorem in the companion paper, the result gives local anticoncentration for finite Haar interferometers.
Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps in the argument for classical hardness of GBS is the so-called “hiding conjecture'', which asserts that one can “hide'' a complex Gaussian matrix as a submatrix of the symmetric product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with all input modes squeezed, which is a setup that has recently been realized experimentally \cite{madsen2022}. In this setting, the hiding conjecture states that a o ( M ) × o ( M ) submatrix of an M × M circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as M → ∞ . This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with the maximum number of squeezed input modes on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)] \cite{aa}.
Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number NNN of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan PPP representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the state exactly between detections and, after each detection, replaces the conditional state by a Gaussian with the same covariance. For every interferometer its total variation error is O(Nη3)O(Nη^3)O(Nη3) at polynomial expected cost, where ηηη is the photon survival probability. The mean surviving photon number can therefore grow as N2/3N^{2/3}N2/3 at fixed accuracy. A separate pair construction reaches N3/4N^{3/4}N3/4 when every input mode is equally squeezed.
Boson sampling demonstrates quantum advantage through the interference of indistinguishable particles, with output probabilities governed by matrix permanents. Realizing it on deterministic, matter-based platforms requires encoding the bosonic modes in finite-dimensional local Hilbert spaces, which introduces a leakage channel absent in linear optics: multi-particle bunching beyond the local truncation ddd. We develop a unified framework for non-interacting sampling on the irreducible representations of compact Lie groups, in which the transition amplitude is the immanant of a submatrix of the single-particle transition matrix, recovering the permanent in the bosonic case. Within this framework we bound the bunching leakage through a Dyson-series analysis: decomposing the correlated many-body leakage operator into independent random matrices and applying non-commutative concentration inequalities, we prove, in a Gaussian model of the transition matrix, that its spectral norm concentrates at O~(n)\tilde{O}(\sqrt{n})O~(n​) rather than the O(n)O(n)O(n) worst-case of prior spin-based emulations; the passage to the physical Haar ensemble is reduced to a single submatrix-comparison input, verified at leading order. Exact numerics across local dimensions d=2d=2d=2--555 indicate that the bound is tight, the Haar-ensemble norm matching the closed form d(n−d+1)\sqrt{d(n-d+1)}d(n−d+1)​ to sub-percent accuracy. This tightens the required mode number from m=Ω(n4)m=Ω(n^4)m=Ω(n4) to the near-optimal m=Ω~(n1+2/(d−1))m=\tildeΩ(n^{1+2/(d-1)})m=Ω~(n1+2/(d−1)); for a spin-1 representation (d=3d=3d=3) the overhead falls to m=Ω~(n2)m=\tildeΩ(n^2)m=Ω~(n2), matching the collision-free threshold. The result is independent of particle statistics and applies across finite-dimensional Lie-symmetric architectures, quantifying the spatial resources needed to preserve sampling hardness.
Boson sampling experiments aim to demonstrate quantum computational advantage with increasing numbers of interfering photons. A central question is whether their computational hardness survives under photon loss. We show that even an arbitrarily small nonzero uniform loss rate permits efficient classical sampling in the average case when the rate remains fixed as the system grows. We exploit how loss suppresses correlations involving many photons to approximate the full output distribution using low correlation orders. The resulting samplers run in time polynomial in system size and inverse total variation error, with the error averaged over Haar random interferometers. The results apply to Fock state boson sampling with single-photon states in distinct input modes and arbitrary additional vacuum inputs, and to Gaussian boson sampling with equal squeezing of bounded strength in every input mode. Classical sampling is efficient even when the mean detected photon number grows linearly with system size, showing that large photon counts alone do not ensure computational hardness.