Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2307.04681 · Physical Review A

Matrix permanent and determinant from a spin system

Abhijeet Alase, Owen Doty, David L. Feder

Published Jul 19, 2023• 3 citations
arXivHTMLPDF

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.

DOI
10.1103/physreva.108.012207

Related papers

Approximating the Permanent via Nonabelian Determinants

Cristopher Moore, Alexander C. Russell

Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671–697], we have known that the permanent of a matrix with entries in $\{0,1\}$ can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra $\mathcal{A}$ and considering the determinant of the resulting matrix. In the case where $\mathcal{A}$ is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first—and therefore the number of trials we need to obtain a good estimate of the permanent—is $(1 + O(1/d))^n$ when $\mathcal{A}$ is the algebra of $d \times d$ matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant—the only case in which an efficient algorithm is known—we show that the critical ratio exceeds $2^{n} / n^{O(d)}$. Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group.

arXiv:0906.1702•SIAM Journal on Computing•Jan 1, 2012•27 citations

Efficient computation of permanents, with applications to Boson sampling and random matrices

P. H. Lundow, Klas Markström

In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.

arXiv:1904.06229•Journal of Computational Physics•Jan 19, 2022•25 citations

Boson–fermion complementarity in a linear interferometer: An identity relating the determinant and permanent of a matrix

Michael G. Jabbour, Nicolas J. Cerf

Bosonic and fermionic statistics are well known to give rise to antinomic behaviors, most notably boson bunching vs fermion antibunching. Here, we establish a fundamental relation that combines bosonic and fermionic multiparticle interferences in an arbitrary linear interferometer. The bosonic and fermionic transition probabilities appear together in a single equation which constrains their values, hence expressing a boson–fermion complementarity that is independent of the details of the interferometer. For two particles in any interferometer, for example, it implies that the average between the bosonic and fermionic probabilities must coincide with the probability obeyed by classical particles. Crucially, this fundamental relation also provides a heretofore unknown mathematical identity connecting the squared moduli of the permanent and determinant of an arbitrary complex matrix, hence extending an identity by Muir dating from the nineteenth century.

arXiv:2312.17709•Journal of Mathematical Physics•May 1, 2026•1 citation

Polynomial computational complexity of matrix elements of finite-rank-generated single-particle operators in products of finite bosonic states

Dmitri A. Ivanov

It is known that computing the permanent of the matrix 1+A, where A is a finite-rank matrix, requires a number of operations polynomial in the matrix size. Motivated by the boson-sampling proposal of restricted quantum computation, I extend this result to a generalization of the matrix permanent: An expectation value in a product of a large number of identical bosonic states with a bounded number of bosons. This result complements earlier studies on the computational complexity in boson sampling and related setups. The proposed technique based on the Gaussian averaging is equally applicable to bosonic and fermionic systems. This also allows us to improve an earlier polynomial complexity estimate for the fermionic version of the same problem.

arXiv:2210.11568•SciPost Physics Core•Apr 22, 2024•0 citations

A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

Krishnakanta Barik, Goutam Paul

Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values $\braket{x|M|x}$, where $\ket{x}$ is a prepared eigenstate and $M$ is an observable. For an $n \times n$ $s$-sparse Hermitian matrix $H$, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in $\mathcal{O}(n^3)$ time. Exploiting sparsity, the Lanczos method computes all eigenvalues in $\mathcal{O}(n^2 s)$ time in exact arithmetic, but recovering all eigenvectors still requires $\mathcal{O}(n^3)$ time. In contrast, our algorithm runs in time $\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$, where $Δ_{\min}$ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to $Δ_{\min}^{-1} = \mathcal{O}(n)$, the most favorable scaling for $n$ distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to $s = o(\sqrt{n}/\log n)$, the proposed algorithm achieves an improved asymptotic runtime over the classical $\mathcal{O}(n^3)$ approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.

arXiv:2611.16610•Nov 12, 2026•0 citations

Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality

Frederic Koehler, Pui Kuen Leung

