At first glance, the matrix permanent looks almost identical to the determinant. Both formulas sum over all possible permutations $\sigma$ of an $n \times n$ matrix's elements:
$$\text{det}(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n A_{i, \sigma(i)}$$
$$\text{per}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i, \sigma(i)}$$
The only difference is the omission of the sign bit, $\text{sgn}(\sigma)$. Yet this tiny algebraic modification changes everything. In the determinant, the alternating signs cause massive cancellations, creating a rich geometric structure that allows us to compute the value in polynomial time using Gaussian elimination. In the permanent, the lack of these cancellations forces us to confront the sheer combinatorial explosion of all $n!$ permutations.
As established by Travis Hance and Scott Aaronson, computing the permanent exactly is #P-complete, making it fundamentally harder than standard NP-complete problems. This stark contrast represents one of the deepest chasms in algebraic complexity theory, a benchmark for testing the limits of computation explored by Pranjal Dutta et al.. Because exact computation is intractable, a vast body of research focuses on finding clever ways to approximate it.
The Hardness Frontier
To understand why the permanent resists efficient computation, we have to look at its algebraic structure. In classical complexity, we separate problems into P and NP. In algebraic complexity, the equivalents are VP (polynomials that can be computed by small arithmetic circuits) and VNP (polynomials whose coefficients are easy to compute). The determinant is in VP, while the permanent is VNP-complete.
This hardness holds up even under severe structural constraints. For instance, Ankit Gupta et al. demonstrated that even if we restrict our computational model to depth-four arithmetic circuits with bounded bottom fan-in, computing the permanent still requires an exponential circuit size.
Even when we restrict the input matrices to specific mathematical families, the problem remains stubborn. For example, positive semidefinite (PSD) matrices are generally well-behaved in optimization because they guarantee non-negative outputs and lack sign conflicts. However, as noted by Nima Anari et al., the exact calculation of the permanent for PSD matrices remains strictly #P-hard.
Deterministic Approximations via Continuous Relaxations
If exact calculation is impossible, how close can we get deterministically? The core strategy is to transform the discrete, combinatorial problem of counting permutations into a continuous optimization problem.
One prominent approach leverages the Bethe approximation, a heuristic originating in statistical physics. The permanent of a non-negative matrix can be framed as calculating the partition function of a monomer-dimer system. By optimizing a continuous objective function over a relaxed space of fractional matchings (often related to making the matrix doubly stochastic via Sinkhorn scaling), we can obtain a deterministic estimate.
Alireza Rezaei and Nima Anari provided a tight analysis of this method, proving that the Bethe approximation yields a deterministic approximation factor of $\sqrt{2^n}$ for any non-negative matrix. To tighten this bound further, Yuwen Huang et al. introduced higher-degree Bethe and Sinkhorn permanent bounds, creating a systematic framework where the approximations scale monotonically toward the true permanent value.
Another way to see this connection between continuous optimization and the permanent is through linear forms. Chenyang Yuan and Pablo Parrilo showed that the permanent of a PSD matrix can be directly related to the problem of maximizing the product of linear forms over a convex domain, bridging the gap between non-convex optimization and combinatorial matrix theory.
Randomized Approximations and Deep Rejection Sampling
When deterministic bounds are too loose, randomized algorithms offer a way to achieve arbitrary precision $(\epsilon, \delta)$ at the expense of runtime. The standard approach is to use importance sampling or rejection sampling: we recursively choose entries from the matrix to build a permutation, weighting our choices to match the distribution of the permanent's terms.
However, naive sampling suffers from an exponential variance problem. If our sampling choices diverge from the true distribution, the algorithm will almost always sample permutations that contribute nothing to the total sum, leading to massive computational waste.
To solve this, modern algorithms use nesting upper bounds to guide the sampler. If we can efficiently compute a tight upper bound for the permanent of any submatrix, we can use these bounds to prune dead ends early or construct highly accurate proposal distributions.
Naive Sampling:
[Root] -> Choose Entry -> Choose Entry -> [Zero Term / Waste]
-> Choose Entry -> Choose Entry -> [Zero Term / Waste]
Deep Rejection Sampling:
[Root] -> Evaluate Nesting Bound -> [Prune / Avoid Dead End]
-> Evaluate Nesting Bound -> Follow High-Weight Path -> [Valid Term]
A series of developments have rapidly accelerated this mechanism:
- Adaptive Partitioning: Jonathan Kuck et al. developed ADAPART, which adaptively partitions the state space at runtime, verifying structural properties dynamically to draw exact samples without requiring a priori proofs.
- Look-Ahead Recursion: Juha Harviainen et al. introduced DeepAR (Deep Acceptance-Rejection). By using dynamic programming to look multiple levels deeper into the matrix's recursion tree, the algorithm computes significantly tighter upper bounds, accelerating the sampling rate by orders of magnitude.
- Hybrid Sampling: Juha Harviainen and Mikko Koivisto combined these deep nesting bounds with importance sampling (Nesting Importance Sampling). This hybrid approach retains the rigorous probabilistic accuracy guarantees of rejection sampling while achieving up to a 100x speedup. They further refined this in another work by introducing the Extended Huber bound, a tighter analytical tool that mitigates the exponential runtime growth typically triggered by adversarial matrix structures (the authors).
Islands of Tractability
While the general permanent is hard, certain structural constraints collapse the complexity entirely, offering exact closed-form solutions or highly efficient algorithms.
Graph Laplacians and Topology
In graph theory, the permanent of a graph's adjacency or Laplacian matrix counts specific structures like perfect matchings or cycle covers. While determining whether a graph's Laplacian spectrally dominates another is NP-hard (Alexandra Kolla et al.), restricting the graph's topology makes the permanent tractable.
For example, Xiaolei Dong derived exact closed-form formulas for the Laplacian permanents of caterpillar trees. Similarly, Tingzeng Wu and X. L. Wang proved that while computing the permanent for an arbitrary unicyclic graph is #P-complete, its extremal values (the absolute maximum and minimum possible permanents within that family) can be precisely determined due to the tight constraints of the single-cycle topology.
Average-Case and Generalized Permanents
The hardness of the permanent is an asset for fields like quantum supremacy (e.g., Boson Sampling), which rely on the average-case hardness of computing permanents of random matrices. Zhengfeng Ji et al. advanced this domain by designing simpler, more flexible approximation algorithms specifically tailored for random matrices with vanishing mean entries.
Finally, researchers look at algebraic generalizations like the $\alpha$-permanent, which interpolates between the determinant ($\alpha = -1$) and the permanent ($\alpha = 1$). Yushu Zheng demonstrated that by mapping these functions to probabilistic "loop soups" and random Markov loops, one can derive explicit expansion formulas for matrices associated with graphs that lack complex cycles.
Key Foundational Work
The efficient evaluation of the hypergeometric function of a matrix argument (2006) — contributed 1 concept elements to this direction.
Holomorphic extensions of Laplacians and their determinants (2006) — contributed 1 concept elements to this direction.
Faster Subset Selection for Matrices and Applications (2013) — contributed 1 concept elements to this direction.