arXiv:2403.13878

The Second Moment of Hafnians in Gaussian Boson Sampling

Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande, Dominik Hangleiter, Alexey Vyacheslavovich Gorshkov

Published Mar 20, 2024• 0 citations

Abstract

Gaussian Boson Sampling is a popular method for experimental demonstrations of quantum advantage, but many subtleties remain in fully understanding its theoretical underpinnings. An important component in the theoretical arguments for approximate average-case hardness of sampling is anticoncentration, which is a second-moment property of the output probabilities. In Gaussian Boson Sampling these are given by hafnians of generalized circular orthogonal ensemble matrices. In a companion work [arXiv:2312.08433], we develop a graph-theoretic method to study these moments and use it to identify a transition in anticoncentration. In this work, we find a recursive expression for the second moment using these graph-theoretic techniques. While we have not been able to solve this recursion by hand, we are able to solve it numerically exactly, which we do up to Fock sector $2n = 80$. We further derive new analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device.

DOI: 10.48550/arxiv.2403.13878

Related papers

Transition of Anticoncentration in Gaussian Boson Sampling

Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande +2 more

arXiv:2312.08433Physical Review LettersApr 8, 20253 citations

Exact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak Anticoncentration

Hongru Zhao

quant-pharXiv:2608.17065Aug 19, 20260 citations

Second moment of Hafnians in Gaussian boson sampling

Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande +2 more

This paper addresses the question of exactly how to tell if Gaussian boson sampling gives a quantum advantage. It complements a joint PRL paper that uses a graph-theoretic method to study the output probabilities of Gaussian boson sampling. In this PRA paper, the authors dive deeper into the formalism and detail a numerical technique based on recursion.

Physical Review AApr 8, 20253 citations

Anticoncentration and entanglement in Gaussian boson sampling

Laura Shou, Adam Ehrenberg, Yu-Xin Wang +2 more

quant-pharXiv:2609.01241Aug 28, 20260 citations

Boson sampling beyond the dilute regime: second moments and anti-concentration

Hela Mhiri, Hugo Thomas, Léo Monbroussou +3 more

quant-pharXiv:2604.14323Apr 17, 20260 citations

General framework for anticoncentration and linear cross-entropy benchmarking in photonic quantum advantage experiments

Zoltán Kolarovszki, Ágoston Kaposi, Zoltán Zimborás +1 more

quant-pharXiv:2604.15258Apr 17, 20260 citations

arXiv:2403.13878

The Second Moment of Hafnians in Gaussian Boson Sampling

Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande, Dominik Hangleiter, Alexey Vyacheslavovich Gorshkov

Published Mar 20, 2024• 0 citations

arXiv HTML PDF

Abstract

2n = 80

. We further derive new analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device.

DOI: 10.48550/arxiv.2403.13878

Related papers

Transition of Anticoncentration in Gaussian Boson Sampling

Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande +2 more

Gaussian boson sampling is a promising method for experimental demonstrations of quantum advantage because it is easier to implement than other comparable schemes. While most of the properties of Gaussian boson sampling are understood to the same degree as for these other schemes, we understand relatively little about the statistical properties of its output distribution. The most relevant statistical property, from the perspective of demonstrating quantum advantage, is the "anticoncentration" of the output distribution as measured by its second moment. The degree of anticoncentration features in arguments for the complexity-theoretic hardness of Gaussian boson sampling. In this Letter, we develop a graph-theoretic framework for analyzing the moments of the Gaussian boson sampling distribution. Using this framework, we show that Gaussian boson sampling undergoes a transition in anticoncentration as a function of the number of modes that are initially squeezed compared to the number of photons measured at the end of the circuit. When the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration. However, if the number of initially squeezed modes scales quickly enough, the output probabilities anticoncentrate weakly.Gaussian boson sampling is a promising method for experimental demonstrations of quantum advantage because it is easier to implement than other comparable schemes. While most of the properties of Gaussian boson sampling are understood to the same degree as for these other schemes, we understand relatively little about the statistical properties of its output distribution. The most relevant statistical property, from the perspective of demonstrating quantum advantage, is the "anticoncentration" of the output distribution as measured by its second moment. The degree of anticoncentration features in arguments for the complexity-theoretic hardness of Gaussian boson sampling. In this Letter, we develop a graph-theoretic framework for analyzing the moments of the Gaussian boson sampling distribution. Using this framework, we show that Gaussian boson sampling undergoes a transition in anticoncentration as a function of the number of modes that are initially squeezed compared to the number of photons measured at the end of the circuit. When the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration. However, if the number of initially squeezed modes scales quickly enough, the output probabilities anticoncentrate weakly.

