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:2302.08083

The Computational Complexity of Quantum Determinants

Hung, Shih-Han, En-Jui Kuo

Published Feb 16, 2023• 4 citations
arXivHTMLPDF

Abstract

In this work, we study the computational complexity of quantum determinants, a $q$-deformation of matrix permanents: Given a complex number $q$ on the unit circle in the complex plane and an $n\times n$ matrix $X$, the $q$-permanent of $X$ is defined as $$\mathrm{Per}_q(X) = \sum_{σ\in S_n} q^{\ell(σ)}X_{1,σ(1)}\ldots X_{n,σ(n)},$$ where $\ell(σ)$ is the inversion number of permutation $σ$ in the symmetric group $S_n$ on $n$ elements. The function family generalizes determinant and permanent, which correspond to the cases $q=-1$ and $q=1$ respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive $m$-th root of unity $q$ for odd prime power $m=p^k$, exactly computing $q$-permanent is $\mathsf{Mod}_p\mathsf{P}$-hard. This implies that an efficient algorithm for computing $q$-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing $q$-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing $q$-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from $1$-permanent to $q$-permanent for $O(1/n^2)$ points $z$ on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to $q$-permanents.

DOI
10.48550/arxiv.2302.08083

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

Quantum Computational Complexity of Matrix Functions

Santiago Cifuentes, Samson Wang, Thais de Lima Silva +2 more

We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function f and a Hermitian matrix A , we compute a matrix element of f ( A ) or a local measurement on f ( A ) | 0 ⟩ ⊗ n , with | 0 ⟩ ⊗ n being an n -qubit reference state vector, in both cases up to additive approximation error. We consider four functions—monomials, Chebyshev polynomials, the time evolution function, and the inverse function—and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm and sparsity), the approximation error, and function-specific parameters. We identify BQP- forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results, we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree poly ( n ) , both problems can be efficiently classically simulated when A has O ( log  n ) nonzero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP- in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity O ( log  n ) . Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.

arXiv:2410.13937•PRX Quantum•Mar 2, 2026•8 citations

The Computational Complexity of Ball Permutations

Scott Aaronson, Adam Bouland, Greg Kuperberg +1 more

Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find that the computational power of this model depends on the initial input states. More precisely, with a standard basis input state, we show how to approximate the amplitudes of this model within additive error using the model DQC1 (the class of problems solvable with one clean qubit), providing evidence that the model in this case is weaker than universal quantum computing. However, for specific choices of input states, the model is shown to be universal for BQP in an encoded sense. We use representation theory of the symmetric group to partially classify the computational complexity of this model for arbitrary input states. Interestingly, we find some input states which yield a model intermediate between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an integrable scattering problem in 1+1 dimensions. We show it is universal under postselection, if we allow intermediate destructive measurements and specific input states. Therefore, the existence of any classical procedure to sample from the output distribution of this model within multiplicative error implies collapse of polynomial hierarchy to its third level. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP. Moreover, we find a nondeterministic version of this model is NP-complete.

arXiv:1610.06646•Oct 21, 2016•8 citations

Permanents of matrix ensembles: computation, distribution, and geometry

Igor Rivin

We report on a computational and experimental study of permanents. On the computational side, we use the GPU to greaatly accelerate the computation of permanents over $\mathbb{C},$ $\mathbb{R},$ $\mathbb{F}_p$ and $\mathbb{Q}.$ First, for Haar-distributed unitary matrices~$U$, the permanent $\perm(U)$ follows a circularly-symmetric complex Gaussian distribution $\mathcal{CN}(0,σ^2)$ -- we confirm this via a number of tests for $n$ up to~23 with $50{,}000$ samples. The DFT matrix permanent is an extreme outlier for every prime $n\ge 7$. In contrast, for Haar-random \emph{orthogonal} matrices~$O$, the permanent $\perm(O)$ is approximately real Gaussian but with positive excess kurtosis that decays as~$O(1/n)$, indicating slower convergence. For matrices with Gaussian entries (GUE, GOE, Ginibre), the permanent follows an $α$-stable distribution with stability index $α\approx 1.0$--$1.4$, well below the Gaussian value $α=2$. We test Aaronson's conjecture that $|\perm(X)|^2$ is asymptotically lognormal for Gaussian~$X$: it is plausible for the complex Ginibre and GOE ensembles, but appears to fail for GUE and real Ginibre, where the $α$-stable tails prevent convergence. Anti-concentration, however, holds for all Gaussian ensembles and is more robust than for Haar unitaries. Secondly, we study the permanent along geodesics on the unitary group. For the geodesic from the identity to the $n$-cycle permutation matrix, we find a universal scaling function $f(t)=\frac{1}{n}\ln|\perm(γ(t))|$ that is independent of~$n$ in the large-$n$ limit, with a midpoint value \[ \perm(γ({\textstyle\frac12})) = (-1)^{(n-1)/2}\cdot 2e^{-n}\bigl(1+\tfrac{1}{3n}+O(n^{-2})\bigr) \] for odd~$n$ and zero for even~$n$. We also study the geodesic forom the identity to the DFT matrix.

