BosonSampling Is Far From Uniform

Definition

• BosonSampling samples output configurations from a distribution determined by permanents of submatrices of an optical transition matrix.The input is an m × n matrix with orthonormal columns, and outcomes record photon counts across output modes.Source: §1 · pp. 1–2

Quantum implementation

• A nonadaptive beamsplitter network with identical photons solves BosonSampling naturally on a quantum computer.The matrix A represents transitions between input and output modes, while S specifies the measured photon configuration.Source: §1 · p. 2

Classical hardness

• Exact classical BosonSampling would collapse the polynomial hierarchy, while approximate sampling is linked to the difficulty of approximating Gaussian matrix permanents.These conclusions support BosonSampling as evidence relevant to Feynman’s Conjecture under the authors’ complexity assumptions.Source: §1 · p. 2

Experiments

• Early experiments used three or four photons and five or six output modes, confirming that three-photon amplitudes are governed by matrix permanents.The authors describe these experiments as initial demonstrations rather than computational speedups.Source: §1 · p. 3

Experimental outlook

• Scaling to roughly 20–30 photons could make BosonSampling outperform its fastest classical simulations, but reliable single-photon sources and larger networks remain open challenges.The authors also question whether this regime is reachable without quantum fault-tolerance.Source: §1 · p. 3

Claims

• Gogolin et al. claimed that even ideal BosonSampling outputs could be operationally indistinguishable from uniform random outputs under reasonable assumptions.They interpreted this as limiting a skeptic’s ability to identify a genuine BosonSampling device.Source: §2 · p. 3

Limitations of “Symmetric Algorithms”

• The paper argues that restricting verifiers to symmetric algorithms is unjustified because the verifier knows the matrix A and can use the identities of observed outcomes.The authors compare discarding these identities to ignoring whether proposed factors actually multiply to the input integer.Source: §2 · p. 4

Intractability of Verification

• The authors note that the possibility of computationally hard verification was already discussed in [1], but argue that asymptotic hardness need not obstruct practical experiments with about 30 photons.They criticize Gogolin et al. for presenting this point without engaging with the practical qualification in [1].Source: §2 · p. 4

Detecting Deviations from Uniformity

• A linear-time row-norm estimator R* distinguishes BosonSampling from uniform with constant bias for typical Haar-random matrices.The estimator is scaled to have expectation one and exploits a weak correlation with squared permanents.Source: §3 · p. 4

Deviation from Uniformity

• For Haar-random A, BosonSampling distributions have Ω(1) variation distance from uniform with probability 1−O(δ), under the theorem’s mode-count condition.The result applies to uniform distributions over all outcomes or collision-free outcomes.Source: §3 · p. 4

BosonSampling versus Efficiently Samplable Distributions

• R* does not distinguish BosonSampling from every efficiently samplable distribution, because natural classical models and high-entropy mockups can reproduce its statistics or evade fixed-size circuits.The paper leaves open whether one efficiently samplable distribution fools every polynomial-time algorithm.Source: §3 · pp. 4–5

Robustness

• The estimator remains applicable with general initial states concentrated in few modes and can tolerate substantial random photon loss.The stated scope includes pure or mixed states and coherent or Gaussian inputs.Source: §3 · p. 5

FermionSampling

• FermionSampling is solvable in classical polynomial time, and the paper presents a simpler and faster algorithm than previously published approaches.The authors use this contrast to argue that quantum behavior, large Hilbert spaces, and multiparticle interference alone do not establish computational hardness.Source: §3 · p. 5

Random FermionSampling

• For Haar-random fermionic instances, squared determinants converge to a lognormal distribution, motivating a conjectured analogous limit for squared permanents.The determinant convergence rate is stated as O(…); the permanent claim remains a conjecture based partly on numerical similarity.Source: §3 · p. 5

Notation

• Variation distance measures the maximum bias with which samples from two probability distributions can be distinguished.Source: §4 · p. 6

Collision-free outcomes

• An outcome is collision-free when every mode contains at most one photon, making its associated matrix an n × n submatrix of A.For such outcomes, the probability is simply |Per(AS)|^2.Source: §4 · p. 6

Regime of analysis

