Transition of Anticoncentration in Gaussian Boson Sampling

Abstract

Gaussian Boson Sampling is a promising method for experimental demonstrations of quantum advantage because it is easier to implement than other comparable schemes. While most of the properties of Gaussian Boson Sampling are understood to the same degree as for these other schemes, we understand relatively little about the statistical properties of its output distribution. The most relevant statistical property, from the perspective of demonstrating quantum advantage, is the anticoncentration of the output distribution as measured by its second moment. The degree of anticoncentration features in arguments for the complexity-theoretic hardness of Gaussian Boson Sampling, and it is also important to know when using cross-entropy benchmarking to verify experimental performance. In this work, we develop a graph-theoretic framework for analyzing the moments of the Gaussian Boson Sampling distribution. Using this framework, we show that Gaussian Boson Sampling undergoes a transition in anticoncentration as a function of the number of modes that are initially squeezed compared to the number of photons measured at the end of the circuit. When the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration. However, if the number of initially squeezed modes scales quickly enough, the output probabilities anticoncentrate weakly.

arXiv comment5+13 pages, 2+3 figures

References in corpus (15)

• Quantum computational advantage using photons
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Gaussian Boson Sampling
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Boson Sampling from Gaussian States
• A detailed study of Gaussian Boson Sampling
• Computational advantage of quantum random sampling
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• How many entries of a typical orthogonal matrix can be approximated by independent normals?
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• What can quantum optics say about computational complexity theory?
• Resources for bosonic quantum computational advantage
• Quantum approximate optimization with Gaussian boson sampling
• The Complexity of Bipartite Gaussian Boson Sampling
• The Second Moment of Hafnians in Gaussian Boson Sampling

Cited by in corpus (2)

• The Second Moment of Hafnians in Gaussian Boson Sampling
• Matrix phase-space representations for gaussian boson sampling