Classical simulation of boson sampling with sparse output
arXiv:1904.05494 · doi:10.1038/s41598-020-71892-0
Abstract
Boson sampling can simulate physical problems for which classical simulations are inefficient. However, not all problems simulated by boson sampling are classically intractable. We consider a situation in which it is known that the outcome from boson sampling is sparse. It can be determined from a few marginal distributions which are classically calculable. Still, recovering of the joint distribution can be of high complexity. We show classically efficient methods of the recovery assuming high sparsity of the joint distribution. Various extensions are discussed including a version involving quantum annealing.
arXiv comment6 pages, 1 figure
References in corpus (26)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Quantum Chemistry in the Age of Quantum Computing
- Quantum state tomography via compressed sensing
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Efficient quantum state tomography
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- Gaussian Boson Sampling
- Efficient Classical Simulation of Continuous Variable Quantum Information Processes
- Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
- Boson Sampling for Molecular Vibronic Spectra
- Convex Optimization for Big Data
- Boson Sampling from Gaussian States
- Efficient measurement of quantum dynamics via compressive sensing
- A detailed study of Gaussian Boson Sampling
- Scalable boson-sampling with time-bin encoding using a loop-based architecture
- Stringent and efficient assessment of Boson-Sampling devices
- Classical simulation of photonic linear optics with lost particles
- Efficient estimation of nearly sparse many-body quantum Hamiltonians
- Simulating realistic non-Gaussian state preparation
- Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
- From estimation of quantum probabilities to simulation of quantum circuits
- Franck-Condon factors by counting perfect matchings of graphs with loops
- Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
- Franck-Condon factors via compressive sensing
Cited by in corpus (7)
- Computational advantage of quantum random sampling
- Classical simulation of linear optics subject to nonuniform losses
- Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
- Franck-Condon factors via compressive sensing
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Bosonic randomized benchmarking with passive transformations
- Compressed sensing enhanced by quantum approximate optimization algorithm