• When m is much larger than n^2, most outcomes are collision-free, and the authors generally restrict analysis to this regime.For Haar-random A, a prior theorem justifies focusing on collision-free outcomes.Source: §4 · p. 6

Verification criteria

• The paper defines useful verifiers as polynomial-time tests that accept samples from DA and reject specified fake distributions, with uniformity and properness as common additional constraints.Properness restricts attention to collision-free outcomes because the BosonSampling hardness results use that regime.Source: §5 · pp. 6–7

Symmetry

• Symmetric verifiers retain only outcome multiplicities, ignoring the identities of observed outcomes despite knowing A.This restriction makes the verifier invariant under arbitrary permutations of the exponentially large outcome set.Source: §5 · pp. 7–8
• Gogolin et al.’s exponential-sample result applies to symmetric algorithms because repeated outcomes are unlikely when the collision-free outcome space is exponentially large.After subexponentially many runs, such algorithms typically learn only that no outcome has appeared twice, whether sampling uses DA or U.Source: §5 · p. 7

Why symmetry is inappropriate

• The paper rejects symmetry as an appropriate verification constraint because A is public input and outcome identities are directly relevant to testing DA against U.The authors compare discarding these identities to judging factoring without checking whether the reported factors multiply to N.Source: §5 · p. 8

Weak symmetry

• Even weakly symmetric verifiers can distinguish DA from U using poly(m,n) samples, because mode relabelings are far fewer than arbitrary relabelings of all outcomes.The construction runs a verifier across the possible input and output mode relabelings and checks whether any gives a good match.Source: §5 · p. 8

Unrestricted verification

• Unrestricted verifiers need only O(1/epsilon^2) samples when the variation distance epsilon is constant, so proving epsilon = Omega(1) is the central remaining task.The paper later establishes this constant-distance condition with high probability over A.Source: §5 · p. 8

Scale limitations

• The paper acknowledges that for very large n, especially above about 100 photons, feasible classical verification may be unavailable without presupposing the physical laws being tested.This limitation motivates distinguishing near-term proof-of-principle experiments from claims about scalable certification.Source: §6 · p. 9

Open complexity questions

• Gogolin et al. provide no formal proof that BosonSampling verification is intractable, and the paper likewise lacks a complete classification of efficiently verifiable tasks.The authors describe verification as encompassing multiple technically distinct notions whose complexity remains unsettled.Source: §6 · p. 9

What verification requires

• Hardness of computing Per(X) does not prove that every meaningful verification task for DA is hard.A verifier might distinguish DA from broad null hypotheses without calculating the permanent of any particular matrix.Source: §6 · p. 10

Near-term experiments

• For near-term experiments, n between 20 and 30 could allow classical checking while still testing a sampling task that is difficult for classical simulation.This regime is presented as a proof-of-principle setting rather than a claim that arbitrarily large devices can be efficiently certified.Source: §6 · p. 10

Experimental goal

• The intended experimental regime is one where both linear-optical devices and classical computers can solve BosonSampling in non-astronomical time, but devices are noticeably faster.This is framed as sufficient for demonstrating a meaningful quantum-over-classical performance gap.Source: §6 · p. 10

Near-term experiments

• At n = 30, Ryser’s algorithm requires about 64 billion floating-point operations, potentially allowing classical checking while a device samples faster than known classical methods.The proposed check compares observed outputs’ permanent-related statistics with their expected values.Source: §6 · p. 10

7 Deviation from Uniformity

• The key structural fact is that P(X)=|Per(X)|^2/n! is a mixture of exponentially distributed random variables for an iid Gaussian matrix X.This follows by expanding the permanent along one row and conditioning on the remaining minors.Source: §7 · p. 11
• The density f_P is monotonically decreasing, finite, positive, and smooth away from a possible divergence at zero.The section also establishes that f_P is far from the point distribution concentrated at P=1, with bounds including approximately 0.313 and above 0.615.Source: §7 · p. 13
• A BosonSampled submatrix tends to stand out through an unusually large permanent, allowing distinction from a uniformly sampled submatrix without knowing its label or the rest of A.The argument compares distributions of scaled submatrices generated under BosonSampling and uniform sampling.Source: §7 · p. 14
• The proof controls heavy-tail and correlation difficulties using Gaussian-submatrix approximation, bounds on overlapping outcomes, and a variation-distance lemma.The stated technical regime m≥n^5.1/δ is described as probably non-tight, with n^2 expected in place of n^5.1.Source: §7 · pp. 14, 16
• With probability 1−O(δ) over Haar-random A satisfying m≥n^5.1/δ, the BosonSampling distribution D_A has constant variation distance from uniform U.Thus only a constant number of samples suffice for information-theoretic distinction with constant bias.Source: §7 · pp. 11, 17

