Permanent-of-Gaussians Conjecture
- Field
- Topics
Problem
Is the following estimation task \(\#\mathrm{P}\)-hard under randomized polynomial-time Turing reductions? Given \(X\in\mathbb{C}^{n\times n}\) with independent entries \(X_{ij}=(a_{ij}+ib_{ij})/\sqrt{2}\), where all \(a_{ij},b_{ij}\sim\mathcal{N}(0,1)\) independently, and \(\epsilon,\delta\in(0,1)\), output \(z(X)\in\mathbb{C}\) satisfying
Here \(S_n\) is the set of permutations of \(\{1,\ldots,n\}\). The guarantee in Eq. (1) is required for arbitrary \(\epsilon,\delta\), with running time measured in \(n,1/\epsilon,1/\delta\).
Source
Aaronson and Arkhipov’s Permanent-of-Gaussians Conjecture: Conjecture 5 and the preceding definition of \(\mathrm{GPE}_{\times}\) in arXiv:1011.3245, Section 1.2.3 (2010 preprint; published 2013) [AA13]. The original task approximates the complex permanent itself with relative error.
Progress
2010–2013: Aaronson–Arkhipov prove exact Gaussian-permanent \(\#\mathrm{P}\)-hardness at success fraction \(3/4+1/\operatorname{poly}(n)\), and hardness for estimating \(|\operatorname{Per}(X)|^2\) with exponentially small additive error (arXiv Theorems 60 and 62) [AA13].
2021: Bouland–Fefferman–Landau–Liu obtain additive tolerance \(e^{-4n\log n-O(n)}\) for \(|\operatorname{Per}(X)|^2\), with any constant failure probability below \(1/4\), using \(\mathrm{BPP}^{\mathrm{NP}}\) reductions (proof of Corollary 1) [BFLL22].
2023 (unpublished): Krovi’s tighter total-variation estimate improves this tolerance to \(e^{-2n\log n-O(n)}\), as reported and explained by Bouland et al. (Section 1.2.1) [BDFH25].
2025 (real ensemble): for \(R\sim\mathcal{N}(0,1)^{n\times n}\), Bouland et al. prove \(\#\mathrm{P}\)-hardness at additive error \(n!e^{-O(n^\gamma)}\) for \(|\operatorname{Per}(R)|^2\), for every fixed \(\gamma>0\), with constant success probability, assuming permanent anticoncentration (Theorem 1, Section 4; \(\mathrm{BPP}^{\mathrm{NP}}\) reduction) [BDFH25].
Comment
The complex-Gaussian conjecture remains open. Its squared-permanent counterpart has additive-error target \(\epsilon n!\), equivalent under permanent anticoncentration (arXiv Theorem 7) [AA13]. Koehler–Leung’s July 2026 preprint proves this auxiliary conjecture (Theorem 1.1) [KL26].
The 2025 tolerance \(n!e^{-O(n^\gamma)}\) is for real Gaussian matrices \(R\), and still falls short of \(n!/\operatorname{poly}(n)\) in that ensemble. It is not a hardness bound for the complex \(X\) in the Problem. Appendix E leaves the complex square-method argument unproved [BDFH25]; the anticoncentration result does not supply that separate missing argument.