Stringent and Efficient Assessment of Boson-Sampling Devices

Boson sampling holds the potential to experimentally falsify the extended Church-Turing thesis. The computational hardness of boson sampling, however, complicates the certification that an experimental device yields correct results in the regime in which it outmatches classical computers. To certify a boson sampler, one needs to verify quantum predictions and rule out models that yield these predictions without true many-boson interference. We show that a semiclassical model for many-boson propagation reproduces coarse-grained observables that are proposed as witnesses of boson sampling. A test based on Fourier matrices is demonstrated to falsify physically plausible alternatives to coherent many-boson propagation.

Figure 1

Sampling models. (a) Uniform sampler: The scattering matrix and the initial state are ignored. (b) Classical sampler: Distinguishable particles propagate independently without interference. (c) Mean-field sampler: Macroscopic interference and bosonic effects are incorporated. (d) Boson sampling requires the interference of all $n!$ paths of the $n$-boson wave function.

Figure 2

Bunching and clouding in different sampling models. Classical distinguishable particles (blue circles) are compared to the mean-field sampler (red squares) and the boson-sampler (black diamonds). (a) Coincidence probability $P_1$ for 100 Haar-random unitary matrices of dimension $m=n^2$ with error bars that represent one standard deviation (the mean-field sampler is hardly discernible from the boson sampler). The lines are the combinatorially expected probabilities [16]. (b) Clouding for a discrete-time quantum walk of eight steps with $n$ particles starting in adjacent modes [20, 28]. The probability $C$ that all particles be in the same half of the output array coincides for the mean-field and boson samplers. The values for $P_1$ and $C$ for the mean-field sampler are obtained by averaging numerically over random phases.

Figure 3

Violation $\mathcal{V}$ of the suppression law (7) by the classical (blue circles), mean-field (red squares), and misaligned (brown diamonds) samplers for $m=n^2$. The classical violation coincides with the ratio of suppressed events for the boson sampler, $(n-1)/n$ (black solid line). For small particle numbers $n⪅4$, the suppression law favors bunched states with many particles in few modes, which alleviates the violation by the mean-field sampler. For the misaligned data, we assume that one particle out of $n$ is distinguishable from the others; the total violation is inferred from computing the probability for up to $10^4$ distinct forbidden output states.

Figure 4

Violation $\mathcal{V}$ for matrices described by Eq. (11), for $n=3,10$, and $m=n^2$. We compute the total probability of 200 randomly chosen forbidden events for 400 different matrices $\delta$ for each value of the average deviation $||\delta ||$. Error bars represent one standard deviation; the dashed red and solid blue lines show the estimate (13) for $n=10$ and $n=3$, respectively, which breaks down when $||\delta ||$ is not smaller than $1/n$. In order to observe the suppression law in the experiment, the violation needs to be significantly smaller than $(n-1)/n$ (compare to Fig. 3).