Sample caching Markov chain Monte Carlo approach to boson sampling simulation
Open Access
- 1 March 2020
- journal article
- research article
- Published by IOP Publishing in New Journal of Physics
- Vol. 22 (3), 033022
- https://doi.org/10.1088/1367-2630/ab73c4
Abstract
Boson sampling is a promising candidate for quantum supremacy. It requires to sample from a complicated distribution, and is trusted to be intractable on classical computers. Among the various classical sampling methods, the Markov chain Monte Carlo method is an important approach to the simulation and validation of boson sampling. This method however suffers from the severe sample loss issue caused by the autocorrelation of the sample sequence. Addressing this, we propose the sample caching Markov chain Monte Carlo method that eliminates the correlations among the samples, and prevents the sample loss at the meantime, allowing more efficient simulation of boson sampling. Moreover, our method can be used as a general sampling framework that can benefit a wide range of sampling tasks, and is particularly suitable for applications where a large number of samples are taken.Funding Information
- National Natural Science Foundation of China (11621091)
This publication has 40 references indexed in Scilit:
- Photonic Boson Sampling in a Tunable CircuitScience, 2013
- Modified Metropolis–Hastings algorithm with delayed rejectionProbabilistic Engineering Mechanics, 2011
- The permanent of a square matrixEuropean Journal of Combinatorics, 2010
- Temporally unstructured quantum computationProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009
- Quantum Computation and Quantum InformationAmerican Journal of Physics, 2002
- Estimation of small failure probabilities in high dimensions by subset simulationProbabilistic Engineering Mechanics, 2001
- Metropolized independent sampling with comparisons to rejection sampling and importance samplingStatistics and Computing, 1996
- Understanding the Metropolis-Hastings AlgorithmThe American Statistician, 1995
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Testing for Serial Correlation in Least Squares Regression. IIIBiometrika, 1971