Behavior Modeling of Boson Sampling and Quantitative Analyses of Its Complexity

Subjects: Information Science and Systems Science >> Simulation Science and Technology submitted time 2021-04-22

张武荣

Abstract： We prove that the number of samples required for Gaussian Boson Sampling problem is exponentially increasing so that the problem is NP-hard for a linear optical device that uses classical sampling clock frequencies. We propose a new engineering scheme for the Gaussian Boson sampling problem to demonstrate the quantum supremacy: the scheme uses a combination of quantum true random number generator and a classic computer; the “build-in” quantum randomness is realized by the quantum true random number generator; a classic computer is used to simulate the sampling processes, thus the Gaussian Boson Sample problem is realized in an error-free manner, completing the computational tasks that cannot be accomplished by classical computer only, and ultimately proving the supremacy of quantum computing. The behavior level simulation scheme proposed in this paper can effectively simulate the stochastic characteristics of the Boson Sampling problem, and thus making it possible to verify the validity and correctness of the physical optical sampling device. "

Peer Review Status:Awaiting Review

 Hits 18756  Downloads 1273  Comment