BosonSampling is far from uniform
The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Abstract
BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. \ In a recent manuscript, Gogolin et al.\ claimed that even an ideal BosonSampling device's output would be operationally indistinguishable\textquotedblright\ from a uniform random outcome, at least \textquotedblleft without detailed a priori knowledge; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of a priori knowledge such that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments.However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s arguments. We prove that, with high probability over a Haar-random matrix $A$, the BosonSampling distribution induced by $A$ is far from the uniform distribution in total variation distance. More surprisingly, and counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three bonus results about BosonSampling. First, we report an observation of Fernando Brandao: that one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that Fermion Sampling is solvable in classical polynomial time, and we reuse techniques from our Boson Sampling analysis to characterize random FermionSampling distributions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A scheme for efficient quantum computation with linear optics
Knill, E., Laflamme, R., & Milburn, G. J. (2001) · Nature · doi:10.1038/35051009 · Cited by 5,880
Boson Sampling on a Photonic Chip
Spring, J. B., Metcalf, B. J., Humphreys, P. C., Kolthammer, W. S., Jin, X.-M., Barbieri, M., Datta, A., Thomas-Peter, N., Langford, N. K., Kundys, D., et al. (2013) · Science · doi:10.1126/science.1231692 · Cited by 837
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., & Walther, P. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.102 · Cited by 709
Integrated multimode interferometers with arbitrary designs for photonic boson sampling
Crespi, A., Osellame, R., Ramponi, R., Brod, D. J., Galvão, E. F., Spagnolo, N., Vitelli, C., Maiorino, E., Mataloni, P., & Sciarrino, F. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.112 · Cited by 662
Photonic Boson Sampling in a Tunable Circuit
Broome, M. A., Fedrizzi, A., Rahimi-Keshari, S., Dove, J., Aaronson, S., Ralph, T. C., & White, A. G. (2013) · Science · doi:10.1126/science.1231440 · Cited by 634 · cited 1×
“74 60 v2 [ qu an tph ] 1 O ct 2 01 3”
Self-citationClassical simulation of noninteracting-fermion quantum circuits
Terhal, B. M., & DiVincenzo, D. P. (2002) · Physical Review A · doi:10.1103/physreva.65.032325 · Cited by 329 · cited 2×
“It was already known, from work by Valiant [19], Terhal and DiVincenzo [16], and Knill [10], that FermionSampling is efficiently solvable classically.”
ResultQuantum Circuits That Can Be Simulated Classically in Polynomial Time
Valiant, L. G. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700377025 · Cited by 311 · cited 1×
“Thus, in Appendix 11, we study the broader question of BosonSampling versus any efficientlysamplable distribution.”
BackgroundThe Computational Complexity of Linear Optics
Aaronson, S., & Arkhipov, A. (2014) · Research in Optical Sciences · doi:10.1364/qim.2014.qth1a.2 · Cited by 75
Self-citation
Cited by
Quantum computational advantage using photons
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., et al. (2020) · Science · doi:10.1126/science.abe8770 · Cited by 2,405
“In stark contrast, due to constructive and destructive interference, an ideal boson-sampler is expected to generate samples with exponentially different occurring probability ( 5,51 ).”
BackgroundMethodCarolan, J., Harrold, C., Sparrow, C., Martín-López, E., Russell, N. J., Silverstone, J. W., Shadbolt, P. J., Matsuda, N., Oguma, M., Itoh, M., et al. (2015) · Science · doi:10.1126/science.aab3642 · Cited by 1,093
Photonic quantum information processing: a review
Flamini, F., Spagnolo, N., & Sciarrino, F. (2019) · Reports on Progress in Physics · doi:10.1088/1361-6633/aad5b2 · Cited by 770
Quantum computational supremacy
Harrow, A. W., & Montanaro, A. (2017) · Nature · doi:10.1038/nature23458 · Cited by 702
Boson Sampling with 20 Input Photons and a 60-Mode Interferometer in a1014-Dimensional Hilbert Space
Wang, H., Qin, J., Ding, X., Chen, M.-C., Chen, S., You, X., He, Y.-M., Jiang, X., You, L., Wang, Z., et al. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.250503 · Cited by 508
Metadata
- Authors
- Aaronson, S., & Arkhipov, A.
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2014-11
- Volume
- 14
- Issue
- 15&16
- Pages
- 1383-1423
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W1928647796
- Cited by
- 101
- References
- 8
- FWCI
- 13.53
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.