We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and \emph{boson sampling} (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial $\mathrm{per}(zJ + W)$, where $J$ is the all-ones matrix and $W$ is a random matrix with independent mean-zero entries. We show that when the entries of $W$ are standard complex Gaussians, all zeros of the random polynomial $\mathrm{per}(zJ + W)$ lie within a disk of radius $\tilde{O}(n^{-1/3})$, which yields an approximation algorithm when the bias of the entries is $\tildeΩ(n^{-1/3})$. Previously, there were no efficient algorithms at biases smaller than $1/\mathrm{polylog}(n)$, and it was unknown whether there typically exist zeros $z$ with $|z| \ge 1$. As a complementary result, we show that the bulk of the zeros, namely $(1 - ε)n$ of them, have magnitude $Θ(n^{-1/2})$. This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices $W$ with i.i.d. subexponential entries.

cs.DSCross-listedarXiv:2604.01367•Apr 3, 2026•3 citations
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 M\ifmmode\else˘\textasciibreve\fi\stackrel{\ifmmode \u\else \textasciibreve \fi{}}{M}M\ifmmode\else˘​\textasciibreve\fi​ for nnn spin-1/21/21/2 particles are the nthn\mathrm{th}nth roots of the permanent or determinant of an n\ifmmode×\else\texttimes\finn\ifmmode\times\else\texttimes\fi{}nn\ifmmode×\else\texttimes\fin matrix MMM, 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 MMM is then equivalent to the successive removal of the generalized zero eigenspace of the fermionic M\ifmmode\else˘\textasciibreve\fi\stackrel{\ifmmode \u\else \textasciibreve \fi{}}{M}M\ifmmode\else˘​\textasciibreve\fi​, equivalent to the deletion of some nodes and reweighting of the remaining edges in the graph such that only nnn nodes survive after the last step. In the bosonic case, the successive removal of generalized zero eigenspaces for M\ifmmode\else˘\textasciibreve\fi\stackrel{\ifmmode \u\else \textasciibreve \fi{}}{M}M\ifmmode\else˘​\textasciibreve\fi​ 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.
Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671–697], we have known that the permanent of a matrix with entries in {0,1}\{0,1\}{0,1} can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra A\mathcal{A}A and considering the determinant of the resulting matrix. In the case where A\mathcal{A}A is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first—and therefore the number of trials we need to obtain a good estimate of the permanent—is (1+O(1/d))n(1 + O(1/d))^n(1+O(1/d))n when A\mathcal{A}A is the algebra of d×dd \times dd×d matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant—the only case in which an efficient algorithm is known—we show that the critical ratio exceeds 2n/nO(d)2^{n} / n^{O(d)}2n/nO(d). Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group.
In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.
Bosonic and fermionic statistics are well known to give rise to antinomic behaviors, most notably boson bunching vs fermion antibunching. Here, we establish a fundamental relation that combines bosonic and fermionic multiparticle interferences in an arbitrary linear interferometer. The bosonic and fermionic transition probabilities appear together in a single equation which constrains their values, hence expressing a boson–fermion complementarity that is independent of the details of the interferometer. For two particles in any interferometer, for example, it implies that the average between the bosonic and fermionic probabilities must coincide with the probability obeyed by classical particles. Crucially, this fundamental relation also provides a heretofore unknown mathematical identity connecting the squared moduli of the permanent and determinant of an arbitrary complex matrix, hence extending an identity by Muir dating from the nineteenth century.
It is known that computing the permanent of the matrix 1+A, where A is a finite-rank matrix, requires a number of operations polynomial in the matrix size. Motivated by the boson-sampling proposal of restricted quantum computation, I extend this result to a generalization of the matrix permanent: An expectation value in a product of a large number of identical bosonic states with a bounded number of bosons. This result complements earlier studies on the computational complexity in boson sampling and related setups. The proposed technique based on the Gaussian averaging is equally applicable to bosonic and fermionic systems. This also allows us to improve an earlier polynomial complexity estimate for the fermionic version of the same problem.
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩\braket{x|M|x}⟨x∣M∣x⟩, where ∣x⟩\ket{x}∣x⟩ is a prepared eigenstate and MMM is an observable. For an n×nn \times nn×n sss-sparse Hermitian matrix HHH, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3)\mathcal{O}(n^3)O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s)\mathcal{O}(n^2 s)O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3)\mathcal{O}(n^3)O(n3) time. In contrast, our algorithm runs in time O~(ns2log⁡2n/Δmin⁡)\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})O~(ns2log2n/Δmin​), where Δmin⁡Δ_{\min}Δmin​ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin⁡−1=O(n)Δ_{\min}^{-1} = \mathcal{O}(n)Δmin−1​=O(n), the most favorable scaling for nnn distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/log⁡n)s = o(\sqrt{n}/\log n)s=o(n​/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3)\mathcal{O}(n^3)O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and \emph{boson sampling} (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial per(zJ+W)\mathrm{per}(zJ + W)per(zJ+W), where JJJ is the all-ones matrix and WWW is a random matrix with independent mean-zero entries. We show that when the entries of WWW are standard complex Gaussians, all zeros of the random polynomial per(zJ+W)\mathrm{per}(zJ + W)per(zJ+W) lie within a disk of radius O~(n−1/3)\tilde{O}(n^{-1/3})O~(n−1/3), which yields an approximation algorithm when the bias of the entries is Ω~(n−1/3)\tildeΩ(n^{-1/3})Ω~(n−1/3). Previously, there were no efficient algorithms at biases smaller than 1/polylog(n)1/\mathrm{polylog}(n)1/polylog(n), and it was unknown whether there typically exist zeros zzz with ∣z∣≥1|z| \ge 1∣z∣≥1. As a complementary result, we show that the bulk of the zeros, namely (1−ε)n(1 - ε)n(1−ε)n of them, have magnitude Θ(n−1/2)Θ(n^{-1/2})Θ(n−1/2). This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices WWW with i.i.d. subexponential entries.