arXiv:2312.08433Physical Review LettersApr 8, 20253 citations

Exact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak AnticoncentrationExact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak Anticoncentration

Hongru Zhao

Anticoncentration is central to hardness arguments for approximate sampling. In the independent Gaussian surrogate for collision free Gaussian boson sampling, the moment ratio studied here also determines the averaged ideal linear cross entropy reference value. Let $H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)$ , where $X\in\mathbb{C}^{k\times 2n}$ has independent standard circular complex Gaussian entries. We evaluate $\mathbb{E}|H_{k,n}|^2$ and $\mathbb{E}|H_{k,n}|^4$ exactly by reducing four hafnian copies to a rank two Gaussian integral. For $R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4$ , we obtain $R_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}$ , where $F_{k,n}={}3F_2(-n,-n,1/2;1,k/2;1)$ is a terminating generalized hypergeometric polynomial. If $k/n^2\to c>0$ , then $F{k,n}\to e^{1/c}I_0(1/c)$ , where $I_0$ is the modified Bessel function of the first kind of order zero, and consequently $R_{k,n}\sqrt{πn}\to[e^{1/c}I_0(1/c)]^{-1}$ . Thus $k\asymp n^2$ is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is $k\asymp n^2/\log n$ . These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.Anticoncentration is central to hardness arguments for approximate sampling. In the independent Gaussian surrogate for collision free Gaussian boson sampling, the moment ratio studied here also determines the averaged ideal linear cross entropy reference value. Let $H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)$, where $X\in\mathbb{C}^{k\times 2n}$ has independent standard circular complex Gaussian entries. We evaluate $\mathbb{E}|H_{k,n}|^2$ and $\mathbb{E}|H_{k,n}|^4$ exactly by reducing four hafnian copies to a rank two Gaussian integral. For $R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4$, we obtain $R_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}$, where $F_{k,n}={}3F_2(-n,-n,1/2;1,k/2;1)$ is a terminating generalized hypergeometric polynomial. If $k/n^2\to c>0$, then $F{k,n}\to e^{1/c}I_0(1/c)$, where $I_0$ is the modified Bessel function of the first kind of order zero, and consequently $R_{k,n}\sqrt{πn}\to[e^{1/c}I_0(1/c)]^{-1}$. Thus $k\asymp n^2$ is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is $k\asymp n^2/\log n$. These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.

quant-pharXiv:2608.17065Aug 19, 20260 citations

Second moment of Hafnians in Gaussian boson sampling

Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande +2 more

Physical Review AApr 8, 20253 citations

Anticoncentration and entanglement in Gaussian boson sampling

Laura Shou, Adam Ehrenberg, Yu-Xin Wang +2 more

