Pith. sign in

REVIEW 4 major objections 4 minor 54 references

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

T0 review · 4 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves a weak permanent anti-concentration bound for random complex Gaussian matrices: a Gaussian permanent is superexponentially small only with polynomially decaying probability.

desk verdict The paper's weak anti-concentration bound for Gaussian permanents is new and the proof is essentially sound; the reviewer's key objection about Lemma 11 does not survive contact with the manuscript. read the letter →

arxiv 2607.22088 v1 pith:V6MF4FHO submitted 2026-07-24 quant-ph

Fei Meng , Bin Cheng , Jianan Li , Man-Hong Yung This is my paper · ORCID
classification quant-ph MSC 15B5260B2068Q17
keywords permanentanti-concentrationcomplexGaussianmatrixrandombosonsamplingtypicalmagnitudeestimationconjectureMcDiarmidinequality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to prove a weak version of the permanent anti-concentration conjecture for random complex Gaussian matrices: for every α>0, the probability that |Per(M)| falls below sqrt(n!)/n^{αn} is at most O(1/n^c) for a fixed c>0. That is, a Gaussian permanent is rarely superexponentially smaller than its standard deviation. A direct corollary is the first typical-magnitude statement for this distribution: |Per(M)| = n^{(1/2+o(1))n} asymptotically almost surely. The result matters because boson-sampling hardness rests on anti-concentration plus an average-case hardness conjecture; this bound moves the Gaussian case from open to a polynomially decaying weak form, while the full conjecture would follow if the denominator were tightened to a polynomial. The proof adapts the row-exposure framework for discrete random matrices to continuous Gaussian entries, replacing discrete Littlewood-Offord tools with Gaussian anti-concentration and rotation-invariance arguments.

What carries the argument

The engine is row-exposure induction over minors of M. A minor M_A is λ-heavy if |Per(M_A)| ≥ λ. Lemma 7 gives the key local identity: by cofactor expansion, a newly exposed Gaussian row makes Per(M_{A∪{i}}) a complex Gaussian with variance at least |Per(M_A)|^2, so its modulus dominates the parent's with probability at least 1/e. Around this, the paper assembles (i) a Gaussian Littlewood-Offord-type bound controlling linear combinations a1 v1 + ... + am vm (Lemma 3), (ii) a first-moment lemma for many possibly dependent events, (iii) a supermartingale potential argument that forces either the count of heavy minors N or the threshold λ to grow at each of roughly (1−ε)n row-exposure steps, an

What would settle it

Instantiate the Lemma 11 construction for moderately large n: pick a column h_l from the set of added columns and vary the single entry a_{n-j+1,h_l} by a unit amount while holding all other entries fixed. Count how many of the N ≈ n^{0.5} quantities Y_i change; the proof requires this count ≤ 3T ≈ O(n^{0.1}), while direct inspection with h_l ∈ A_i for every i ≠ l gives a count about N. Alternatively, Monte-Carlo estimate Pr(|Per(M)| < sqrt(n!)/n^{αn}) for n=20,30,40; if the tail does not decay like 1/n^c, the theorem is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for M ~ G^{n×n} i.i.d. standard complex Gaussian entries, there is a constant c>0 with Pr(|Per(M)| < sqrt(n!)/n^{αn}) = O(1/n^c) for every α>0 once n is large. Because sqrt(n!) = n^{(1/2+o(1))n}, this yields Corollary 1: asymptotically almost surely |Per(M)| = n^{(1/2+o(1))n}. The proof obtains this by exposing rows one at a time and tracking minors whose permanents stay above a threshold. The elementary step is cofactor expansion: when a new row is added, the child minor is a complex Gaussian whose variance is at least the parent permanent squared, and rotational symmetry gives at least probability 1/e that the child's permanent dominates the parent's. A grow

Load-bearing premise

The argument collapses if the endgame's McDiarmid step is wrong: the proof needs every single Gaussian matrix entry to affect only O(n^{0.1}) of the tracked quantities, but under the paper's own construction of child minors with disjoint complements, one entry sits in nearly all of those minors and can affect O(n^{0.5}) of them. The anti-concentration theorem is only as solid as that bounded-difference assertion.

Editorial extensions

