Anticoncentration bounds support quantum advantage in boson sampling
Anticoncentration of Complex Gaussian Hafnians
Computational Complexity
Summary
This paper proves a mathematical bound that shows a certain random number associated with complex Gaussian matrices does not cluster too closely around any fixed point. The authors focus on the hafnian, a special function important in quantum physics problems like Gaussian boson sampling. Their result ensures that the hafnian values spread out enough, which is important to support the idea that some quantum computations are hard for classical computers to simulate. This finding helps strengthen the theoretical foundation behind claims of quantum advantage in specific quantum experiments.
What this means in practice
- •For quantum hardware engineers: Validate assumptions about output distributions in Gaussian boson sampling devices to support quantum advantage claims.
- •For quantum algorithm developers: Design algorithms and complexity arguments relying on the spread of hafnian distributions in Gaussian boson sampling models.
A theory result. No direct application yet.
Authors
Priyanshu Pant
Abstract
Let $G_{2n}$ be a complex symmetric random matrix whose entries above the diagonal are independent standard circular complex Gaussians, and let $H_n=\operatorname{haf}(G_{2n})$. We prove the uniform shifted anticoncentration bound $$ \Pr\!\left( \left| \frac{H_n}{\sqrt{(2n-1)!!}}-z \right| \le \varepsilon \right) \le 2\sqrt{\frac nπ}\,\varepsilon^2 $$ for every $z\in\mathbb C$ and $\varepsilon>0$. This establishes a local anticoncentration property that supports hardness arguments for quantum advantage in Gaussian boson sampling.