Permanent-of-Gaussians Conjecture
- Field
- Topics
Problem
Is the following Gaussian permanent estimation task \(\#\mathrm P\)-hard under randomized polynomial-time oracle reductions? For \(n\geq1\), let \(X\in\mathbb C^{n\times n}\) have independent entries with density \(\pi^{-1}e^{-|z|^2}\). Given \(0<\epsilon,\delta<1\), output \(z(X)\in\mathbb C\) satisfying
Here \(S_n\) is the set of permutations of \(\{1,\ldots,n\}\). Probability in Eq. (1) includes the matrix and the estimator’s randomness. Cost is measured in the binary input length, \(1/\epsilon\), and \(1/\delta\). Use a binary truncation precise enough to alter the target by at most \(\epsilon|\operatorname{Per}X|/2\) except with probability \(\delta/2\). Polynomially many bits in \(n,\log(1/\epsilon),\log(1/\delta)\) per entry suffice.
Equivalently, ask for the same hardness of additive squared-permanent estimation:
For Eq. (2), use a rounded, truncated matrix whose squared permanent differs from the original by at most \(\epsilon n!/2\) except with probability \(\delta/2\). The input precision and reduction cost obey the same polynomial bounds. Here \(\#\mathrm P\) counts accepting paths of nondeterministic polynomial-time machines.
Source
Aaronson and Arkhipov state the multiplicative Permanent-of-Gaussians Conjecture as Conjecture 5 in arXiv Section 1.2.3. Their Theorem 3 uses the additive squared-permanent task, and Theorem 7 relates the two under permanent anticoncentration [AA13]. The finite-precision convention makes the binary input model explicit.
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].
Koehler and Leung’s July 2026 preprint proves permanent anticoncentration for both real and complex Gaussian matrices (Theorem 1.1) [KL26]. Together with Aaronson–Arkhipov Theorem 7, it establishes polynomial-time equivalence of Eqs. (1) and (2) [AA13]. The binary-rounding convention follows from Gaussian tail bounds, polynomial continuity, and the lower-tail estimate. Anticoncentration does not itself prove counting hardness.
Koehler–Leung Theorem 4.1 also proves Bouland et al.’s Conjecture 6 on gently perturbed Gaussian permanents, with arbitrary deterministic shifts and, more generally, arbitrary independent random perturbations. This removes the perturbation-size and bounded-matrix restrictions in that conjecture. It supplies anticoncentration, not the complex-Gaussian counting-hardness conclusion asked for here [KL26], [BDFH25].
Comment
The complex-Gaussian hardness conjecture remains open. Its additive squared-permanent formulation is represented by Eq. (2) in this same canonical record. The equivalence now uses the resolving anticoncentration preprint of Koehler and Leung, rather than an unproved hypothesis [KL26].
The 2025 tolerance \(n!e^{-O(n^\gamma)}\) applies to real Gaussian matrices and falls short of \(n!/\operatorname{poly}(n)\). The real anticoncentration assumption in that theorem is supplied by the 2026 preprint. Its result still uses \(\mathrm{BPP}^{\mathrm{NP}}\) reductions and does not prove the complex-Gaussian conjecture. Bouland et al., Appendix E, leave the required complex square-method argument unproved [BDFH25].