Matrix permanent and determinant from a spin system

Abstract

In contrast to the determinant, no algorithm is known for the exact determination of the permanent of a square matrix that runs in time polynomial in its dimension. Consequently, noninteracting fermions are classically efficiently simulatable while noninteracting bosons are not, underpinning quantum supremacy arguments for sampling the output distribution of photon interferometer arrays. This work introduces a graph-theoretic framework that bridges both the determinant and permanent. The only nonzero eigenvalues of a sparse non-Hermitian operator $\stackrel{\ifmmode \u\else \textasciibreve \fi{}}{M}$ for $n$ spin-$1/2$ particles are the $n\mathrm{th}$ roots of the permanent or determinant of an $n\ifmmode\times\else\texttimes\fi{}n$ matrix $M$, interpreting basis states as bosonic or fermionic occupation states, respectively. This operator can be used to design a simple and straightforward method for the classical determination of the permanent that matches the efficiency of the best-known algorithm. Gauss-Jordan elimination for the determinant of $M$ is then equivalent to the successive removal of the generalized zero eigenspace of the fermionic $\stackrel{\ifmmode \u\else \textasciibreve \fi{}}{M}$, equivalent to the deletion of some nodes and reweighting of the remaining edges in the graph such that only $n$ nodes survive after the last step. In the bosonic case, the successive removal of generalized zero eigenspaces for $\stackrel{\ifmmode \u\else \textasciibreve \fi{}}{M}$ is also equivalent to node deletion, but new edges are added during this process, which gives rise to the higher complexity of computing the permanent. Our analysis may point the way to new strategies for classical and quantum evaluation of the permanent.