The Permanent-of-Gaussians Conjecture

In BosonSampling, photons pass through a random linear-optical network, and each output pattern occurs with probability given by the squared permanent of a submatrix that is close to a matrix of independent Gaussians. Aaronson and Arkhipov showed that a fast classical simulation of this experiment would collapse the polynomial hierarchy, provided that approximating such permanents is #P-hard for most Gaussian matrices. That missing step is the Permanent-of-Gaussians Conjecture.

Problem

Let $X$ be an $n\times n$ matrix of independent standard complex Gaussian entries, each with density $\pi^{-1}e^{-|z|^2}$, and let

$$\operatorname{Per}X=\sum_{\sigma\in S_n}\prod_{j=1}^{n}X_{j,\sigma(j)} .$$

Gaussian Permanent Estimation, $\mathrm{GPE}_\times$, asks: given $X$ and $\varepsilon,\delta>0$, output $z$ with $|z-\operatorname{Per}X|\le\varepsilon\,|\operatorname{Per}X|$, with probability at least $1-\delta$ over $X$, in time $\mathrm{poly}(n,1/\varepsilon,1/\delta)$.

Conjecture. $\mathrm{GPE}_\times$ is $\#\mathsf{P}$-hard: if an oracle $\mathcal{O}$ solves it, then $\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}$.

The additive version $|\mathrm{GPE}|^2_\pm$ asks instead for $|\operatorname{Per}X|^2$ to within $\pm\varepsilon\, n!$, under the same conditions [1].

Background

Aaronson and Arkhipov stated the conjecture in 2010 as the main complexity-theoretic challenge of their work on linear optics [1]. They proved that a classical algorithm sampling approximately from the BosonSampling distribution in polynomial time would put $|\mathrm{GPE}|^2_\pm$ in $\mathsf{BPP}^{\mathsf{NP}}$. Under a second conjecture, permanent anticoncentration ($|\operatorname{Per}X|\ge\sqrt{n!}/\mathrm{poly}(n,1/\delta)$ except with probability $\delta$), the two versions are polynomial-time equivalent, and the conjecture above would then give $\mathsf{P}^{\#\mathsf{P}}=\mathsf{BPP}^{\mathsf{NP}}$, collapsing the polynomial hierarchy to its third level [1]. This argument underlies the complexity-theoretic case for quantum advantage in BosonSampling experiments [1, 3].

What is known

• Exact computation is hard on average: by extending Lipton's random self-reducibility of the permanent, computing $\operatorname{Per}X$ exactly for a $3/4+1/\mathrm{poly}(n)$ fraction of Gaussian matrices is $\#\mathsf{P}$-hard, and so is estimating $|\operatorname{Per}X|^2$ to within exponentially small additive error [1]. Aaronson and Arkhipov expected that $3/4$ could be lowered to $1/2+1/\mathrm{poly}(n)$ or $1/\mathrm{poly}(n)$, as over finite fields, and left this for future work [1].
• Error tolerance, measured as additive error on the output probabilities of random $n$-photon experiments: $\#\mathsf{P}$-hardness was shown for error $e^{-O(n^4)}$ by Aaronson and Arkhipov [1, 3], then $e^{-6n\log n-O(n)}$ by Bouland, Fefferman, Landau and Liu [2], and in 2025 $e^{-n\log n-n-O(n^\delta)}$ for every $\delta>0$ by Bouland, Datta, Fefferman and Hernández, under $\mathsf{BPP}^{\mathsf{NP}}$ reductions and assuming anticoncentration [3]. The conjecture corresponds to error $e^{-n\log n-n-O(\log n)}$ [3].
• A July 2026 preprint by Koehler and Leung reports a proof of the permanent anticoncentration conjecture of [1] for complex Gaussian matrices, with analogues for real and quaternionic ones; it has not yet been refereed [4]. If it holds, then by [1] the additive and multiplicative versions are equivalent, and the anticoncentration assumption in [3] is no longer needed; it does not by itself give $\#\mathsf{P}$-hardness.

What would count as progress

• Improving the $O(n^\delta)$ term in the exponent of [3] to $O(\log n)$, which [3] identifies as the remaining step toward the conjecture.
• An independent check, or a simpler proof, of the anticoncentration theorem of [4], on which the equivalence of the two versions now rests.

References

1. S. Aaronson and A. Arkhipov, "The computational complexity of linear optics", Theory of Computing 9(4), 143–252 (2013). doi:10.4086/toc.2013.v009a004
2. A. Bouland, B. Fefferman, Z. Landau and Y. Liu, "Noise and the frontier of quantum supremacy", in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 1308–1317 (2022). doi:10.1109/FOCS52979.2021.00127
3. A. Bouland, I. Datta, B. Fefferman and F. Hernández, "Exponential improvements to the average-case hardness of BosonSampling", in 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), 912–933 (2025). doi:10.1109/FOCS63196.2025.00047
4. F. Koehler and P. K. Leung, "Anticoncentration of the permanent in Ginibre ensembles", preprint (2026). arXiv:2607.20329

Source

Imported from QIQCOP Zoo op_af68b033a88ef934, curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.