The complexity of the fermionant, and immanants of constant width

Abstract

In the context of statistical physics, Chandrasekharan and Wiese recently introduced the \emph{fermionant} $\Ferm_k$, a determinant-like quantity where each permutation $\pi$ is weighted by $-k$ raised to the number of cycles in $\pi$. We show that computing $\Ferm_k$ is #P-hard under Turing reductions for any constant $k>2$, and is $\oplusP$-hard for $k=2$, even for the adjacency matrices of planar graphs. As a consequence, unless the polynomial hierarchy collapses, it is impossible to compute the immanant $\Imm_λ\,A$ as a function of the Young diagram $\lambda$ in polynomial time, even if the width of $\lambda$ is restricted to be at most 2. In particular, if $\Ferm_2$ is in P, or if $\Imm_λ$ is in P for all $\lambda$ of width 2, then $\NP \subseteq \RP$ and there are randomized polynomial-time algorithms for NP-complete problems.

7 pages, 1 figure

References in corpus (3)

• Inapproximability of the Tutte polynomial of a planar graph
• Complexity and Completeness of Immanants
• Partition Functions of Strongly Correlated Electron Systems as "Fermionants"

Cited by in corpus (5)

• Quantum simulation of partially distinguishable boson sampling
• Mixed Determinants and the Kadison-Singer problem
• The generalized fermion-bag approach
• On immanant functions related to Weyl groups of $A_n$
• Undirected determinant, permanent and their complexity