Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling

• URL: http://arxiv.org/abs/2607.22088v1
• Date: Fri, 24 Jul 2026 08:35:27 GMT
• Title: Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling
• Abstract summary: boson sampling involves sampling from the output distribution of a linear optical network.<n>We show that the typical magnitude of a random Gaussian permanent is on par with Tao and Vu's seminal result for Bernoulli matrices.<n>Our result implies that classically boson sampling to within a superexponentially small total variation distance would collapse the hierarchy.
• Score: 9.33606630554665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.

Related papers

• Analytic Cancellation of Interference Terms and Closed-Form 1-Mode Marginals in Canonical Boson Sampling [4.653967722732359]
  We provide a direct, bottom-up derivation of the exact 1-mode marginal distribution in CBS, computable in $mathcalORR time.<n>We explicitly bridge this physical derivation with the mathematical theory of rank-1 matrixs, proving that multiphoton interference reduces to a symmetric scaled by a factorialic bunching factor.
  arXiv  Detail & Related papers  (2026-03-01T04:26:35Z)
• Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination [40.15176310729312]
  We study the basic task of mean estimation in the presence of mean-shift contamination.<n>We show that there exists a sample-efficient algorithm that estimates the target mean to any desired accuracy.
  arXiv  Detail & Related papers  (2026-02-25T17:21:23Z)
• The symplectic rank of non-Gaussian quantum states [0.0]
  Non-Gaussianity is a key resource for achieving quantum advantages in bosonic platforms.<n>Here, we investigate the symplectic rank: a novel non-Gaussianity monotone that satisfies remarkable operational and resource-theoretic properties.<n>We show that the symplectic rank is a robust non-Gaussian measure, explaining how to witness it in experiments and how to exploit it to meaningfully benchmark different bosonic platforms.
  arXiv  Detail & Related papers  (2025-04-27T18:00:31Z)
• Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations [29.212403229351253]
  We analyze a complex variant of the Gaussian mechanism and obtain upper bounds on the Frobenius norm of the difference between the matrix output by this mechanism and the best rank-$k$ approximation to $M$.<n>We show that the eigenvalues of the matrix $M$ perturbed by Gaussian noise have large gaps with high probability.
  arXiv  Detail & Related papers  (2025-02-11T15:46:03Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains [11.3631620309434]
  We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real alpha, we prove that the empirical distribution of the process converges almost surely to the the target (
  arXiv  Detail & Related papers  (2023-05-08T23:59:09Z)
• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods [35.24886589614034]
  We consider quadratic definite Ising models on the hypercube with a general interaction $J$. Our general result implies the first time sampling algorithms for low-rank Ising models.
  arXiv  Detail & Related papers  (2022-02-17T21:43:50Z)
• The Complexity of Bipartite Gaussian Boson Sampling [0.0]
  We show that under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient algorithm to sample from ideal GBS unless the hierarchy collapses. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons.
  arXiv  Detail & Related papers  (2021-10-13T18:08:37Z)
• A Random Matrix Perspective on Random Tensors [40.89521598604993]
  We study the spectra of random matrices arising from contractions of a given random tensor. Our technique yields a hitherto unknown characterization of the local maximum of the ML problem. Our approach is versatile and can be extended to other models, such as asymmetric, non-Gaussian and higher-order ones.
  arXiv  Detail & Related papers  (2021-08-02T10:42:22Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.