7.1 Weakly-Symmetric Verifiers

• Even weakly-symmetric verifiers can distinguish D_A from U for generic A, despite ignoring input and output mode labels.The construction symmetrizes a proper verifier over row and column permutations while retaining its distinguishing behavior with high probability.Source: §7.1 · p. 18

8 Detecting Deviations from Uniformity

• R*(X), the normalized product of squared row norms, is efficiently computable and only barely correlated with |Per(X)|2, yet its fluctuations suffice for constant-bias distinguishing.Independence between the permanent-related factor and R* reduces distinguishing power to the intrinsic variation of R*; a product of row norms is needed for constant bias.Source: §8 · pp. 20, 22
• With probability 1−O(δ) over Haar-random A (m≥n^5.1/δ), testing whether R*(AS)≥1 distinguishes DA from U with constant bias.The test applies for sufficiently large n and uses collision-free outcomes, relying on Gaussian approximation and near-independence of submatrices.Source: §8 · p. 25

8.1 Classical Mockup Distribution

• The classical mockup distribution MA is samplable in O(mn) time, but every verification test using only R* accepts MA and DA with exactly the same probability.MA models distinguishable photons, or classical particles, independently entering bins according to probabilities determined by A’s entrywise squared magnitudes.Source: §8.1 · pp. 25–26
• R* therefore rules out uniform noise but cannot by itself certify BosonSampling or quantum interference; additional evidence and tests are required to exclude MA and related alternatives.FermionSampling FA and another distribution BA provide further classically samplable examples with the same relevant row-scaling statistics.Source: §8.1 · p. 26
• A complete proof would need to establish that, with high probability over Haar-random A, D_A differs statistically from M_A, F_A, and B_A in the stated tests; these statements are left for future work.The authors regard the statements as presumably true but do not prove them.Source: §8.1 · p. 27

• A row-norm estimator efficiently distinguishes a generic BosonSampling distribution from uniform, despite earlier claims that distinguishing might be hard.The estimator has constant or non-negligible bias in the relevant regimes.Source: §9 · pp. 27–28
• The paper leaves open whether stronger approximation algorithms for |Per (X)|2 exist, because its weak estimator remains far from the Permanent of Gaussians Conjecture’s hardness parameters.Linial, Samorodnitsky, and Wigderson’s iterative row-and-column normalization is proposed as an unresolved comparison.Source: §9 · pp. 27–28
• For any fixed polynomial size, an efficiently samplable high-entropy distribution can be indistinguishable from the collision-free part of a BosonSampling distribution.The authors emphasize that the fixed-size result says little specifically about BosonSampling and contrast it with the harder question of one mockup defeating all polynomial-time distinguishers.Source: §9 · p. 28
• The distinguishability results extend to photon losses and general initial states, although experimental errors may reduce distinguishability from mockup distributions.The analysis covers random photon loss and Gaussian inputs but not unitary-dependent losses or mode mismatch.Source: §9 · p. 28
• The analysis mainly assumes collision-free outcomes and Haar-random matrices with m ≥ n^5.1, leaving arbitrary matrices, smaller m, stronger probability bounds, and collision-based tests open.The authors also ask whether including multi-photon collisions can strengthen distinguishing or verification algorithms.Source: §9 · p. 29
• For Gaussian X, |Det (X)|2 is O-close to a lognormal random variable, but this approximation breaks down when |Det (X)|2 is very small or very large.A more detailed understanding of its pdf might provide clues about the pdf for |Per (X)|2 and proving the Permanent Anti-Concentration Conjecture (PACC) from [1].Source: §9 · p. 29

• Brandao’s result gives an efficiently samplable distribution with large min-entropy that is indistinguishable from the collision-free part of generic BosonSampling.The BosonSampling-specific ingredient is that the distribution is close to one with large min-entropy.Source: §11 · p. 31
• Without the large-entropy requirement, constructing a fixed-size indistinguishable mockup is trivial for any distribution, so the entropy condition is the nontrivial part of the observation.A sampled multiset can be hardwired into a small circuit and made indistinguishable from a fixed circuit by concentration and a union bound.Source: §11 · p. 31
• The proof first replaces the collision-free BosonSampling distribution by a nearby distribution with high min-entropy, using a cutoff that limits every probability mass.The smoothing step follows the Renner–Wolf lemma and preserves closeness while increasing min-entropy.Source: §11 · p. 32
• Trevisan-Tulsiani-Vadhan’s theorem then converts the high-min-entropy distribution into one sampled efficiently and indistinguishable to circuits of bounded size.The theorem supplies the circuit construction once the min-entropy condition is established.Source: §11 · p. 32
• For every circuit-size bound T and error ε, a circuit of size polynomial in T, n, 1/ε, and 1/δ samples a distribution indistinguishable from BosonSampling by circuits of size at most T.The result holds with probability at least 1 −δ over a Haar-random BosonSampling matrix under m ≥ n^5.1.Source: §11 · pp. 31, 34

• For essentially any initial state, the row-norm estimator remains a distinguisher from uniform with non-negligible, typically constant, bias.The discussion is explicitly given at a physics level of rigor.Source: §12 · pp. 34, 36
• The analysis extends from pure states to mixed states because the output probabilities are convex combinations sharing the same row-norm factor.This common factor allows the same distinguishability argument to apply after mixing.Source: §12 · pp. 35–36
• The framework assumes many output modes relative to input and detected photons, and a non-negligible probability of detecting at least one photon.The authors regard k > 0 as necessary and suggest that more sophisticated analysis could weaken the mode assumptions.Source: §12 · p. 35
• The argument models photon losses as mixtures over photon configurations but excludes unitary-dependent losses, mode mismatch, and other complicated errors.Extending the analysis to those processes is left as future work.Source: §12 · p. 35
• The estimator’s bias is controlled by intrinsic variation in the row-norm statistic under uniform sampling, which persists for collision-free outcomes and increases when collisions are included.The variation is non-negligible for k > 0 and constant when k = Ω(n).Source: §12 · p. 36

• FermionSampling is solvable classically in polynomial time, using an algorithm simpler and faster than previous procedures.The algorithm is closely related to sampling methods for determinantal point processes.Source: §13 · p. 37
• The distribution of |Det (X)|2 approaches a lognormal law at a 1/log^(3/2) n rate, implying convergence of collision-free FermionSampling probabilities to lognormal.The result fills gaps in earlier real-matrix analyses by handling complex matrices and bounding the convergence rate.Source: §13 · pp. 37, 39, 40
• FermionSampling serves as a tractable mockup and model system because its row-norm statistics and near-identical determinant/permanent density shapes parallel BosonSampling.Unlike BosonSampling, repeated rows have zero determinant, reflecting the exclusion principle.Source: §13 · p. 37
• The sampler repeatedly selects a row according to its squared projected norm, projects all remaining rows orthogonally, and outputs the selected set.The procedure samples h_t, updates every row by projection, and returns S = {h_1, ..., h_n}.Source: §13 · pp. 37–38
• Correctness follows because the product of successive squared projection norms equals the squared determinant, yielding the FermionSampling probabilities.Accounting for all orderings contributes the factor n!, producing |Det (A_S)|2.Source: §13 · p. 38
• For an iid complex Gaussian matrix, |Det (X)|2 decomposes into a product of independent chi-square variables from successive orthogonal projections.This decomposition underlies the distributional analysis of random FermionSampling.Source: §13 · p. 39
• Despite its asymptotic lognormal approximation, |Det (X)|2 is not exactly lognormal at fixed n because its density is monotonically decreasing and nonzero at the origin.A lognormal density instead vanishes at the origin and is not monotonically decreasing.Source: §13 · pp. 40–41