Performance of randomized estimators of the Hafnian of a non-negative matrix

Gaussian boson samplers aim to demonstrate quantum advantage by performing a sampling task believed to be classically hard. The probabilities of individual outcomes in the sampling experiment are determined by the Hafnian of an appropriately constructed symmetric matrix. For non-negative matrices, there is a family of randomized estimators of the Hafnian based on generating a particular random matrix and calculating its determinant. While these estimators are unbiased (the mean of the determinant is equal to the Hafnian of interest), their variance may be so high as to prevent an efficient estimation. Here we investigate the performance of two such estimators, which we call the Barvinok and Godsil-Gutman estimators. We find that, in general, both estimators perform well for adjacency matrices of random graphs, demonstrating a slow growth of variance with the size of the problem. Nonetheless, there are simple examples where both estimators show high variance, requiring an exponential number of samples. In addition, we calculate the asymptotic behavior of the variance for the complete graph. Finally, we simulate the Gaussian boson sampling using the Godsil-Gutman estimator and show that this technique can successfully reproduce low-order correlation functions.

Figure 1

Perfect matchings counted by the Hafnian function.

Figure 2

Examples of perfect 2-matchings. The one on the bottom right contains cycles of odd length; such 2-matchings do not contribute to the sum (3).

Figure 3

Examples of perfect 2-matchings formed by two permutations (orange arrows and black arrows). Note that if both permutations map two vertices to each other, they become connected by four arrows, meaning that the corresponding term in (4) has a fourth power in $g_{ij}$.

Figure 4

Average relative standard deviation $\sigma /\mu$ of (a) Godsil-Gutman and (b) Barvinok estimators for random graphs. Error bars denote confidence interval of one sigma, evaluated by bootstrap resampling and averaged over the sampled graphs.

Figure 5

Share of graph instances with Hafnian calculated up to relative error 0.05 using (a) Godsil-Gutman and (b) Barvinok estimators.

Figure 6

Relative standard deviation $\sigma /\mu$ of (a) Godsil-Gutman and (b) Barvinok estimators for the complete graphs of different sizes. The dashed line shows the exact values computed using the Taylor expansion of (B6), the dash-dotted line shows the asymptote as per Theorem t3.

Figure 7

Correlation functions for the GBS experiment obtained with Godsil-Gutman sampling versus those obtained with exact sampling. Top row: $N=10$; bottom row: $N=1000$.