Wigner Distribution Sets Universal Lower Bound for Quantum Advantage in Gaussian Boson Sampling

The computational complexity, or quantum advantage, of Gaussian boson sampling is ascribed to squeezing of the Wigner quasiprobability distribution. This approach reveals the physical origin of the quantum complexity resource. This approach sets an easy-to-compute universal lower bound for the complexity dimension determined by the boson number in the quantum complexity resource. It is shown that the Wigner lower bound is close to the exact value of the complexity dimension obtained via numerical convex optimization. Our analytical and numerical results disclose a series of remarkable properties of quantum advantage.