The Computational Complexity of Quantum Determinants

MaRDI QIDQ6426637zbMATH OpenFDO

Authors Shih-Han Hung, En-Jui Kuo

Publication date 15 February 2023

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 $nimesn$ matrix $X$, the $q$-permanent of $X$ is defined as ${\displaystyle }$mathrm{Per}_q(X) = sum_{sigmain S_n} q^{ell(sigma)}X_{1,sigma(1)}ldots X_{n,sigma(n)},${\displaystyle }$ where $ell(sigma)$ is the inversion number of permutation $sigma$ 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}mathsfP$-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.

This page was built for publication: The Computational Complexity of Quantum Determinants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426637)