Anticoncentration and entanglement are two properties used to study classical hardness or easiness of Gaussian boson sampling in varying regimes. In this paper, we consider three directions concerning anticoncentration and entanglement in Gaussian boson sampling: (1) We derive closed-form expressions for the second moment of hafnians of symmetric Gaussian products, and use this to precisely locate the anticoncentration transition as a function of the number of squeezed input modes. (2) We derive closed-form expressions for the Rényi- $α$ Page curves for Gaussian boson sampling. (3) We study unequal input squeezing parameters $(s_i)_i$ , and prove estimates as well as monotonicity of the average-case Rényi-2 entropy Page curve in terms of the magnitudes $|s_i|$ , which allow for extending equal squeezing results to unequal squeezing.Anticoncentration and entanglement are two properties used to study classical hardness or easiness of Gaussian boson sampling in varying regimes. In this paper, we consider three directions concerning anticoncentration and entanglement in Gaussian boson sampling: (1) We derive closed-form expressions for the second moment of hafnians of symmetric Gaussian products, and use this to precisely locate the anticoncentration transition as a function of the number of squeezed input modes. (2) We derive closed-form expressions for the Rényi-$α$ Page curves for Gaussian boson sampling. (3) We study unequal input squeezing parameters $(s_i)_i$, and prove estimates as well as monotonicity of the average-case Rényi-2 entropy Page curve in terms of the magnitudes $|s_i|$, which allow for extending equal squeezing results to unequal squeezing.

quant-pharXiv:2609.01241Aug 28, 20260 citations

Boson sampling beyond the dilute regime: second moments and anti-concentration

Hela Mhiri, Hugo Thomas, Léo Monbroussou +3 more

Boson sampling is a leading candidate for demonstrating quantum advantage in photonic systems. Despite significant experimental and theoretical progress, a characterization of its output statistics remains incomplete. This is especially true beyond the dilute regime, where photon collisions and bunching become significant. The associated saturated regime, characterized by mode number growing linearly with photon number, or more generally sub-quadratically, is precisely the regime of greatest experimental interest. As a consequence, anti-concentration of the output distribution--a key ingredient in hardness arguments--remains poorly understood in boson sampling. In this work, we leverage representation-theoretic tools to address this gap, obtaining closed-form expressions for second moments of generic particle-number-preserving bosonic observables. We express these quantities in terms of Hilbert-Schmidt norms of projections onto irreducible components of the operator space and show that these projection norms admit compact analytical expressions by exploiting the underlying symmetry structure. Focusing on Fock state output probabilities, we further establish anti-concentration beyond the dilute regime. Together with recent complexity-theoretic results, our findings strengthen hardness guarantees for boson sampling in experimentally interesting settings.Boson sampling is a leading candidate for demonstrating quantum advantage in photonic systems. Despite significant experimental and theoretical progress, a characterization of its output statistics remains incomplete. This is especially true beyond the dilute regime, where photon collisions and bunching become significant. The associated saturated regime, characterized by mode number growing linearly with photon number, or more generally sub-quadratically, is precisely the regime of greatest experimental interest. As a consequence, anti-concentration of the output distribution--a key ingredient in hardness arguments--remains poorly understood in boson sampling. In this work, we leverage representation-theoretic tools to address this gap, obtaining closed-form expressions for second moments of generic particle-number-preserving bosonic observables. We express these quantities in terms of Hilbert-Schmidt norms of projections onto irreducible components of the operator space and show that these projection norms admit compact analytical expressions by exploiting the underlying symmetry structure. Focusing on Fock state output probabilities, we further establish anti-concentration beyond the dilute regime. Together with recent complexity-theoretic results, our findings strengthen hardness guarantees for boson sampling in experimentally interesting settings.

quant-pharXiv:2604.14323Apr 17, 20260 citations

General framework for anticoncentration and linear cross-entropy benchmarking in photonic quantum advantage experiments

Zoltán Kolarovszki, Ágoston Kaposi, Zoltán Zimborás +1 more