If this is right

  • Gaussian permanents have typical magnitude n^{(1/2+o(1))n} asymptotically almost surely, matching the known discrete-random-matrix picture.
  • If the remaining average-case hardness conjecture holds, classical simulation of boson sampling to total variation distance O(1/n^{2αn}) would put #P in BPP^NP and collapse the polynomial hierarchy.
  • The superexponential denominator n^{αn} is still far from the polynomial denominator required by the full permanent anti-concentration conjecture; closing that gap is now explicitly the remaining mathematical barrier.
  • For random linear-optical networks with far more modes than photons, transition amplitudes scale as n^{(1/2+o(1))n}/m^{n/2} with high probability, consistent with random-walk addition of n! paths.
  • The proof establishes that row-exposure methods transfer from discrete entry distributions to continuous, unbounded Gaussian entries, widening the class of random matrix ensembles for which anti-concentration-type conclusions are available.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the endgame concentration step can be replaced by a correct Lipschitz estimate respecting the actual dependency graph of the tracked Y_i variables, the same three-phase structure may prove anti-concentration directly for submatrices of Haar-random unitaries, bypassing the Gaussian approximation and covering arbitrary m/n ratios.
  • A natural testable extension is numerical: for n=20–50, directly estimate Pr(|Per(M)| < sqrt(n!)/n^{αn}) by Monte Carlo; a decay consistent with 1/n^c would corroborate Theorem 1, while a slower or flat tail would indicate the bound needs stronger machinery.
  • The n^{logn} endgame loss looks like an intrinsic limit of row-exposure, so combining this framework with high-moment methods may be the most direct route to the full anti-concentration conjecture, though the paper leaves that combination open.
  • The permanent's typical magnitude being n^{(1/2+o(1))n} gives a quantitative normalization for heuristic comparisons of ideal and noisy boson sampling, since output probabilities will concentrate around this scale.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proves a weak permanent anti-concentration bound for n×n complex Gaussian matrices: for every α>0, the probability that |Per(M)| < √n!/n^{αn} is O(n^{-c}) for a constant c>0. It then derives that |Per(M)| = n^{(1/2+o(1))n} asymptotically almost surely, which is the first typical-magnitude result for complex Gaussian permanents, and discusses a conditional hardness implication for boson sampling under the Permanent-of-Gaussians Conjecture and non-collapse of PH. The proof adapts Tao and Vu's row-exposure framework to Gaussian entries, replacing discrete Littlewood-Offord with a Gaussian linear-combination bound, replacing a discrete one-step growth lemma with a rotational-symmetry argument, and replacing Azuma's inequality by McDiarmid's inequality in the endgame.

Significance. If the proof is made fully rigorous, the main theorem is a genuine advance: it supplies a superexponentially small lower-tail bound for complex Gaussian permanents and the first typical-magnitude result of Tao-Vu type for the Gaussian distribution relevant to boson sampling. It does not prove the full PACC, but it gives a concrete quantitative weakening that is directly usable in the Aaronson-Arkhipov hardness framework. The paper also gives an explicit conditional hardness corollary, though the corollary depends on external conjectures (Permanent-of-Gaussians, non-collapse of PH). The mathematical contribution is distributional and probabilistic; no numerical or code verification is provided, but the proof is intended to be self-contained except for the imported Tao-Vu endgame lemmas.