quant-pharXiv:2602.10141•Feb 10, 2026

New Hardness Results for the Permanent Using Linear Optics

Daniel Grier, Luke Schaeffer

In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques. First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_{p^4} for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan. Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.

arXiv:1610.04670•Leibniz international proceedings in informatics•Oct 15, 2016•13 citations

Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling

Sepehr Nezami

Computing the distribution of permanents of random matrices has been an outstanding open problem for several decades. In quantum computing, "anti-concentration" of this distribution is an unproven input for the proof of hardness of the task of boson-sampling. We study permanents of random i.i.d. complex Gaussian matrices, and more broadly, submatrices of random unitary matrices. Using a hybrid representation-theoretic and combinatorial approach, we prove strong lower bounds for all moments of the permanent distribution. We provide substantial evidence that our bounds are close to being tight and constitute accurate estimates for the moments. Let $U(d)^{k\times k}$ be the distribution of $k\times k$ submatrices of $d\times d$ random unitary matrices, and $G^{k\times k}$ be the distribution of $k\times k$ complex Gaussian matrices. (1) Using the Schur-Weyl duality (or the Howe duality), we prove an expansion formula for the $2t$-th moment of $|Perm(M)|$ when $M$ is drawn from $U(d)^{k\times k}$ or $G^{k\times k}$. (2) We prove a surprising size-moment duality: the $2t$-th moment of the permanent of random $k\times k$ matrices is equal to the $2k$-th moment of the permanent of $t\times t$ matrices. (3) We design an algorithm to exactly compute high moments of the permanent of small matrices. (4) We prove lower bounds for arbitrary moments of permanents of matrices drawn from $G^{ k\times k}$ or $U(k)$, and conjecture that our lower bounds are close to saturation up to a small multiplicative error. (5) Assuming our conjectures, we use the large deviation theory to compute the tail of the distribution of log-permanent of Gaussian matrices for the first time. (6) We argue that it is unlikely that the permanent distribution can be uniquely determined from the integer moments and one may need to supplement the moment calculations with extra assumptions to prove the anti-concentration conjecture.