Photonic architectures are one of the leading platforms for demonstrating quantum computational advantage, with Boson Sampling and Gaussian Boson Sampling as the primary schemes. Yet, we lack for these photonic primitives a systematic theoretical understanding of linear cross-entropy benchmarking (LXEB), which is a central tool for testing quantum advantage proposals. In this work, we develop a representation-theoretic framework for the classical computation of average LXEB scores and second moments of output probability distributions, covering a range of quantum advantage experiments based on scattering $n$ -photon states through $m$ -mode Haar-random interferometers. Our methods apply in any regime, including the saturated regime, where the (expected) number of photons is comparable to the number of optical modes. The same second-moment techniques also allow us to prove anticoncentration for traditional Fock-state Boson Sampling in the saturated regime. Interestingly, for Gaussian Boson Sampling second moments are not sufficient to establish a meaningful anticoncentration statement. The technical core of our approach rests on decomposing two copies of the $n$ -particle bosonic space $\mathrm{Sym}^n(\mathbb{C}^m)$ into irreducible representations of $\mathrm{U}(m)$ . This reduces two-copy Haar averages to computing purities of initial states after partial traces over particles, highlighting the role that particle entanglement plays for LXEB and anticoncentration.Photonic architectures are one of the leading platforms for demonstrating quantum computational advantage, with Boson Sampling and Gaussian Boson Sampling as the primary schemes. Yet, we lack for these photonic primitives a systematic theoretical understanding of linear cross-entropy benchmarking (LXEB), which is a central tool for testing quantum advantage proposals. In this work, we develop a representation-theoretic framework for the classical computation of average LXEB scores and second moments of output probability distributions, covering a range of quantum advantage experiments based on scattering $n$-photon states through $m$-mode Haar-random interferometers. Our methods apply in any regime, including the saturated regime, where the (expected) number of photons is comparable to the number of optical modes. The same second-moment techniques also allow us to prove anticoncentration for traditional Fock-state Boson Sampling in the saturated regime. Interestingly, for Gaussian Boson Sampling second moments are not sufficient to establish a meaningful anticoncentration statement. The technical core of our approach rests on decomposing two copies of the $n$-particle bosonic space $\mathrm{Sym}^n(\mathbb{C}^m)$ into irreducible representations of $\mathrm{U}(m)$. This reduces two-copy Haar averages to computing purities of initial states after partial traces over particles, highlighting the role that particle entanglement plays for LXEB and anticoncentration.

quant-pharXiv:2604.15258Apr 17, 20260 citations

2n = 80

Exact Moments of Gaussian Gram Hafnians Reveal an

n^2/\log n

Threshold for Weak Anticoncentration

H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)

, where

X\in\mathbb{C}^{k\times 2n}

has independent standard circular complex Gaussian entries. We evaluate

\mathbb{E}|H_{k,n}|^2

and

\mathbb{E}|H_{k,n}|^4

exactly by reducing four hafnian copies to a rank two Gaussian integral. For

R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4

, we obtain

R_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}

, where

F_{k,n}={}3F_2(-n,-n,1/2;1,k/2;1)

is a terminating generalized hypergeometric polynomial. If

k/n^2\to c>0

, then

F{k,n}\to e^{1/c}I_0(1/c)

, where

I_0

is the modified Bessel function of the first kind of order zero, and consequently

R_{k,n}\sqrt{πn}\to[e^{1/c}I_0(1/c)]^{-1}

. Thus

k\asymp n^2

is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is

k\asymp n^2/\log n

. These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.

α

Page curves for Gaussian boson sampling. (3) We study unequal input squeezing parameters

(s_i)_i

, and prove estimates as well as monotonicity of the average-case Rényi-2 entropy Page curve in terms of the magnitudes

|s_i|

, which allow for extending equal squeezing results to unequal squeezing.

n

-photon states through

m

-mode Haar-random interferometers. Our methods apply in any regime, including the saturated regime, where the (expected) number of photons is comparable to the number of optical modes. The same second-moment techniques also allow us to prove anticoncentration for traditional Fock-state Boson Sampling in the saturated regime. Interestingly, for Gaussian Boson Sampling second moments are not sufficient to establish a meaningful anticoncentration statement. The technical core of our approach rests on decomposing two copies of the

n

-particle bosonic space

\mathrm{Sym}^n(\mathbb{C}^m)

into irreducible representations of

\mathrm{U}(m)

. This reduces two-copy Haar averages to computing purities of initial states after partial traces over particles, highlighting the role that particle entanglement plays for LXEB and anticoncentration.