Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a uniform, shifted anticoncentration bound for the hafnian of $2n \times 2n$ complex symmetric Gaussian random matrices. Specifically, the authors prove that the probability of the normalized hafnian concentrating within an $\varepsilon$-radius disk around any arbitrary complex point $z$ is bounded by $2\sqrt{n/\pi}\,\varepsilon^2$. This provides a long-sought analytical component required to rigorously ground the average-case computational hardness of Gaussian boson sampling.
Hafnians of Gaussian random matrices resist clustering around any complex value, supplying the missing anticoncentration foundation needed to prove quantum advantage in Gaussian boson sampling.
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.