arXiv:2104.06423•Apr 13, 2021•15 citations
In this work, we study the computational complexity of quantum determinants, a qqq-deformation of matrix permanents: Given a complex number qqq on the unit circle in the complex plane and an n×nn\times nn×n matrix XXX, the qqq-permanent of XXX is defined as Perq(X)=∑σ∈Snqℓ(σ)X1,σ(1)…Xn,σ(n),\mathrm{Per}_q(X) = \sum_{σ\in S_n} q^{\ell(σ)}X_{1,σ(1)}\ldots X_{n,σ(n)},Perq​(X)=∑σ∈Sn​​qℓ(σ)X1,σ(1)​…Xn,σ(n)​, where ℓ(σ)\ell(σ)ℓ(σ) is the inversion number of permutation σσσ in the symmetric group SnS_nSn​ on nnn elements. The function family generalizes determinant and permanent, which correspond to the cases q=−1q=-1q=−1 and q=1q=1q=1 respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive mmm-th root of unity qqq for odd prime power m=pkm=p^km=pk, exactly computing qqq-permanent is ModpP\mathsf{Mod}_p\mathsf{P}Modp​P-hard. This implies that an efficient algorithm for computing qqq-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing qqq-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing qqq-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from 111-permanent to qqq-permanent for O(1/n2)O(1/n^2)O(1/n2) points zzz on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to qqq-permanents.
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.
We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function f and a Hermitian matrix A , we compute a matrix element of f ( A ) or a local measurement on f ( A ) | 0 ⟩ ⊗ n , with | 0 ⟩ ⊗ n being an n -qubit reference state vector, in both cases up to additive approximation error. We consider four functions—monomials, Chebyshev polynomials, the time evolution function, and the inverse function—and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm and sparsity), the approximation error, and function-specific parameters. We identify BQP- forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results, we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree poly ( n ) , both problems can be efficiently classically simulated when A has O ( log  n ) nonzero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP- in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity O ( log  n ) . Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.
Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find that the computational power of this model depends on the initial input states. More precisely, with a standard basis input state, we show how to approximate the amplitudes of this model within additive error using the model DQC1 (the class of problems solvable with one clean qubit), providing evidence that the model in this case is weaker than universal quantum computing. However, for specific choices of input states, the model is shown to be universal for BQP in an encoded sense. We use representation theory of the symmetric group to partially classify the computational complexity of this model for arbitrary input states. Interestingly, we find some input states which yield a model intermediate between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an integrable scattering problem in 1+1 dimensions. We show it is universal under postselection, if we allow intermediate destructive measurements and specific input states. Therefore, the existence of any classical procedure to sample from the output distribution of this model within multiplicative error implies collapse of polynomial hierarchy to its third level. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP. Moreover, we find a nondeterministic version of this model is NP-complete.
We report on a computational and experimental study of permanents. On the computational side, we use the GPU to greaatly accelerate the computation of permanents over C,\mathbb{C},C, R,\mathbb{R},R, Fp\mathbb{F}_pFp​ and Q.\mathbb{Q}.Q. First, for Haar-distributed unitary matrices~UUU, the permanent $\perm(U)$ follows a circularly-symmetric complex Gaussian distribution CN(0,σ2)\mathcal{CN}(0,σ^2)CN(0,σ2) -- we confirm this via a number of tests for nnn up to~23 with 50,00050{,}00050,000 samples. The DFT matrix permanent is an extreme outlier for every prime n≥7n\ge 7n≥7. In contrast, for Haar-random \emph{orthogonal} matrices~OOO, the permanent $\perm(O)$ is approximately real Gaussian but with positive excess kurtosis that decays as~O(1/n)O(1/n)O(1/n), indicating slower convergence. For matrices with Gaussian entries (GUE, GOE, Ginibre), the permanent follows an ααα-stable distribution with stability index α≈1.0α\approx 1.0α≈1.0--1.41.41.4, well below the Gaussian value α=2α=2α=2. We test Aaronson's conjecture that $|\perm(X)|^2$ is asymptotically lognormal for Gaussian~XXX: it is plausible for the complex Ginibre and GOE ensembles, but appears to fail for GUE and real Ginibre, where the ααα-stable tails prevent convergence. Anti-concentration, however, holds for all Gaussian ensembles and is more robust than for Haar unitaries. Secondly, we study the permanent along geodesics on the unitary group. For the geodesic from the identity to the nnn-cycle permutation matrix, we find a universal scaling function $f(t)=\frac{1}{n}\ln|\perm(γ(t))|$ that is independent of~nnn in the large-nnn limit, with a midpoint value \[ \perm(γ({\textstyle\frac12})) = (-1)^{(n-1)/2}\cdot 2e^{-n}\bigl(1+\tfrac{1}{3n}+O(n^{-2})\bigr) \] for odd~nnn and zero for even~nnn. We also study the geodesic forom the identity to the DFT matrix.
In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques. First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_{p^4} for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan. Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.
Computing the distribution of permanents of random matrices has been an outstanding open problem for several decades. In quantum computing, "anti-concentration" of this distribution is an unproven input for the proof of hardness of the task of boson-sampling. We study permanents of random i.i.d. complex Gaussian matrices, and more broadly, submatrices of random unitary matrices. Using a hybrid representation-theoretic and combinatorial approach, we prove strong lower bounds for all moments of the permanent distribution. We provide substantial evidence that our bounds are close to being tight and constitute accurate estimates for the moments. Let U(d)k×kU(d)^{k\times k}U(d)k×k be the distribution of k×kk\times kk×k submatrices of d×dd\times dd×d random unitary matrices, and Gk×kG^{k\times k}Gk×k be the distribution of k×kk\times kk×k complex Gaussian matrices. (1) Using the Schur-Weyl duality (or the Howe duality), we prove an expansion formula for the 2t2t2t-th moment of ∣Perm(M)∣|Perm(M)|∣Perm(M)∣ when MMM is drawn from U(d)k×kU(d)^{k\times k}U(d)k×k or Gk×kG^{k\times k}Gk×k. (2) We prove a surprising size-moment duality: the 2t2t2t-th moment of the permanent of random k×kk\times kk×k matrices is equal to the 2k2k2k-th moment of the permanent of t×tt\times tt×t matrices. (3) We design an algorithm to exactly compute high moments of the permanent of small matrices. (4) We prove lower bounds for arbitrary moments of permanents of matrices drawn from Gk×kG^{ k\times k}Gk×k or U(k)U(k)U(k), and conjecture that our lower bounds are close to saturation up to a small multiplicative error. (5) Assuming our conjectures, we use the large deviation theory to compute the tail of the distribution of log-permanent of Gaussian matrices for the first time. (6) We argue that it is unlikely that the permanent distribution can be uniquely determined from the integer moments and one may need to supplement the moment calculations with extra assumptions to prove the anti-concentration conjecture.