Classical simulation of boson sampling with sparse output

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.

6 pages, 1 figure

References in corpus (12)

• Quantum Chemistry in the Age of Quantum Computing
• Efficient quantum state tomography
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Convex Optimization for Big Data
• A detailed study of Gaussian Boson Sampling
• Scalable boson-sampling with time-bin encoding using a loop-based architecture
• Classical simulation of photonic linear optics with lost particles
• Simulating realistic non-Gaussian state preparation
• From estimation of quantum probabilities to simulation of quantum circuits
• Franck-Condon factors by counting perfect matchings of graphs with loops
• 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