  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_{\sigma\in S_n}
q^{\ell(\sigma)}X_{1,\sigma(1)}\ldots X_{n,\sigma(n)},$$ 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\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.