major comments (4)
  1. [Appendix B, Lemma 8 and Lemma 9] The stated independence is not correct as written. In Lemma 9, the indicators X_j for different j are not independent under conditioning on M^{(k)} only, because Per(A∪{i_j}) contains the common row entries a_{k+1,l} for l∈A. For example, with A={1}, k=1, I={2,3}, X_2 and X_3 both depend on a_{2,1}. The lemma can be repaired by conditioning also on {a_{k+1,l}: l∈A}; Lemma 7 holds for arbitrary fixed B, so the X_j become independent Bernoulli variables with success probability at least 1/e, yielding the stated Chernoff bound unconditionally. The same conditioning is needed in Lemma 8's proof of Pr(ν=0) ≤ η^{-|I|}. As written, the proof of these lemmas is invalid, and they are load-bearing for Step 1 and for Propositions 4 and 5.
  2. [Appendix C, Lemma 11, Eq. (66)] The sentence "at most 2T indices i∈I′ satisfy h∈B_i" is false under complement-disjointness: for h = h_l, every B_i (i∈I′) contains h_l, because h_l ∈ A_i for all i≠l. However, the intended Lipschitz bound can be recovered by replacing this statement with the correct claim: at most 2T indices have B_i−{h} λ′/n²-heavy. Since light coefficients contribute at most 2/n each and |I′|≤N≤n, the total change is ≤2T·1+n·(2/n)=2T+2≤3T. Thus the McDiarmid constant is valid, but the text's justification is wrong and needs to be corrected. This is not a fatal flaw, but it is a load-bearing misstatement that must be fixed.
  3. [Proposition 9 and Eq. (69)] The claimed endgame loss n^{−log n} is not what the iteration proves. Each application of Lemma 11 multiplies λ′ by n^{−2}; with L=⌊(1/100)log n⌋ iterations, the total loss is n^{−2L}=n^{−0.02 log n}, not n^{−log n}. This weaker bound still suffices for Theorem 1 because n^{−0.02 log n}=n^{−o(n)}, but Proposition 9 and the chaining in Section IV (Step 3) and in the proof of Theorem 1 must be restated with n^{−2L} instead of n^{−log n}. As written, the proposition claims a stronger result than the proof establishes.
  4. [Propositions 4–5 and Step 2 algorithm] Propositions 4 and 5 are stated for N≥1, but in the Step 2 algorithm the parameter N_k can drop below 1 after Type II, III, or IV steps (e.g., N_{k+1}=ϵN_k/6). The text permits real N with the convention that E_{k,N,λ} means at least ⌈N⌉ minors, but the proofs of Propositions 4 and 5 use "there exist N λ-heavy minors," which is not meaningful for N<1. This is fixable by replacing N with max(N,1) whenever the propositions are applied, but as written the induction has a bookkeeping gap in a load-bearing part of the growth phase.
minor comments (4)
  1. [Appendix C, after Eq. (66)] The McDiarmid application is made conditionally on the event C={∀l, |x_l|≤n}, and the Lipschitz bound is only proved on C. For full rigor, the proof should apply McDiarmid to the conditional expectation E[Y|C] and then transfer the bound to E[Y] using Pr(C^c)=o(1). As written, the use of the unconditional E[Y] after conditioning is implicit and should be stated.
  2. [Theorem 1 statement] The phrase "there exists a constant c>0 such that for all α>0" suggests c is independent of α. The proof's failure probabilities in the growth phase depend on ϵ and ϵ′, which are chosen from α. The statement should clarify whether c is uniform or may depend on α, and the proof should justify the chosen quantifier order.
  3. [Section V] The closing discussion says the endgame "inherently loses a factor of n^{log n}"; with L=0.01 log n the actual loss in the proof is n^{0.02 log n}. Update the discussion to match the corrected endgame statement.
  4. [Throughout] There are several small formulation issues: "Ehrenberg el al." should be "Ehrenberg et al."; the N≥1/non-integer N convention in E_{k,N,λ} should be stated once with the ceiling convention; and Eq. (62) writes 1−exp(−Ω(L))=1−n^{−Ω(1)}, which is correct but could be clarified once L∼log n.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof adapts external Tao–Vu machinery to Gaussian entries and states all hardness implications as conditional on explicit conjectures.

full rationale

The paper's central theorem (Theorem 1) is derived by a row-exposure argument over i.i.d. complex Gaussian entries, with no fitted parameters and no quantity defined in terms of the target bound. The proof imports Tao–Vu's structural lemmas (e.g., Lemma 10 and the first-moment lemma) as external mathematical results, and replaces distribution-dependent tools with Gaussian analogues (Lemmas 3, 5, 7). These are genuine external inputs, not restatements of the conclusion. The hardness application in Section III-A is explicitly conditional on the Permanent-of-Gaussians Conjecture and the non-collapse of the polynomial hierarchy, which are stated as assumptions rather than derived. The one self-citation involving a coauthor, [26] (Bremner, Cheng, Ji), appears only in a background list of sampling models and is not load-bearing. No equation reduces to its own input by construction, and no fitted value is relabeled as a prediction. The alleged McDiarmid flaw in Lemma 11, if valid, would be a mathematical correctness issue, not a circularity issue. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central theorem rests on standard Gaussian and concentration inequalities, plus Tao–Vu's endgame lemmas imported without proof. The hardness corollary adds the permanent-of-Gaussians conjecture and non-collapse of PH. No new entities or fitted parameters are introduced.

