On the classical complexity of sampling from quantum interference of indistinguishable bosons

DOI10.1142/S0219749920500446MaRDI QIDQ4985083zbMATH OpenOpenAlexFDO

Authors V. S. Shchesnovich

Publication date 22 April 2021

Published in International Journal of Quantum Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.02013

zbMATH Keywords

boson samplingcomputational complexitymulti-photon interference

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68) Bosonic systems in quantum theory (81V73) Quantum optics (81V80)

Abstract: Experimental demonstration of the quantum advantage over classical simulations with Boson Sampling is currently under intensive investigation. There seems to be a scalability issue to the necessary number of bosons on the linear optical platforms and the experiments, such as the recent Boson Sampling with $20$ photons on $60$-port interferometer by H.~Wang~ extit{et al}, extit{Phys. Rev. Lett.} extbf{123,} 250503 (2019), are usually carried out on a small interferometer, much smaller than the size necessary for the no-collision regime. Before demonstration of quantum advantage, it is urgent to estimate exactly how the classical computations necessary for sampling from the output distribution of Boson Sampling are reduced when a smaller-size interferometer is used. The present work supplies such a result, valid with arbitrarily close to $1$ probability, which reduces in the no-collision regime to the previous estimate by P.~Clifford and R.~Clifford. One of the results with immediate application to current experiments with Boson Sampling is that classically sampling from the interference of $N$ single bosons on an $M$-port interferometer is at least as hard as that with $mathcalN=fracN1+N/M$ single bosons in the no-collision regime, i.e., on a much larger interferometer with at least $mathcalMgg{N}^2$ ports.

Recommendations

• The classical complexity of boson sampling
• Boson sampling with non-identical single photons
• Towards quantum supremacy with lossy scattershot boson sampling
• Statistical benchmark for bosonsampling
• Sampling of bosonic qubits

Cites work

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons
• Computing the permanent of (some) complex matrices
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3621932 (Why is no real title available?)
• scientific article; zbMATH DE number 799789 (Why is no real title available?)
• Majorization and the time complexity of linear optical networks
• Mathematical Foundations of Computer Science 2005
• On Gospers formula for the Gamma function
• Probability Inequalities for Sums of Bounded Random Variables
• The classical complexity of boson sampling
• The complexity of computing the permanent
• The computational complexity of linear optics
• The permanent of a square matrix
• The quantum computer puzzle
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(12)

• The classical complexity of boson sampling
• Nosé-Hoover sampling of quantum entangled distribution functions
• Partial distinguishability as a coherence resource in boson sampling
• Classical benchmarking of Gaussian boson sampling on the Titan supercomputer
• Multi-boson correlation sampling
• Boson sampling with non-identical single photons
• Complex scattering as canonical transformation: A semiclassical approach in Fock space
• Majorization and the time complexity of linear optical networks
• Sampling of bosonic qubits
• Statistical benchmark for bosonsampling
• Towards quantum supremacy with lossy scattershot boson sampling
• Fast and memory-efficient strong simulation of noisy adaptive linear optical circuits

This page was built for publication: On the classical complexity of sampling from quantum interference of indistinguishable bosons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985083)