We present a randomized algorithm for estimating the permanent of an $M \times M$ real matrix $A$ up to an additive error. We do this by viewing the permanent $\mathrm{ perm}(A)$ of $A$ as the expectation of a product of centered joint Gaussian random variables with a particular covariance matrix $C$. The algorithm outputs the empirical mean $S_{ N}$ of this product after sampling $N$ times. Our algorithm runs in total time $O(M^{ 3} + M^{ 2}N + MN)$ with failure probability \begin{ equation*} P(|S_{ N}-\text{ perm}(A)| > t) \leq \frac{ 3^{ M}}{ t^{ 2}N} \prod^{ 2M}_{ i=1} C_{ ii}. \end{ equation*} In particular, we can estimate $\mathrm{ perm}(A)$ to an additive error of $\epsilon\bigg(\sqrt{ 3^{ 2M}\prod^{ 2M}_{ i=1} C_{ ii}}\bigg)$ in polynomial time. We compare to a previous procedure due to Gurvits. We discuss how to find a particular $C$ using a semidefinite program and a relation to the Max-Cut problem and cut-norms.
Categories: math.PR cs.DS math.CO quant-ph