Source-linked AI summary
The Classical Complexity of Boson Sampling
Peter Clifford, Raphaël Clifford
TL;DR
Exact Boson Sampling is a classically challenging sampling problem, and its complexity bears on the experiment size needed to demonstrate quantum supremacy. The paper develops an exact classical sampler with a faster runtime, supporting n = 50 as a threshold for quantum supremacy in this setting.
Problem
Exact Boson Sampling is challenging for classical computation, and without a clear account of its classical complexity the minimum experiment size needed to establish quantum supremacy is difficult to determine.
Source: §1 · p. 2Method
The algorithm expands the sample space and uses conditional sampling, Laplace expansion, and auxiliary variables to construct an exact sampler.
Source: §1 · p. 3Results
O(n2^n + mn^2) time yields an exact Boson Sampling algorithm dramatically faster than the naive approach, and the analysis supports n = 50 as a quantum-supremacy threshold.
Source: §1 · pp. 2–3Takeaways & Limitations
The authors’ analysis supports n = 50 as the threshold for quantum supremacy in exact Boson Sampling.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed by Aaronson and Arkhipov in 2011 as an attainable demonstration of `quantum supremacy', that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless $P^{\#P} = BPP^{NP}$ and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem takes $O({m + n -1 \choose n} n 2^n )$ time to produce samples for a system with input size $n$ and $m$ output modes, making it infeasible for anything but the smallest values of $n$ and $m$. We give an algorithm that is much faster, running in $O(n 2^n + \operatorname{poly}(m,n))$ time and $O(m)$ additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.
1 Introduction
Boson Sampling was proposed as a linear-optics route to demonstrating quantum speed-up, but its classical complexity made the minimum experiment size uncertain. This section presents an exact, faster classical sampler and describes consequences and applications of the improved analysis.
1 Introduction
- The algorithm also returns a sample’s probability at no extra computational cost and enables an efficiently computable bound on duplicate-element probabilities.That bound can be used to analyze rejection-sampling variants in the collision-free setting.Source: §1 · pp. 2–3
- The analysis supports n = 50 as the threshold for quantum supremacy in exact Boson Sampling, based on the time bound and feasibility studies for large permanents.The cited discussion notes that earlier estimates varied from 7 to 50 when m = n^2.Source: §1 · pp. 2–3
- The algorithm applies directly to scattershot Boson Sampling and lets researchers sample from the distribution over a wider parameter range for testing physical devices.This wider range allows more statistical tests of whether device outputs correspond to theoretical predictions.Source: §1 · p. 3
- O(n2^n + mn^2) time, with the exponential term depending only on n, gives an exact Boson Sampling algorithm dramatically faster than the naive approach.The algorithm’s total cost per sample is approximately that of calculating two n × n permanents.Source: §1 · pp. 2–3
- The algorithm expands multisets into arrays, uses conditional probabilities, and combines Laplace expansion with auxiliary variables and conditioning to obtain its improved complexity.The initial array-based approach gives an O(mn^3n) algorithm before the further innovations yield the final bound.Source: §1 · p. 3
- Unlike the earlier MCMC approach, which offered numerical evidence for approximate sampling, this is described as the first provably correct algorithmic speed-up for Boson Sampling.Its cost is approximately two n × n permanent calculations for all n when m remains polynomial in n.Source: §1 · p. 2, Related work and computation of the… · p. 4
2 Problem specification
Boson Sampling is formulated as sampling multisets of size n from [m], with probabilities determined by matrix permanents. The paper’s task is to simulate samples from this probability mass function.
2 Problem specification
- The target is a probability mass function q over multisets of size n whose elements lie in [m].Each multiset is represented by a non-decreasing array z.Source: §2 · pp. 4–5
- For each multiset z, the matrix A_z is formed by taking rows of A according to z, including repeated rows.A consists of the first n columns of an m × m Haar random unitary matrix.Source: §2 · p. 5
- The probability assigned to a multiset is specified using the permanent of A_z and the multiplicity factor μ(z).μ(z) is the product of the factorials of the multiplicities of the values in z.Source: §2 · p. 5
- The Cauchy-Binet formula for permanents establishes that q is a probability mass function, and the computing task is to simulate samples from q(z).Source: §2 · p. 5
3 Exact Boson Sampling Algorithms
The section develops two exact samplers, first using sequential conditional probabilities and then accelerating that approach by conditioning on a random permutation of columns. The faster sampler has an exponential cost dependent on n and polynomial dependence on m, with O(m) additional space.
Algorithm A
- Algorithm A’s sequential conditional sampler serves as a faster-than-prior baseline and prepares the way for Algorithm B, the paper’s main result.Source: §3 · p. 5
- Algorithm A expands the multiset space to arrays in [m]^n, samples the array through conditional probability mass functions, then sorts it to recover a sample from q(z).Permuting an array representation preserves its permanent, enabling the expanded-space construction.Source: §3 · pp. 5, 7
- Algorithm A samples exactly in O(mn3^n) time per sample and uses O(m) additional words beyond the input.Its total operation count is O(mn3^n), with one permanent result and a list of m probabilities stored at a time.Source: §3 · p. 8
Algorithm B
- The joint permanents needed for row variants can be computed in O(k2^k) time and O(k) additional space.Gray-code ordering and cumulative products support the joint computation.Source: §3 · p. 9
- Algorithm B introduces a uniformly random column permutation α and conditional pmfs φ, whose average over α recovers the target array distribution p(r).This conditioning permits faster sequential sampling while preserving the marginal distribution.Source: §3 · p. 9
- Algorithm B samples each next array element from a conditional pmf using permanents and Laplace expansion, then sorts the completed array to obtain the Boson Sampling multiset.For stage k, the method computes the needed row-variant permanents jointly in O(k2^k) time and forms an array of m weights.Source: §3 · pp. 10–11
- Algorithm B samples one output in O(n2^n + poly(m, n)) time, with O(m) space and the sample probability available at no extra computational cost.The total time is also expressed as O(n2^n) + O(mn2); the exponentially growing term is approximately the cost of two n × n permanents.Source: §3 · p. 11
Appendix
The appendix compares the operation counts of two permanent-evaluation approaches and bounds the probability of duplicate outputs. The Haar-averaged upper bound scales approximately as n²/m.
- Glynn’s-formula evaluation of Per B takes k2^k operations; Lemma 2’s count is approximately 25% larger, though complex additions and multiplications can differ in floating-point cost.Source: Appendix · p. 12
- The duplication probability is A-specific and measures the chance that a sampled output contains repeated values.Source: Appendix · p. 12
- The expected upper bound on duplication probability, averaged over Haar-random A, is n(n−1)/(m+1), approximately n²/m.Source: Appendix · p. 12