Optimal $e^{(\gamma +o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices

Abstract

We determine, up to lower-order terms in the exponent, the best possible deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite matrix. If $A⪰0$ has no zero diagonal entry, $d=\mathrm{rank}(A)$, $A=V{V}^{†}$ with $V\in {\mathbb{C}}^{n\times d}$ full column rank, and $v_1,\dots ,v_n$ are the rows of $V$, define \[ Φ(V)=\max_{X\succ 0} \left\{\sum_{i=1}^n \log(v_i^\dagger Xv_i)+\log\det X-\operatorname{tr} X+d\right\}, \qquad \widehat P(A)=e^{Φ(V)}. \] We prove the exact sandwich \[ e^{-γn}\widehat P(A)\le \operatorname{per}(A)\le \widehat P(A). \] Here $\gamma$ is the Euler--Mascheroni constant. Since the maximization is concave, this gives a deterministic polynomial-time $e^{(\gamma +\epsilon )n}$-approximation for every $\epsilon >0$. Combined with the previous $e^{(\gamma -\epsilon )n}$-hardness of approximation for positive semidefinite permanents, this resolves the optimal exponential approximation ratio for deterministic polynomial-time algorithms as $e^{(\gamma +o(1))n}$, assuming $\mathrm{P}\ne \mathrm{NP}$. The proof is an entropy argument applied to the standard Wick integral formula for $\mathrm{per}(A)$; the loss is exactly $\gamma$ per factor because $\mathbb{E}[\log T]=-\gamma$ for $T\sim \mathrm{Exp}(1)$. The result was obtained through interactions with GPT 5.5 Pro Extended: the first author's interaction was one-shot, while the second author's was a separate multi-turn interaction with high-level guidance. Both authors verified the theorem and proof. Codex was used to assemble and typeset the manuscript.