Fetching the paper…
Reading the bibliography…
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.
Combinatorial Mathematics
Ryser, H. J. (1963) · 1963
Earlier work this paper cites.
Permanents
Marcus, M. and Minc, H. (1965) · 1965
Earlier work this paper cites.
An Introduction to Probability Theory and its Applications. - Vol. 1
Feller, W. (1968) · 1968
Earlier work this paper cites.
Monte Carlo sampling methods using Markov chains and their applications
Hastings, W. K. (1970) · 1970
Earlier work this paper cites.
New fast method for generating discrete random numbers with arbitrary frequency distributions
Walker, A. J. (1974) · 1974
Earlier work this paper cites.
Combinatorial Algorithms: for Computers and Calculators
Nijenhuis, A. and Wilf, H. S. (1978) · 1978
Earlier work this paper cites.
On the alias method for generating random variables from a discrete distribution
Kronmal, R. A. and Peterson Jr, A. V. (1979) · 1979
Earlier work this paper cites.
The complexity of computing the permanent
Valiant, L. (1979) · 1979
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · 1996
Earlier work this paper cites.
Exact sampling with coupled Markov chains and applications to statistical mechanics
Propp, J. G. and Wilson, D. B. (1996) · 1996
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · 1997
Earlier work this paper cites.
Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
Terhal, B. M. and DiVincenzo, D. P. (2004) · 2004
Earlier work this paper cites.
Monte Carlo Strategies in Scientific Computing
Liu, J. S. (2008) · 2008
Earlier work this paper cites.
The permanent of a square matrix
Glynn, D. G. (2010) · 2010
Cited alongside, same era.
The computational complexity of linear optics
Aaronson, S. and Arkhipov, A. (2011) · 2011
Cited alongside, same era.
Entanglement and Interference of Identical Particles
Tichy, M. C. (2011) · 2011
Cited alongside, same era.
The bosonic birthday paradox
Arkhipov, A. and Kuperberg, G. (2012) · 2012
Cited alongside, same era.
Photonic boson sampling in a tunable circuit
Broome, M. A., Fedrizzi, A., Rahimi-Keshari, S., Dove, J., Aaronson, S., Ralph, T. C., and White, A. G. (2013) · 2013
Cited alongside, same era.
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., and Sciarrino, F. (2013) · 2013
Cited alongside, same era.
Weighted random sampling over data streams
Efraimidis, P. S. (2015) · 2015
Later among the works it cites.
Bayesian computation: a summary of the current state, and samples backwards and forwards
Green, P. J., 𝖫 \mathsf{L} atuszyński, K., Pereyra, M., and Robert, C. P. (2015) · 2015
Later among the works it cites.
Below all subsets for some permutational counting problems
Björklund, A. (2016) · 2016
Later among the works it cites.
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., and Neven, H. (2016) · 2016
Later among the works it cites.
Towards quantum supremacy with lossy scattershot boson sampling
Latmiral, L., Spagnolo, N., and Sciarrino, F. (2016) · 2016
Later among the works it cites.
Statistical benchmark for bosonsampling
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons
Shchesnovich, V. (2013) · 2013
Cited alongside, same era.
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) · 2013
Cited alongside, same era.
Experimental boson sampling
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., and Walther, P. (2013) · 2013
Cited alongside, same era.
Bosonsampling is far from uniform
Aaronson, S. and Arkhipov, A. (2014) · 2014
Cited alongside, same era.
Experimental validation of photonic boson sampling
Spagnolo, N., Vitelli, C., Bentivegna, M., Brod, D. J., Crespi, A., Flamini, F., Giacomini, S., Milani, G., Ramponi, R., Mataloni, P., et al. (2014) · 2014
Cited alongside, same era.
Stringent and efficient assessment of boson-sampling devices
Tichy, M. C., Mayer, K., Buchleitner, A., and Mølmer, K. (2014) · 2014
Cited alongside, same era.
Walschaers, M., Kuipers, J., Urbina, J.-D., Mayer, K., Tichy, M. C., Richter, K., and Buchleitner, A. (2016) · 2016
Later among the works it cites.
Multi-photon boson-sampling machines beating early classical computers
Wang, H., He, Y., Li, Y.-H., Su, Z.-E., Li, B., Huang, H.-L., Ding, X., Chen, M.-C., Liu, C., Qin, J., Li, J.-P., He, Y.-M., Schneider, C., Kamp, M., Peng, C.-Z., Hoefling, S., Lu, C.-Y., and Pan, J.-W. (2016) · 2016
Later among the works it cites.
Certification of boson sampling devices with coarse-grained measurements
Wang, S.-T. and Duan, L. (2016) · 2016
Later among the works it cites.
Computing permanents for boson sampling on Tianhe-2 supercomputer
Wu, J., Liu, Y., Zhang, B., Jin, X., Wang, Y., Wang, H., and Yang, X. (2016) · 2016
Later among the works it cites.
R: Classical Boson Sampling
Clifford, P. and Clifford, R. (2017) · 2017
Closest in time.
Quantum computational supremacy
Harrow, A. W. and Montanaro, A. (2017) · 2017
Closest in time.
Quantum sampling problems, bosonsampling and quantum supremacy
Lund, A. P., Bremner, M. J., and Ralph, T. C. (2017) · 2017
Closest in time.
Classical boson sampling algorithms with superior performance to near-term experiments
Neville, A., Sparrow, C., Clifford, R., Johnston, E., Birchall, P. M., Montanaro, A., and Laing, A. (2017) · 2017
Closest in time.