The Second Moment of Hafnians in Gaussian Boson Sampling
arXiv:2403.13878 · doi:10.1103/PhysRevA.111.042412
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 . 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.
16+18 pages, 8+9 figures, 0+3 tables
References in corpus (10)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum computational advantage using photons
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Computational advantage of quantum random sampling
- What can quantum optics say about computational complexity theory?
- Resources for bosonic quantum computational advantage
- Tight bounds on the convergence of noisy random circuits to the uniform distribution
- The Complexity of Bipartite Gaussian Boson Sampling
- Spoofing cross entropy measure in boson sampling
- Transition of Anticoncentration in Gaussian Boson Sampling