The permanent of an $n \times n$ matrix looks deceptively similar to the determinant. Both compute a sum over all possible permutations of matrix entries. However, while the determinant alternates signs based on permutation parity—allowing it to be computed efficiently via Gaussian elimination—the permanent features no such cancellations. Every term is added directly.
This minor algebraic difference makes computing the permanent notoriously difficult ($\text{\#P}$-hard). While randomized algorithms can approximate the permanent of non-negative matrices efficiently, designing deterministic polynomial-time algorithms has long been a major hurdle. Historically, deterministic approximations suffered from loose, factorially growing errors ($n!$).
A recent wave of research has broken this barrier, developing deterministic algorithms that achieve simply exponential ($c^n$) or even tighter approximation ratios. By shifting from discrete counting to continuous optimization, these methods exploit the geometric and algebraic properties of matrix relaxations.
The Geometry of Relaxations
To understand why the permanent can be approximated deterministically, it helps to view it through the lens of matrix scaling. If we take a non-negative matrix and scale its rows and columns so that every row and column sums to 1, we obtain a doubly stochastic matrix.
By Van der Waerden's theorem, the permanent of any $n \times n$ doubly stochastic matrix is at least $n! / n^n \approx e^{-n}$. This scaling process (often called Sinkhorn normalization) provides a natural continuous relaxation of the problem. Because we can find this scaling efficiently, we instantly get a deterministic lower bound on the permanent.
The core challenge is controlling the upper bound: how far can the true permanent deviate from this continuous baseline?
Bridging the Gap with Gaussian Expectations
For positive semidefinite (PSD) matrices, a breakthrough by Nima Anari et al. in Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices proved that the gap between a matrix's relaxation and its true permanent is strictly bounded by a simply exponential factor ($\approx 4.84^n$).
The authors achieved this by reinterpreting the permanent as the expectation of a specific polynomial evaluated over complex Gaussian vectors:
$$\text{Perm}(A) = \mathbb{E}_{z \sim \mathcal{N}_c(0, I)} \prod_{i=1}^n \langle a_i, z \rangle|^2$$
By framing the permanent as a continuous expectation, the authors used the geometric properties of complex normal distributions to prove that the worst-case inflation from the relaxation is bounded by a constant raised to the power of $n$. This collapsed the deterministic approximation error from a factorial scale down to a manageable exponential one.
Building on this optimization perspective, Chenyang Yuan et al. in Maximizing Products of Linear Forms, and The Permanent of Positive Semidefinite Matrices connected the permanent to the problem of maximizing products of linear forms. By applying a randomized rounding strategy to a low-rank convex relaxation, the authors achieved a sub-exponential improvement over previous bounds, demonstrating that the space between tractable continuous relaxations and hard combinatorial values is narrower than previously assumed.
The Bethe Approximation and Entropy
For general non-negative matrices, an alternative framework comes from statistical physics: the Bethe approximation. This approach treats the matrix as a factor graph where rows and columns are nodes, and non-zero entries represent valid edges in a matching problem.
While Nicholas Ruozzi demonstrated in The Bethe Partition Function of Log-supermodular Graphical Models that variational frameworks consistently provide lower bounds for specific log-supermodular combinatorial problems, proving tight upper bounds for the permanent remained an open challenge.
This was resolved by Alireza Rezaei 0001 et al. in A Tight Analysis of Bethe Approximation for Permanent. The authors utilized an entropy-based measure to tightly bound the approximation quality, proving that the Bethe approximation yields a deterministic upper bound within a factor of $\sqrt{2^n}$. This settled a long-standing conjecture and significantly closed the performance gap between deterministic and randomized approximation algorithms.
[Exact Permanent] (Hard to compute)
▲
│ Bounded by √2ⁿ (Rezaei et al.)
▼
[Bethe Approximation] (Computed via Factor Graphs)
▲
│ Converges as M → ∞ (Huang et al.)
▼
[Degree-M Covers] (Structured intermediate bounds)
To understand the structural behavior of these bounds, Yuwen Huang et al. in Degree-M Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-Negative Matrix introduced intermediate approximations based on "degree-$M$ covers" of the underlying graph. These covers create a systematic ladder of approximations: as the degree $M$ approaches infinity, the combinatorial bounds converge directly to the standard Bethe and Sinkhorn permanents, offering a granular way to scale computational complexity against approximation accuracy.
Polynomial Stability and Derandomization
Another facet of this research direction leverages algebraic stability. Gurvits's original approximation algorithm relied on the theory of real stable polynomials—polynomials that do not have roots in the right half of the complex plane.
Shayan Oveis Gharan expanded this framework in A generalization of permanent inequalities and applications in counting and optimization, translating abstract stable polynomial properties into deterministic, polynomial-time algorithms for counting perfect matchings in graphs.
In parallel, Travis Hance et al. in Generalizing and derandomizing Gurvits's approximation algorithm for the permanent generalized this approach by reinterpreting formal variables as bosonic creation operators from quantum optics. Crucially, the authors successfully derandomized the algorithm for non-negative matrices. This provides a completely deterministic method with tight additive error guarantees, which becomes exceptionally efficient when dealing with matrices containing heavily repeated rows or columns.
Specialized Applications
The mathematical machinery developed for simply exponential approximations has found immediate utility in nearby fields:
- Statistical Estimation: In Approximate Profile Maximum Likelihood, Dmitri S. Pavlichin et al. bypassed the intractable permanent calculations required for distribution estimation. They achieved this by restricting the permutation space to "level sets"—grouping symbols with similar empirical counts together—to compute fast, highly accurate approximations.
- Average-Case Complexity: In Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler, Zhengfeng Ji et al. focused on random matrices. They developed a simpler, more flexible algorithmic framework that extends the tractability of permanent approximations to matrices with vanishingly small mean entries ($1/\text{polylog}(n)$), a boundary relevant to quantum supremacy verification.
By combining tools from quantum mechanics, statistical physics, and convex optimization, this research direction demonstrates that the permanent's combinatorial explosion can be tamed. Continuous relaxations do not merely provide loose baselines; when analyzed through entropy, stable polynomials, or Gaussian integration, they reveal a tight, deterministic path to approximating $\text{\#P}$-hard problems.
Key Foundational Work
Generalizing and derandomizing Gurvits's approximation algorithm for the permanent (2014) — contributed 3 concept elements to this direction.
The Bethe Partition Function of Log-supermodular Graphical Models (2012) — contributed 1 concept elements to this direction.