Title | The Second Moment of Hafnians in Gaussian Boson Sampling |
Publication Type | Journal Article |
Year of Publication | 2024 |
Authors | Ehrenberg, A, Iosue, JT, Deshpande, A, Hangleiter, D, Gorshkov, AV |
Date Published | 3/20/2024 |
Abstract | Gaussian Boson Sampling is a popular method for experimental demonstrations of quantum advantage, but many subtleties remain in fully understanding its theoretical underpinnings. An important component in the theoretical arguments for approximate average-case hardness of sampling is anticoncentration, which is a second-moment property of the output probabilities. In Gaussian Boson Sampling these are given by hafnians of generalized circular orthogonal ensemble matrices. In a companion work [arXiv:2312.08433], we develop a graph-theoretic method to study these moments and use it to identify a transition in anticoncentration. In this work, we find a recursive expression for the second moment using these graph-theoretic techniques. While we have not been able to solve this recursion by hand, we are able to solve it numerically exactly, which we do up to Fock sector 2n=80. We further derive new analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device. |
URL | https://arxiv.org/abs/2403.13878 |