Summary
Calculating the permanent of a matrix is a hard math problem related to counting arrangements and patterns. The authors developed a reliable method that guesses the permanent value from a matrix without randomness. Their algorithm provides an estimate close to the real answer with error growing exponentially but controllably based on matrix size. It works efficiently and is predictable, helping in cases where previous approximations needed randomness.
What this means in practice
- •For quantum computing engineers: Approximate quantum state probabilities modeled by permanents without relying on randomized methods, enabling deterministic performance guarantees.
- •For statistical physics modelers: Use the algorithm to estimate complex partition functions that can be represented by permanents of nonnegative matrices for deterministic analytical approaches.
A theory result. No direct application yet.
Authors
Dingding Dong, Vishesh Jain
Abstract
For every fixed $0<\varepsilon\le1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in\mathbb{R}_{\ge0}^{n\times n}$, returns $Q$ satisfying $\operatorname{per} A\le Q\le(1+\varepsilon)^n\operatorname{per} A$.