assumptions (5)
  • standard math Sum of independent complex Gaussians with deterministic coefficients is CN(0, sum |v_i|^2) (used in Lemma 3).
    Section A, Lemma 3 proof. This is the defining stability property of Gaussian distributions.
  • standard math Cofactor expansion of the permanent (Eq. 13) and rotational symmetry of complex Gaussians.
    Section IV and Lemma 7. These are standard algebraic and distributional facts.
  • domain assumption Tao–Vu endgame lemmas (Lemma 10 and Corollary 2) providing many complement-disjoint heavy minors.
    Appendix C, Lemma 10 and Corollary 2 are imported from Ref. [45] without proof. They are distribution-independent but not standard background; the paper relies on them as established results.
  • domain assumption Submatrices of Haar-random unitaries are approximately i.i.d. complex Gaussian (AA Theorem 35).
    Used in the introduction and Section V to connect the Gaussian permanent result to boson sampling transition amplitudes.
  • domain assumption Permanent-of-Gaussians Conjecture and non-collapse of the polynomial hierarchy.
    Section III-A: the hardness corollary is explicitly conditional on these conjectures, which are unproven.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling." pith.science (2026). https://pith.science/paper/V6MF4FHO

@misc{pith2026260722088,
  author       = {Pith},
  title        = {Pith review of: Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V6MF4FHO}},
  note         = {Machine review of arXiv:2607.22088}
}
read the original 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 2 canonical work pages

  1. [1]

    Quantum computational advantage via 60-qubit 24-cycle random circuit sampling,

    Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y . Du, D. Fan, M. Gonget al., “Quantum computational advantage via 60-qubit 24-cycle random circuit sampling,”Sci. Bull., vol. 67, no. 3, pp. 240–245, 2022

    2022

  2. [2]

    Quantum computa- tional advantage via high-dimensional Gaussian boson sampling,

    A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioan- nou, L. Madsen, J. Lavoie, H. Qi, J. Eisertet al., “Quantum computa- tional advantage via high-dimensional Gaussian boson sampling,”Sci. Adv., vol. 8, no. 1, p. eabi7894, 2022

    2022

  3. [3]

    Quantum computational advantage with a programmable photonic processor,

    L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collinset al., “Quantum computational advantage with a programmable photonic processor,”Nature, vol. 606, no. 7912, pp. 75–81, 2022

    2022

  4. [4]

    Strong quantum computational advantage using a superconducting quantum processor,

    Y . Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y . Du, D. Fanet al., “Strong quantum computational advantage using a superconducting quantum processor,”Phys. Rev. Lett., vol. 127, no. 18, p. 180501, 2021

    2021

  5. [5]

    Quantum computational advantage using photons,

    H.-S. Zhong, H. Wang, Y .-H. Deng, M.-C. Chen, L.-C. Peng, Y .-H. Luo, J. Qin, D. Wu, X. Ding, Y . Huet al., “Quantum computational advantage using photons,”Science, vol. 370, no. 6523, pp. 1460–1463, 2020

    2020

  6. [6]

    Quantum supremacy using a programmable superconducting processor,

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buellet al., “Quantum supremacy using a programmable superconducting processor,”Nature, vol. 574, no. 7779, pp. 505–510, 2019

    2019

  7. [7]

    Characterizing quantum supremacy in near-term devices,

    S. Boixo, S. V . Isakov, V . N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, “Characterizing quantum supremacy in near-term devices,”Nat. Phys., vol. 14, no. 6, pp. 595–600, 2018

    2018

  8. [8]

    Quantum sampling problems, BosonSampling and quantum supremacy,

    A. P. Lund, M. J. Bremner, and T. C. Ralph, “Quantum sampling problems, BosonSampling and quantum supremacy,”npj Quantum Inf., vol. 3, no. 1, p. 15, 2017

    2017

