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

Author(s)

Shchesnovich, V. S. ^[1]

Affiliation

^[1] Univ Fed ABC, Ctr Ciencias Nat & Humanas, BR-09210170 Santo Andre, SP - Brazil

• Document type: Journal article
• Source: INTERNATIONAL JOURNAL OF QUANTUM INFORMATION; v. 18, n. 7 OCT 2020.
• Web of Science Citations: 0

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 et al., Phys. Rev. Lett.123 (2019) 250503, 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. This work supplies such a result, valid with arbitrarily close to 1 probability, which reduces in the no-collision regime to the previous estimate by Clifford and 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 N = N/1+N/M single bosons in the no-collision regime, i.e. on a much larger interferometer with at least M >> N-2 ports. (AU)

• FAPESP's process: 18/24664-9 - Perspectives for quantum supremacy with Boson Sampling
• Grantee: Valery Shchesnovich
• Support Opportunities: Regular Research Grants