Sample caching Markov chain Monte Carlo approach to boson sampling simulation
arXiv:1907.08077 · doi: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.
5 pages, 4 figures
References in corpus (24)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Characterizing Quantum Supremacy in Near-Term Devices
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Photonic Boson Sampling in a Tunable Circuit
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- Gaussian Boson Sampling
- 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
- Boson Sampling for Molecular Vibronic Spectra
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Boson Sampling from Gaussian States
- Average-case complexity versus approximate simulation of commuting quantum computations
- Experimental Scattershot Boson Sampling
- Generation and sampling of quantum states of light in a silicon chip
- No imminent quantum supremacy by boson sampling
- Instantaneous Quantum Computation
- Using Gaussian Boson Sampling to Find Dense Subgraphs
- General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
- Quantum approximate optimization with Gaussian boson sampling
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Pattern recognition techniques for Boson Sampling validation
- Sample complexity of device-independently certified "quantum supremacy"
- Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states---The quantum-classical divide and computational-complexity transitions in linear optics
- Towards Quantum Supremacy with Lossy Scattershot Boson Sampling