Universal Bound on Quantum Advantage in Gaussian Boson Sampling

The nature of the quantum complexity resource responsible for quantum advantage of Gaussian boson sampling simulator, that was widely studied theoretically and experimentally in the last decade as the top candidate for demonstrating quantum supremacy over classical computers, is revealed. It is shown that, according to the Hafnian Master Theorem, the quantum complexity originates from the $\sharp$P-hardness of computing a hafnian matrix function and is directly related to a geometrical complexity of Wigner quasi-probability distribution in the multimode phase space. An explicit, easy-to-compute formula for the resource’s complexity dimension determined by the photon number in this resource is established. It is proven that this formula provides a universal lower bound for the resource’s complexity dimension. Remarkably, numerical analysis shows that for typical experimental setups the proposed lower bound is quite accurate and differs from the exact value computed via direct numerical convex optimization only by about 20 percent. Moreover, if losses are the same for all modes, the formula gives the exact result.