Hafnians, perfect matchings and Gaussian matrices

Abstract

We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with nonnegative entries. We introduce a condition under which the Barvinok estimator achieves subexponential errors, and show that this condition is almost optimal. Using that hafnians count the number of perfect matchings in graphs, we conclude that Barvinok's estimator gives a polynomial-time algorithm for the approximate (up to subexponential errors) evaluation of the number of perfect matchings.

Published at http://dx.doi.org/10.1214/15-AOP1036 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Concentration of permanent estimators for certain large matrices

Cited by in corpus (13)

• Using Gaussian Boson Sampling to Find Dense Subgraphs
• Gaussian Boson Sampling for perfect matchings of arbitrary graphs
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• Solving Graph Problems Using Gaussian Boson Sampling
• Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• A novel approach to perturbative calculations for a large class of interacting boson theories
• Approximating outcome probabilities of linear optical circuits
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Unified boson sampling
• Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs