Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1811.10342 · Linear and Multilinear Algebra

Nonnegativity for hafnians of certain matrices

Kamil Brádler, Shmuel Friedland, Robert B. Israel

Published Feb 24, 2021• 2 citations
arXivHTMLPDF

Abstract

We show that a complex symmetric matrix of the form A(Y,B)=[YBB⊤Y¯], where B is Hermitian positive semidefinite, has a nonnegative hafnian. Some positive scalar multiples of matrices A(Y,B) are encodable in a Gaussian boson sampler. Further, the hafnian of this matrix is non-decreasing in B in the sense that hafA(Y,L)≥hafA(Y,B) if L⪰B.

DOI
10.1080/03081087.2021.1892022

Related papers

On randomized estimators of the Hafnian of a nonnegative matrix

Alexey Uvarov, Dmitry Vinichenko

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 nonnegative 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.

arXiv:2312.10143•Dec 15, 2023•0 citations

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

Alexey Uvarov, Dmitry Vinichenko

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.

Physical Review A•Apr 17, 2024•0 citations

Real Symmetric Matrices Larger Than a Hermitian Matrix: Applications to Gaussian Quantum Information Processing*

Shan Ma, Yuchen Xiong, Lihan Zhou +1 more

In this paper, we investigate the set of real symmetric matrices that are larger than a given Hermitian matrix in the semidefinite order, with particular attention to its minimal element. We explore the applications of this result in Gaussian quantum information processing. Furthermore, we propose potential research directions, especially the extension of this result to the set of real symmetric matrices that are larger than multiple given Hermitian matrices. These topics are of interest in both matrix theory and quantum information processing.

IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Jun 25, 2025•0 citations

Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry

Hongru Zhao

Local anticoncentration controls the conversion of additive output probability estimates to relative estimates in Gaussian boson sampling. We prove a center-uniform quadratic small-ball bound for hafnians of complex Gaussian transpose Gram matrices for $2n$ selected modes, with an explicit finite coefficient that is polynomial when the number of Gaussian rows is at least of order $n^2/\log n$. Letting the Gaussian row count tend to infinity yields anticoncentration for the independent complex symmetric Gaussian ensemble. For the transpose Gram hafnian bound, the proof compresses dependent hafnian cofactors by Fourier interpolation and controls their self-coupled variance through a conditional Wishart identity that preserves the transpose Gram coordinate. Independent perturbations satisfy related bounds, and a positive mixture density shows that the local quadratic power is exact. Together with the uniform hiding theorem in the companion paper, the result gives local anticoncentration for finite Haar interferometers.

math.PRCross-listedarXiv:2610.00112•Sep 10, 2026•0 citations

Anticoncentration of Complex Gaussian Hafnians

Priyanshu Pant

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.

arXiv:2609.35019•Sep 28, 2026•0 citations

Derivation of the Loop Hafnian Generating Function for Arbitrary Symmetric Matrices via Gaussian Integration

Sergey V. Tarasov

This short note shows that the recently proposed generating function for loop hafnians -- originally derived using quantum-optical methods for a restricted class of matrices -- is in fact valid for arbitrary symmetric matrices. The proof relies solely on Gaussian integration and does not assume any additional properties inherited from the covariance matrices of quantum Gaussian states.

arXiv:2507.16100•Jul 21, 2025•0 citations
We show that a complex symmetric matrix of the form A(Y,B)=[YBB⊤Y¯], where B is Hermitian positive semidefinite, has a nonnegative hafnian. Some positive scalar multiples of matrices A(Y,B) are encodable in a Gaussian boson sampler. Further, the hafnian of this matrix is non-decreasing in B in the sense that hafA(Y,L)≥hafA(Y,B) if L⪰B.
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 nonnegative 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.
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.
In this paper, we investigate the set of real symmetric matrices that are larger than a given Hermitian matrix in the semidefinite order, with particular attention to its minimal element. We explore the applications of this result in Gaussian quantum information processing. Furthermore, we propose potential research directions, especially the extension of this result to the set of real symmetric matrices that are larger than multiple given Hermitian matrices. These topics are of interest in both matrix theory and quantum information processing.
Local anticoncentration controls the conversion of additive output probability estimates to relative estimates in Gaussian boson sampling. We prove a center-uniform quadratic small-ball bound for hafnians of complex Gaussian transpose Gram matrices for 2n2n2n selected modes, with an explicit finite coefficient that is polynomial when the number of Gaussian rows is at least of order n2/log⁡nn^2/\log nn2/logn. Letting the Gaussian row count tend to infinity yields anticoncentration for the independent complex symmetric Gaussian ensemble. For the transpose Gram hafnian bound, the proof compresses dependent hafnian cofactors by Fourier interpolation and controls their self-coupled variance through a conditional Wishart identity that preserves the transpose Gram coordinate. Independent perturbations satisfy related bounds, and a positive mixture density shows that the local quadratic power is exact. Together with the uniform hiding theorem in the companion paper, the result gives local anticoncentration for finite Haar interferometers.
Let G2nG_{2n}G2n​ be a complex symmetric random matrix whose entries above the diagonal are independent standard circular complex Gaussians, and let Hn=haf⁡(G2n)H_n=\operatorname{haf}(G_{2n})Hn​=haf(G2n​). We prove the uniform shifted anticoncentration bound Pr⁡ ⁣(∣Hn(2n−1)!!−z∣≤ε)≤2nπ ε2 \Pr\!\left( \left| \frac{H_n}{\sqrt{(2n-1)!!}}-z \right| \le \varepsilon \right) \le 2\sqrt{\frac nπ}\,\varepsilon^2 Pr(​(2n−1)!!​Hn​​−z​≤ε)≤2πn​​ε2 for every z∈Cz\in\mathbb Cz∈C and ε>0\varepsilon>0ε>0. This establishes a local anticoncentration property that supports hardness arguments for quantum advantage in Gaussian boson sampling.