Show all 54 references
  1. [9]

    Quantum supremacy, here we come,

    B. M. Terhal, “Quantum supremacy, here we come,”Nat. Phys., vol. 14, no. 6, pp. 530–531, 2018

    2018

  2. [10]

    Establishing the quantum supremacy frontier with a 281 pflop/s simulation,

    B. Villalonga, D. Lyakh, S. Boixo, H. Neven, T. S. Humble, R. Biswas, E. G. Rieffel, A. Ho, and S. Mandr `a, “Establishing the quantum supremacy frontier with a 281 pflop/s simulation,”Quantum Sci. Tech- nol., vol. 5, no. 3, p. 034003, 2020

    2020

  3. [11]

    Quantum computational supremacy,

    A. W. Harrow and A. Montanaro, “Quantum computational supremacy,” Nature, vol. 549, no. 7671, pp. 203–209, 2017

    2017

  4. [12]

    Computational advantage of quantum random sampling,

    D. Hangleiter and J. Eisert, “Computational advantage of quantum random sampling,”Rev. Mod. Phys., vol. 95, no. 3, p. 035001, 2023

    2023

  5. [13]

    The computational complexity of linear optics,

    S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,”Theory Comput., vol. 9, no. 1, pp. 143–252, 2013. [Online]. Available: http://www.theoryofcomputing.org/articles/v009a004

    2013

  6. [14]

    Experimental boson sampling,

    M. Tillmann, B. Daki ´c, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,”Nat. Photon., vol. 7, no. 7, pp. 540–544, 2013

    2013

  7. [15]

    Gaussian boson sampling,

    C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, “Gaussian boson sampling,”Phys. Rev. Lett., vol. 119, no. 17, p. 170501, 2017

    2017

  8. [16]

    Photonic implementation of boson sampling: a review,

    D. J. Brod, E. F. Galv ˜ao, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino, “Photonic implementation of boson sampling: a review,” Adv. Photon., vol. 1, no. 3, pp. 034 001–034 001, 2019

    2019

  9. [17]

    Boson sampling on a photonic chip,

    J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys et al., “Boson sampling on a photonic chip,”Science, vol. 339, no. 6121, pp. 798–801, 2013

    2013

  10. [18]

    High-efficiency multiphoton boson sampling,

    H. Wang, Y . He, Y .-H. Li, Z.-E. Su, B. Li, H.-L. Huang, X. Ding, M.-C. Chen, C. Liu, J. Qinet al., “High-efficiency multiphoton boson sampling,”Nat. Photon., vol. 11, no. 6, pp. 361–365, 2017

    2017

  11. [19]

    Boson sampling from a Gaussian state,

    A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,”Phys. Rev. Lett., vol. 113, no. 10, p. 100502, 2014

    2014

  12. [20]

    Experimental scattershot boson sampling,

    M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galv ˜ao, A. Crespiet al., “Experimental scattershot boson sampling,”Sci. Adv., vol. 1, no. 3, p. e1400255, 2015

    2015

  13. [21]

    An introduction to boson-sampling,

    B. T. Gard, K. R. Motes, J. P. Olson, P. P. Rohde, and J. P. Dowling, “An introduction to boson-sampling,” inFrom atomic to mesoscale: The role of quantum coherence in systems of various complexities. World Scientific, 2015, pp. 167–192

    2015

  14. [22]

    Temporally unstructured quantum computation,

    D. Shepherd and M. J. Bremner, “Temporally unstructured quantum computation,”Proc. R. Soc. A, vol. 465, no. 2105, pp. 1413– 1439, May 2009, arXiv: 0809.0847. [Online]. Available: https: //doi.org/10.1098/rspa.2008.0443

    2009 arXiv

  15. [23]

    Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,

    M. J. Bremner, R. Jozsa, and D. J. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,”Proc. R. Soc. A, vol. 467, no. 2126, pp. 459–472, 2011

    2011

  16. [24]

    Average-case complexity versus approximate simulation of commuting quantum computations,

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-case complexity versus approximate simulation of commuting quantum computations,”Phys. Rev. Lett., vol. 117, no. 8, p. 080501, Aug

  17. [25]

    Achieving quantum supremacy with sparse and noisy commuting quantum computations,

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Achieving quantum supremacy with sparse and noisy commuting quantum computations,” Quantum, vol. 1, p. 8, Apr. 2017, arXiv: 1610.01808. [Online]. Available: http://arxiv.org/abs/1610.01808

    2017 arXiv

  18. [26]

    Instantaneous quantum polynomial-time sampling and verifiable quantum advantage: Stabilizer scheme and classical security,

    M. J. Bremner, B. Cheng, and Z. Ji, “Instantaneous quantum polynomial-time sampling and verifiable quantum advantage: Stabilizer scheme and classical security,”PRX Quantum, vol. 6, no. 2, p. 020315, Apr. 2025. [Online]. Available: https://link.aps.org/doi/10. 1103/PRXQuantum.6.020315

    2025

  19. [27]

    Boundaries of quantum supremacy via random circuit sampling,

    A. Zlokapa, B. Villalonga, S. Boixo, and D. A. Lidar, “Boundaries of quantum supremacy via random circuit sampling,”npj Quantum Inf., vol. 9, no. 1, p. 36, 2023

    2023

  20. [28]

    On the complex- ity and verification of quantum random circuit sampling,

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, “On the complex- ity and verification of quantum random circuit sampling,”Nat. Phys., vol. 15, no. 2, pp. 159–163, 2019

    2019

  21. [29]

    Solving graph problems using Gaussian boson sampling,

    Y .-H. Deng, S.-Q. Gong, Y .-C. Gu, Z.-J. Zhang, H.-L. Liu, H. Su, H.-Y . Tang, J.-M. Xu, M.-H. Jia, M.-C. Chenet al., “Solving graph problems using Gaussian boson sampling,”Phys. Rev. Lett., vol. 130, no. 19, p. 190601, 2023

    2023

  22. [30]

    Using Gaussian boson sampling to find dense subgraphs,

    J. M. Arrazola and T. R. Bromley, “Using Gaussian boson sampling to find dense subgraphs,”Phys. Rev. Lett., vol. 121, no. 3, p. 030503, 2018

    2018

  23. [31]

    Gaussian boson sampling for perfect matchings of arbitrary graphs,

    K. Br ´adler, P.-L. Dallaire-Demers, P. Rebentrost, D. Su, and C. Weed- brook, “Gaussian boson sampling for perfect matchings of arbitrary graphs,”Phys. Rev. A, vol. 98, no. 3, p. 032310, 2018

    2018

  24. [32]

    Toward scalable boson sampling with photon loss,

    H. Wang, W. Li, X. Jiang, Y .-M. He, Y .-H. Li, X. Ding, M.-C. Chen, J. Qin, C.-Z. Peng, C. Schneideret al., “Toward scalable boson sampling with photon loss,”Phys. Rev. Lett., vol. 120, no. 23, p. 230502, 2018

    2018

  25. [33]

    Experimental validation of photonic boson sampling,

    N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloniet al., “Experimental validation of photonic boson sampling,”Nat. Photon., vol. 8, no. 8, pp. 615–620, 2014

    2014

  26. [34]

    Experimental Gaussian boson sampling,

    H.-S. Zhong, L.-C. Peng, Y . Li, Y . Hu, W. Li, J. Qin, D. Wu, W. Zhang, H. Li, L. Zhanget al., “Experimental Gaussian boson sampling,”Sci. Bull., vol. 64, no. 8, pp. 511–515, 2019

    2019

  27. [35]

    Boson sampling with 20 input photons and a 60-mode interferometer in a10 14-dimensional Hilbert space,

    H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y .-M. He, X. Jiang, L. You, Z. Wanget al., “Boson sampling with 20 input photons and a 60-mode interferometer in a10 14-dimensional Hilbert space,” Phys. Rev. Lett., vol. 123, no. 25, p. 250503, 2019

    2019

  28. [36]

    Boson sampling with single- photon Fock states from a bright solid-state source,

    J. Loredo, M. Broome, P. Hilaire, O. Gazzano, I. Sagnes, A. Lemaitre, M. Almeida, P. Senellart, and A. White, “Boson sampling with single- photon Fock states from a bright solid-state source,”Phys. Rev. Lett., vol. 118, no. 13, p. 130503, 2017

    2017

  29. [37]

    Photonic boson sampling in a tunable circuit,

    M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, “Photonic boson sampling in a tunable circuit,”Science, vol. 339, no. 6121, pp. 794–798, 2013

    2013

  30. [38]

    Complexity-theoretic foundations of BosonSampling with a linear number of modes,

    A. Bouland, D. Brod, I. Datta, B. Fefferman, D. Grier, F. Hernandez, and M. Oszmaniec, “Complexity-theoretic foundations of BosonSampling with a linear number of modes,” 2023, arXiv:2312.00286

    2023 arXiv

  31. [39]

    Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling,

    S. Nezami, “Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling,” Apr. 2021, arXiv:2104.06423. [Online]. Available: http://arxiv.org/abs/2104.06423

    2021 arXiv

  32. [40]

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

    H. Mhiri, H. Thomas, L. Monbroussou, U. Chabaud, Z. Holmes, and E. Kashefi, “Boson sampling beyond the dilute regime: second moments and anti-concentration,” 2026, arXiv:2604.14323. [Online]. Available: https://arxiv.org/abs/2604.14323

    2026 arXiv

  33. [41]

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

    Z. Kolarovszki, ´A. Kaposi, Z. Zimbor ´as, and M. Oszmaniec, “General framework for anticoncentration and linear cross-entropy benchmarking in photonic quantum advantage experiments,” 2026, arXiv:2604.15258. [Online]. Available: https://arxiv.org/abs/2604.15258

    2026 arXiv

  34. [42]

    Second moment of Hafnians in Gaussian boson sampling,

    A. Ehrenberg, J. T. Iosue, A. Deshpande, D. Hangleiter, and A. V . Gorshkov, “Second moment of Hafnians in Gaussian boson sampling,” Phys. Rev. A, vol. 111, no. 4, p. 042412, Apr. 2025. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.111.042412

    2025 doi

  35. [43]

    Transition of anticoncentration in Gaussian boson sampling,

    A. Ehrenberg, J. T. Iosue, A. Deshpande, D. Hangleiter, and A. V . Gorshkov, “Transition of anticoncentration in Gaussian boson sampling,” Phys. Rev. Lett., vol. 134, no. 14, p. 140601, Apr. 2025. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.134.140601

    2025 doi

  36. [44]

    Barvinok,Combinatorics and complexity of partition functions, ser

    A. Barvinok,Combinatorics and complexity of partition functions, ser. Algorithms and Combinatorics. Cham: Springer International Publishing, 2016, vol. 30. [Online]. Available: http://link.springer.com/ 10.1007/978-3-319-51829-9

    2016 doi

  37. [45]

    On the permanent of random Bernoulli matrices,

    T. Tao and V . Vu, “On the permanent of random Bernoulli matrices,” Adv. Math., vol. 220, no. 3, pp. 657–669, 2009

    2009

  38. [46]

    On the permanent of a random symmetric matrix,

    M. Kwan and L. Sauermann, “On the permanent of a random symmetric matrix,”Sel. Math. New Ser., vol. 28, no. 1, p. 15, Feb. 2022. [Online]. Available: https://link.springer.com/10.1007/s00029-021-00730-6

    2022 doi

  39. [47]

    Exponential anticoncentration of the permanent,

    Z. Hunter, M. Kwan, and L. Sauermann, “Exponential anticoncentration of the permanent,” Sep. 2025, arXiv:2509.22577 [math]. [Online]. Available: http://arxiv.org/abs/2509.22577

    2025

  40. [48]

    Exponential improvements to the average-case hardness of BosonSampling,

    A. Bouland, I. Datta, B. Fefferman, and F. Hern ´andez, “Exponential improvements to the average-case hardness of BosonSampling,” in2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2025, pp. 912–933

    2025

  41. [49]

    The complexity of computing the permanent,

    L. G. Valiant, “The complexity of computing the permanent,”Theor. Comput. Sci., vol. 8, no. 2, pp. 189–201, 1979

    1979

  42. [50]

    PP is as hard as the polynomial-time hierarchy,

    S. Toda, “PP is as hard as the polynomial-time hierarchy,”SIAM J. Comput., vol. 20, no. 5, pp. 865–877, Oct. 1991. [Online]. Available: http://epubs.siam.org/doi/10.1137/0220053

    1991 doi

  43. [51]

    On a lemma of Littlewood and Offord,

    P. Erd ¨os, “On a lemma of Littlewood and Offord,”Bull. Amer. Math. Soc., vol. 51, pp. 898–902, 1945

    1945

  44. [52]

    On the method of bounded differences,

    C. McDiarmidet al., “On the method of bounded differences,”Surv. Comb., vol. 141, no. 1, pp. 148–188, 1989

    1989

  45. [53]

    Alon and J

    N. Alon and J. H. Spencer,The probabilistic method. John Wiley & Sons, 2016

    2016

  46. [2016]

    Available: https://link.aps.org/doi/10.1103/PhysRevLett

    [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett. 117.080501

    doi

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.