The Computational Complexity of Quantum Determinants

Shih-Han Hung¹¹1Department of Computer Science, University of Texas at Austin. Email: [email protected]. En-Jui Kuo²²2Joint Center for Quantum Information and Computer Science, NIST and University of Maryland, College Park, Maryland 20742, USA. Email:[email protected]

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_{\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.

1 Introduction

The study of matrix permanents has played an essential role in theoretical computer science and combinatorics. In a seminal work, Valiant proved that computing matrix permanent is ${\#\mathsf{P}}$ -hard, even if the matrix is over integers, non-negative integers or the set $\{0,1\}$ [Val79a]. This is considered to be one of the most influential results in computational complexity theory. These results have been used to justify of the hardness of other computational tasks in graph theory [Bro86, CX21] and matrix analysis [HJ12]. By contrast, matrix determinant is known to be polynomial-time computable from standard tools in elementary linear algebra [M⁺97].

An interesting observation is that both permanent and determinant of a matrix $X$ can be written as a polynomial in matrix elements with phase coefficients, i.e., they are elements on the unit circle in the complex plane. More specifically, both functions can be written as a summation of $q^{\ell(\sigma)}X_{1,\sigma(1)}\ldots X_{n,\sigma(n)}$ over permutations $\sigma$ on $n$ elements for a phase $q$ . Here $\ell(\sigma)$ is the inversion number of the permutation $\sigma$ , defined as the number of transpositions on adjacent elements applied to restore $\sigma(1),\ldots,\sigma(n)$ to its natural order $1,2,\ldots,n$ [Yan91]. In the case of permanent, $q=1$ , whereas in the case of determinant, $q=-1$ . However, given the expression of both functions in a unified form, what makes their computational complexities so different remains elusive.

A natural idea to explore this question is to study a $q$ -deformation of the matrix polynomial, connecting the cases $q\in\{-1,1\}$ . In mathematics literature, the $q$ -deformation on the unit circle or in $[-1,1]$ has been studied, and was given different names including $\mu$ -permanent, $q$ -permanent, $q$ -determinant, or quantum determinant [Yan91, BL94, Lal98, dF18, DF10, dS18, TAG93]. However, to our knowledge, none of these results discussed the complexity of computing the analogue. In this work, we focus on the unit circle, and study the computational complexity of the function defined as

\displaystyle\mathrm{Per}_{z}(X):=\sum_{\sigma\in S_{n}}z^{\ell(\sigma)}\prod_{i}X_{i,\sigma(i)}.

(1)

for the symmetric group $S_{n}$ on $n$ elements and a complex number $z$ such that $|z|=1$ . In the rest of the paper, for matrix $X$ , we will call $\mathrm{Per}_{z}(X)$ the $z$ -permanent of $X$ .

The $z$ -permanent is not the only $q$ -analogue of matrix permanents. In particular, immanants [Har85, Bür00, MM11, dRA13, Spi20, Cur21] and fermionants [MM11, BKW19, RA13, dRA13] are two families of functions that have been widely studied. They are both defined with class functions, i.e., for some function $f$ invariant under conjugation on the symmetric group, these function can be written in the form

\displaystyle\sum_{\sigma\in S_{n}}f(\sigma)X_{1,\sigma(1)}\ldots X_{n,\sigma(n)}.

(2)

For immanants, $f(\sigma)=\chi_{\lambda}(\sigma)$ where $\chi_{\lambda}$ is the character of the group representation $\lambda$ of $S_{n}$ . The permanent corresponds to the special case that $\chi_{\lambda}$ is the trivial representation, and the determinant corresponds to the sign representation. In a recent breakthrough, Curticapean classified the complexity of computing immanants for partition families. The complexity of immanants is settled down by proving that under plausible assumptions, for every partition family $\Lambda$ , matrix immanants are efficiently computable if and only if a quantity $b(\Lambda)$ , which counts the boxes to the right of the first column in the Young diagram of $\lambda\in\Lambda$ , is unbounded [Cur21]. For fermionants, $f(\sigma)=(-1)^{n}(-k)^{c(\sigma)}$ , where $c(\sigma)$ denotes the number of cycles in $\sigma$ . On the hardness side, Martins and Moore showed that fermionants are ${\#\mathsf{P}}$ -hard for $k>2$ under Turing reduction, and for $k=2$ , the problem is $\oplus\mathsf{P}$ -hard [MM11]. On the other hand, Björklund, Kaski, and Williams gave an algorithm in time $2^{m-\Omega(m/\log\log q))}\cdot O(\mathrm{M}(q))$ for $m\times m$ matrices over a finite field $\mathbb{F}_{q}$ of $q$ elements, where $\mathrm{M}(q)$ is the time complexity of multiplication and division over $\mathbb{F}_{q}$ [BKW19]. These results justify that these functions are computationally intractable in general, except in special cases.

However, to our knowledge, no classification of the complexity of $z$ -permanents has been given for any $z\notin\{-1,+1\}$ , and none of the aforementioned results seems to obviously imply the hardness for this family, partly because the inversion number is not a class function. In fact, no known complexity result for $q$ -deformations of matrix permanents has even been given beyond class functions.

In addition to the fact that the coefficients are not class functions, one may wonder why $z$ -permanent (also called quantum determinant) is interesting object to study? First, in representation theory, the standard Lie algebra can be generalized into the so-called $q$ -deformed algebra (also known as quantum group [Maj00]). Quantum determinants show up naturally in such contexts. More specifically, consider the $z$ -Grassmann algebra which is the associative algebra $K[z]$ generated by $x_{1},x_{2},...,x_{n}$ satisfying the $x_{i}^{2}=0$ for every $i\in[n]$ , and $x_{i}x_{j}=zx_{j}x_{i}$ for $i<j$ . It is straightforward to see that

\mathopen{}\mathclose{{}\left(\sum_{j=1}^{n}a_{1j}x_{j}}\right)\mathopen{}\mathclose{{}\left(\sum_{j=1}^{n}a_{2j}x_{j}}\right)\ldots\mathopen{}\mathclose{{}\left(\sum_{j=1}^{n}a_{nj}x_{j}}\right)=\mathrm{Per}_{z}(A)x_{1}x_{2}\ldots x_{n}.

(3)

which $A$ is $n$ by $n$ matrix such that $A_{ij}=a_{ij}$ . Quantum determinants also serve as an important object in the representation of such $q$ -deformed algebra [ER98], and are closely related to the representation theory over different characteristics. Second, it is known that there are many applications of quantum determinants in various areas of physics, including string theory [FK06] and conformal field theory [GRASRA96, PS90]. In quantum information theory, quantum determinants also play an essential role in the Fock representations of $q$ -deformed commutation relations [BLW17] or anyonic relation [GM04], generalizing the standard bosonic/fermionic commutation relation [BS91].

Motivated by the above observations, we initiate the study on the computational complexity of $z$ -permanents, by giving general hardness results for complex number $z$ on the unit circle. In the following sections, we give an overview of our contributions.

1.1 Our Contributions

In this paper, we study the computational complexity of $z$ -permanent for an $m$ -th primitive root of unity $z$ for integer $m>2$ . Our contribution is built upon tools from algebraic number theory. We summarize our result in Table 1. From Section 3 to Section 5, we prove one theorem in each section.

$z=\zeta_{p^{k}},\in{\displaystyle\mathbb{T}\setminus\{\pm 1\},}\|\mathrm{Per}_{z}(X)\|^{2}$	Exact	Approximate within multiplicative error $\operatorname{poly}(n)$
Worst case	Theorem 3.10	Theorem 4.2
Average case for $X\sim\mathcal{H}$	constant fraction Theorem 5.3	Theorem 6.4

Table 1: We list hardness results into common four categories and specify the four main theorems shown in this paper.

1.1.1 Worst-case Hardness

First, we study the hardness of computing $\zeta_{m}$ -permanent of a $n\times n$ binary matrix $X$ for an $m$ -th primitive root of unity $\zeta_{m}$ . By (1), we can write the $z$ -permanent as a polynomial in $z$ whose coefficients can be written as multivariate polynomials in the elements of $X$ . For $z\notin\{+1,-1\}$ , $z$ -permanent is in general a complex number which can be written as an integral polynomial in $z$ . Since complex number arithmetic can only be computed using a finite precision, we first clarify what it means by an algorithm computing $\mathrm{Per}_{z}(X)$ exactly.

While we do not know how to give a sensible definition for every $z$ on the unit circle, applying facts of cyclotomic fields yields a natural definition for a primitive root of unity and a binary matrix. More specifically, $\zeta_{m}$ -permanent of a binary matrix can be written as an integral polynomial in $\zeta_{m}$ of degree $d=\deg\Phi_{m}-1$ , where $\Phi_{m}$ is the $m$ -th cyclotomic polynomial. This implies that representing $\mathrm{Per}_{\zeta_{m}}(X)$ as a degree- $d$ polynomial, the tuple of coefficients is unique. Thus we define an algorithm which exactly computes $\mathrm{Per}_{\zeta_{m}}(X)$ to be one that outputs a set of coefficients $a_{0},\ldots,a_{d}$ such that $\mathrm{Per}_{\zeta_{m}}(X)=\sum_{i=0}^{d}a_{i}\zeta_{m}^{i}$ .

Given this definition, we show that for odd prime power $m=p^{k}$ , any oracle $\mathcal{O}$ that computes $\zeta_{m}$ -permanent implies that $\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}$ .

Theorem 1.1 (Hardness of $z$ -permanent, informal).

For odd prime $p$ , prime power $m=p^{k}$ and a primitive $m$ -th root of unity $\zeta_{m}$ , it is $\mathsf{Mod}_{p}\mathsf{P}$ -hard to compute $\zeta_{m}$ -permanent of $\{0,1\}$ -matrices. More explicitly, for every oracle $\mathcal{O}$ that on input a binary $n\times n$ matrix $X$ outputs the coefficients of $\mathrm{Per}_{\zeta_{m}}(X)$ , it holds that

\displaystyle\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}.

(4)

The first inequality in (4) follows from the generalized Toda’s theorem [TO92, Tod91]. To prove the second, we rely on the fact that for prime power $m=p^{k}$ , the cyclotomic polynomial evaluated on $1$ is $p$ . This means that the summation of the coefficients is congruent to $\mathrm{Per}(X)$ modulo $p$ . Then the second inequality follows from the fact that computing $\mathrm{Per}(X)$ modulo an odd prime is known to be $\mathsf{Mod}_{p}\mathsf{P}$ -hard by Valiant [Val79a].

While our definition of exact computation seems to be natural, one may wonder whether the requirement to output all the coefficients correctly would be too strong to allow the existence of efficient classical algorithms. We answer this question by studying hardness of approximating $\mathrm{Per}_{\zeta_{m}}(X)$ in $\ell_{2}$ -norm. In particular, we show that finding a close enough complex number to $\mathrm{Per}_{\zeta_{m}}(X)$ already suffices to extract all the coefficients using an $\mathsf{NP}$ oracle.

1.1.2 Hardness of Approximation

Next, we show that an oracle that approximates $\mathrm{Per}_{\zeta_{m}}(X)$ to within polynomial multiplicative error is also $\mathsf{Mod}_{p}\mathsf{P}$ -hard.

Theorem 1.2 (Hardness of approximation, informal).

For odd prime $p$ , prime power $m=p^{k}$ and a primitive $m$ -th root of unity $\zeta_{m}$ , it is $\mathsf{Mod}_{p}\mathsf{P}$ -hard to approximate $\zeta_{m}$ -permanent of $\{0,1\}$ -matrices. More explicitly, for every algorithm $\mathcal{O}$ that on input an $n\times n$ binary matrix $X$ , outputs an approximation to within multiplicative error $g=\operatorname{poly}(n)$ , it holds that

\displaystyle\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathsf{NP}^{\mathcal{O}}}.

(5)

Theorem 1.2 implies that an efficient simulation of $\mathcal{O}$ leads to a collapse of the polynomial hierarchy. The first inequality, again, follows from generalized Toda’s theorem [TO92, Tod91]. We then prove the second inequality in the following two steps. First, we show that there is a deterministic algorithm using polynomially many queries to $\mathcal{O}$ to decrease the error to $\delta=2^{-\operatorname{poly}(n)}$ in $\ell_{2}$ -norm. Our algorithm always output a complex number $\delta$ -close to $\mathrm{Per}_{\zeta_{m}}(X)$ successfully. However, this step alone does not yield a tuple of coefficients that satisfies our definition of exact computation. We overcome this issue by invoking a variant of Liouville’s approximation theorem. From the theorem, we show that two arbitrary algebraic integers, when represented as the minimal polynomial in $\zeta_{m}$ with coefficients in $[-A,B]$ for $A,B=2^{\operatorname{poly}(n)}$ must be $2^{-\operatorname{poly}(n)}$ -far in $\ell_{2}$ -distance. Using an oracle that determines whether there is a $\delta$ -close algebraic integer, we can perform a binary search to identify all the coefficients. Finally, we show determining whether there is an algebraic integer that is close enough to our approximation, and whose coefficients are bounded in $[-A,B]$ that can be solved using a non-deterministic Turing machine.

As a bonus, in Theorem 3.11, we give evidence that there is no polynomial algorithm for computing most of the roots of unity.

1.1.3 Average-Case Hardness of Exactly Computing $z$ -Permanent

For the average-case hardness of 1-permanent, Aaronson and Arkhipov [AA11] showed that under reasonable assumptions, computing $\mathrm{Per}(X)$ exactly for most of the Gaussian matrices is ${\#\mathsf{P}}$ -hard. Haferkamp, Hangleiter, Eisert, and Gluza [HHEG20] proved the hardness for most of the truncated uniform distribution.

In Section 5, we adapt their techniques to show that for every $z$ , if computing $z$ -permanent is hard in the worst case, via random self-reducibility, computing $z$ -permanent of Gaussian matrices is hard. This proof utilizes the Berlekamp-Welch algorithm and the fact that $z$ -permanent is a low-degree polynomial of its matrix elements.

Moreover, we extend the hardness results to a family of probability distributions that satisfy a property, called the strong autocorrelation property. Specifically, a random matrix is said to satisfy the strong autocorrelation property if the total variational distance between shifted or scaled original distribution and the original one is small (see Definition 5.2 for a detailed definition). We show that computing $z$ -permanent of matrices drawn from distributions satisfying this property remains to be ${\#\mathsf{P}}$ -hard. The hardness result can thus be applied to, for example, a uniform distribution centered around zero and truncated at some chosen threshold.

1.1.4 Average-Case Hardness of Approximating $z$ -Permanent

In Section 6, we show that if one can compute particular $\Omega(n^{2})$ points of $\mathrm{Per}_{z}(X)$ in time $\operatorname{poly}(n,1/\epsilon,1/\delta)$ , then one can determine $\mathrm{Per}(X)$ for $X$ sampled from a distribution $\mathcal{H}$ that satisfies the strong autocorrelation property. This implies that given a distribution $\mathcal{H}$ and $X\sim\mathcal{H}$ , approximating $\mathrm{Per}(X)$ is hard. Our results work for multiplicative and additive errors.

In addition, we also show that approximating $\mathrm{Per}_{z}(X)$ is as hard as approximating $\mathrm{Per}_{z^{*}}(X)$ for any distribution $X$ such that $X,X^{*}$ are identically distributed. The proof works for $|\mathrm{Per}_{z}(X)|^{2}$ as well.

1.2 Related Work

As we described in the introduction, permanent and determinant have completely different computational complexity. Any path that connects both cases is interesting from the point of computational complexity. More generally, one can consider such

\sum_{\nu\in S_{n}}f(\nu)\prod_{i=1}^{n}A_{i,\nu(i)}

(6)

function and ask the complexity of functions in the form of (6). People have already investigated a few function families including immanants [MM11, Har85, Bür00, dRA13, Spi20, Bür00] and fermionants [MM11, BKW19, RA13, dRA13]. However, our work is completely different from them in the following perspective:

•

Unlike immanants and fermionants, $z$ -permanent is not a class function. To our best knowledge, the complexity of such matrix function (6) has only been investigated when $f(\nu)$ is a class function. So one can not use the standard immanant results.
•

Since $z$ -permanent is not a class function, we provide completely new techniques involving algebraic number theory.
•

To our best knowledge, All results of approximate hardness in the worst case and average case are investigated for 1-permanent. For $f(\nu)\neq 1$ , no approximate hardness results are given previously in the literature. In Section 4, Section 5, and Section 6, we provide technical tools which lead to the results of approximate hardness for the general function $f$ .

1.3 Organization

The rest of the paper is structured as follows. A preliminary background is presented in Section 2. In Section 3, for worst-case hardness, we show that for primitive $m$ -th root of unity for odd prime power $m=p^{k}$ , exactly computing $z$ -permanent is $\mathsf{Mod}_{p}\mathsf{P}$ -hard. In Section 4, we show that efficiently approximating the $z$ -permanent of binary matrices implies a collapse of the polynomial hierarchy. In Section 5, based on the worst-case hardness, we give average-case hardness of exactly computing $z$ -permanent for a family of distributions satisfying the strong autocorrelation property. In Section 6, we move to the average-case hardness. Finally, in Section 7, we summarize our results and discuss a few open questions related to $z$ -permanent.

2 Preliminaries

2.1 Introduction to Algebraic Number Theory

Here we introduce some facts about field extension [Ben87] and algebraic number theory [Lan13, Neu13, Wei98] relevant to our work, although in this paper, we will only use facts about cyclotomic fields.

First, we recall basic definitions in abstract algebra and algebraic number theory. An abelian group is a set of elements closed under its group operation often denoted $+$ (for an additive group) or $\cdot$ (for a multiplicative group) and every element has an inverse. A commutative ring is an additive group that also has an associative multiplication operation and a multiplicative identity $1$ . A field is a ring, and its non-zero elements form an abelian multiplicative group. For example, the set $\mathbb{Q}$ of rational numbers is a field and the set $\mathbb{Z}$ of integers forms a ring.

A field $K$ is said to be an extension field (or simply extension), denoted $K/F$ , of field $F$ if $K$ contains $F$ as a subfield. The extension field $K$ can be viewed as a vector space over $F$ . The degree of the field extension $K/F$ , denoted $[K:F]$ , is the dimension of $K$ as a vector space of $F$ . Given a field $F$ and some value $\alpha$ , let $F(\alpha)$ , called $F$ adjoined $\alpha$ , be the smallest field containing $F$ and $\alpha$ . The operation of adjoining an element to a field is a field extension. For example, $K=\mathbb{Q}(\zeta_{3})=\{a+b\zeta_{3}:a,b\in\mathbb{Q}\}$ is an extension field of $\mathbb{Q}$ of degree two for $\zeta_{3}=e^{i2\pi/3}$ since every element of $K$ can be written as a vector of two components in $\mathbb{Q}$ . We also denote $\mathbb{Z}[x]$ for indeterminant $x$ the ring of polynomials with integer coefficients. For complex number $\alpha$ , the set $\mathbb{Z}[\alpha]=\{f(\alpha):f(x)\in\mathbb{Z}[x]\}$ forms a ring.

A number field is an extension field of $\mathbb{Q}$ of finite degree. We recall the definition of number fields and algebraic numbers.

Definition 2.1.

An algebraic number field (or simply number field) is an extension field $K$ of the field of rational numbers $\mathbb{Q}$ such that the field extension $K/\mathbb{Q}$ has finite degree (hence is an algebraic field extension).

Definition 2.2.

A complex number $x\in\mathbb{C}$ is an algebraic number if there exists a nonzero polynomial $f$ with rational coefficients (equivalently, integral) such that $x$ is a root of $f$ . The set of algebraic numbers $\bar{\mathbb{Q}}$ forms a subfield of $\mathbb{C}.$

Definition 2.3.

A complex number $x\in\mathbb{C}$ is an algebraic integer if there exists a nonzero monic polynomial $f$ (whose leading coefficient equals one) with integral coefficients such that $x$ is a root of $f$ .

The set of algebraic integer forms a subring of $\bar{\mathbb{Q}}$ . We also have $\alpha\in K$ is an algebraic integer if the minimal monic polynomial of $\alpha$ over $\mathbb{Q}$ is in $\mathbb{Z}[x]$ [Lan13]. We have a very simple fact about rational field and algebraic number using Gauss’s lemma.

Theorem 2.4 ([Lan13]).

Let $\mathcal{O}$ be the set of algebraic integers. The intersection of algebraic integers and $\mathbb{Q}$ is $\mathbb{Z}$ , i.e., $\mathbb{Q}\cap\mathcal{O}=\mathbb{Z}.$

Definition 2.5 (Ring of integers).

The ring of integers $\mathcal{O}_{K}$ of an algebraic number field $K$ is the ring of all algebraic integers contained in $K$ , i.e., $\mathcal{O}_{K}=\mathcal{O}\cap K$ .

The cyclotomic field is a number field obtained by adjoining a primitive root of unity to $\mathbb{Q}$ . In this paper, we denote $\zeta_{n}$ an $n$ th primitive root of unity for integer $n>1$ . Note that a choice of the primitive roots of unity is not unique. Indeed, for $n>1$ , $e^{2\pi ia/n}$ is a primitive root of unity if $\gcd(a,n)=1$ .

Definition 2.6 (Cyclotomic fields).

The $n$ th cyclotomic field is the extension $\mathbb{Q}(\zeta_{n})$ of $\mathbb{Q}$ generated by $\zeta_{n}$ . More explicitly:

\mathbb{Q}(\zeta_{n})=\mathopen{}\mathclose{{}\left\{\mathopen{}\mathclose{{}\left.\sum_{i=0}^{n-1}a_{i}\zeta_{n}^{i}}\right|a_{i}\in\mathbb{Q}}\right\}.

(7)

While there can be multiple choices of $\zeta_{n}$ , the field $\mathbb{Q}(\zeta_{n})$ is unique. This follows from a simple observation: Let $\zeta,\xi$ be two distinct $n$ th primitive roots of unity. Since there exists $a\in\{0,1,\ldots,n-1\}$ and $\gcd(a,n)=1$ such that $\xi=\zeta^{a}$ , $\mathbb{Q}(\xi)\subseteq\mathbb{Q}(\zeta)$ and thus they are equal. Similarly, we consider the ring

\mathbb{Z}[\zeta_{n}]=\mathopen{}\mathclose{{}\left\{\mathopen{}\mathclose{{}\left.\sum_{i=0}^{n-1}a_{i}\zeta_{n}^{i}}\right|a_{i}\in\mathbb{Z}}\right\}.

(8)

For cyclotomic field $\mathbb{Q}(\zeta_{n})$ , the ring of integers is $\mathbb{Z}[\zeta_{n}]$ .

Theorem 2.7 ([Lan13]).

For integer $n>1$ and $K=\mathbb{Q}(\zeta_{n})$ , $\mathcal{O}_{K}=K\cap\mathcal{O}=\mathbb{Z}[\zeta_{n}]$ .

We will need some useful properties about Euler’s totient function [Lan13].

Definition 2.8 (Euler’s totient function [Lan13]).

Euler’s totient function $\phi$ counts the number of positive integers up to a given integer $n$ that are relatively prime to $n$ . More explicitly, it can be computed through the following formula:

{\displaystyle\phi(n)=n\prod_{p\mid n}\mathopen{}\mathclose{{}\left(1-{\frac{1}{p}}}\right),}

(9)

where the product is over the distinct prime numbers dividing $n.$

We will need the following lower bound of $\phi(n)$ [RS62].

Theorem 2.9 ([RS62]).

For $n>2$ ,

\phi(n)>{\frac{n}{e^{\gamma}\;\log\log n+{\frac{3}{\log\log n}}}}.

(10)

simply speaking: the order of $\phi(n)$ is nearly $n$ . So this implies that we always have $\phi(\Omega(n^{c}))>n$ for any $c>1$ for large enough $n.$ Here $\gamma$ is Euler–Mascheroni constant.

For an $n$ th primitive root of unity $\zeta_{n}$ , the $n$ th cyclotomic polynomial $\Phi_{n}$ is the minimal polynomial of $\zeta_{n}$ over $\mathbb{Q}$ .

Definition 2.10 ([Lan12]).

For integer $n\geq 1$ , the $n$ th cyclotomic polynomial is defined as

{\displaystyle\Phi_{n}(x)=\prod_{\stackrel{{\scriptstyle 1\leq k\leq n}}{{\gcd(k,n)=1}}}\mathopen{}\mathclose{{}\left(x-e^{2i\pi{\frac{k}{n}}}}\right)}.

(11)

The polynomial $\Phi_{n}(x)$ has integer coefficients, i.e., $\Phi_{n}(x)\in\mathbb{Z}[x]$ .

We include some basic properties of cyclotomic polynomials useful in our work. Since $\Phi_{n}(x)$ is irreducible over $\mathbb{Q}$ , so it is the minimal polynomial of $\zeta_{n}$ over $\mathbb{Q}$ , the degree $[\mathbb{Q}(\zeta_{n}):\mathbb{Q}]=\text{deg }\Phi_{n}=\phi(n)$ . The minimal polynomial of every element in $\mathbb{Q}(\zeta_{n})$ over $\mathbb{Q}$ has degree at most $\phi(n)$ . The equivalent statement is that the following set $\{e^{2\pi aij/q}:0\leq j<\phi(q)\}$ is linearly independent over $\mathbb{Q}$ . For $n\geq 2$ ,

$\displaystyle\Phi_{n}(0)$	$\displaystyle=1,$
$\displaystyle\Phi_{n}(1)$	$\displaystyle=1,\quad\text{ if $n$ is not a prime power},$
$\displaystyle\Phi_{n}(1)$	$\displaystyle=p,\quad\text{ if $n=p^{k}$ is a prime power with $k\geq 1$.}$	(12)

Theorem 2.11 (Bounds for the coefficients of cyclotomic polynomials [Vau75]).

Let $\Phi_{n}(x):=\sum_{i=0}^{\phi(n)}a_{i}x^{i}$ be the $n$ th cyclotomic polynomial. The maximum absolute value of coefficient $a_{i}$ of $\Phi_{n}(x)$ satisfies

\max_{i\in\mathbb{N},0\leq i\leq\phi(n)}|a_{i}|\leq e^{\frac{1}{2}d(n)\log n},

(13)

where $d(n)$ is the divisor function which counts the number of divisors of $n$ (including $1$ and $n$ ) for integer $n\geq 1$ .³³3For instance, the divisors of $6$ are $1$ , $2$ , $3$ , and $6$ , and thus $d(6)=4$ .

For $n=p_{1}^{a_{1}}\ldots,p_{k}^{a_{k}}$ , $d(n)=(a_{1}+1)\ldots(a_{k}+1)$ . Since for prime $p\geq 2$ and integer $a\geq 1$ , $a+1\leq p^{a}$ , we can get the trivial bound $d(n)\leq n$ . By Theorem 2.11, we can represent $\Phi_{n}(x)$ using at most only $O(n\log n)$ bits.

The following theorem will be useful.

Theorem 2.12 (Liouville’s approximation theorem [LW12]).

Let $\alpha\in\mathbb{C}$ be an algebraic number with minimal polynomial $f(x)=a_{0}x^{d}+a_{1}x^{d-1}+..+a_{d}$ of degree $d$ . Then for any $a,b\in\mathbb{Z}$ that are relatively prime,

\mathopen{}\mathclose{{}\left|\alpha-\frac{a}{b}}\right|\geq\frac{1}{b^{d}a_{0}(2|\bar{\alpha}|+1)^{d-1}}

(14)

where $f(x)=a_{0}\prod_{\sigma}(x-\sigma(\alpha))$ , and $|\bar{\alpha}|$ the maximum complex modulus of the algebraic conjuguates of $\alpha$ in $\mathbb{C}$ , i.e., $|\bar{\alpha}|=\max|\sigma(\alpha)|$ .

In particular, since $0$ and $1$ are relatively prime, applying Theorem 2.12, for every algebraic number $\alpha$ whose minimal polynomial is $f(x)=a_{0}x^{d}+\ldots+a_{d}$ , $|\alpha|\geq\frac{1}{a_{0}(|\bar{\alpha}|+1)^{d-1}}$ . For two algebraic integers $\alpha,\beta\in\mathbb{Z}[\zeta_{n}]$ , $\alpha-\beta\in\mathbb{Z}[\zeta_{n}]$ , and $|\alpha-\beta|\geq\frac{1}{(|\overline{\alpha-\beta}|+1)^{\phi(n)-1}}$ .

Theorem 2.13 (Fermat’s little theorem [Wei04]).

Let $p$ be a prime number. Then for any integer $a$ , the number $a^{p}-a$ is an integer multiple of $p$ . In the notation of modular arithmetic, this is expressed as

a^{p}\equiv a\pmod{p}.

(15)

Theorem 2.13 implies

a^{p^{k}}\equiv a\pmod{p}.

(16)

for $k\geq 1$ since by Theorem 2.13, $a^{p^{k}}\equiv a^{p^{k-1}}\pmod{p}$ .

Theorem 2.14.

For field $F$ of characteristic $p$ and $a,b\in F$ ,

Proof.

By the binomial theorem,

(a+b)^{p}=a^{p}+\binom{p}{1}a^{p-1}b+\binom{p}{2}a^{p-2}b^{2}+...+\binom{p}{p-1}ab^{p-1}+b^{p}.

(17)

We just need the following Lemma: The prime $p$ divides each binomial coefficient $\binom{p}{r}$ for $1\leq r\leq p-1.$ The proof of lemma is simple by definition:

\binom{p}{r}=\frac{p\cdot(p-1)\cdot...\cdot(p-r+1)}{1\cdot 2\cdot...\cdot r}.

(18)

The result follows since $p$ divides the top but not the bottom. ∎

2.2 Properties of $z$ -permanent

Let $\mathbb{T}:=\{z\in\mathbb{C}:|z|=1\}$ be the unit circle in the complex plane. For matrix $X\in\mathbb{C}^{n\times n}$ , the $z$ -permanent of $X$ is defined as

\displaystyle\mathrm{Per}_{z}(X):=\sum_{\sigma\in S_{n}}z^{\ell(\sigma)}\prod_{i}X_{i,\sigma(i)},

(19)

where $S_{n}$ is the symmetric group on $n$ elements and $\ell(\sigma)$ is the inversion number of $\sigma$ . The inversion number is defined as the number of pairs $(i,j)$ such that $i<j$ and $\sigma(i)>\sigma(j)$ . It is clear that $\ell(\sigma)\leq\binom{n}{2}=\frac{1}{2}n(n-1)$ . This implies that we can write a $z$ -permanent as a polynomial in $z$ :

\displaystyle\mathrm{Per}_{z}(X)=\sum_{\ell=0}^{\binom{n}{2}}z^{\ell}\mathopen{}\mathclose{{}\left(\sum_{\sigma:\ell(\sigma)=\ell}\prod_{i=1}^{n}X_{i,\sigma(i)}}\right).

(20)

Note that by (20), $z$ -permanent is a polynomial with degree ${n\choose 2}$ in terms of $z.$

Here we list basic properties of $z$ -permanent [Yan91, DS] for every matrix $X\in\mathbb{C}^{n\times n}$ . Most of them are exact the same as permanent and determinant.

1.

$\mathrm{Per}_{z}(X)$ is a multilinear function of the rows and columns.
2.

For block triangular $X$ , $\mathrm{Per}_{z}(X)$ is the product of the $z$ -permanent of its diagonal blocks.
3.

$\mathrm{Per}_{z}(X)=\mathrm{Per}_{z}(X^{T})$ where $X^{T}$ is the transpose of $X$ .

(Expansion Theorem) Let $X^{ij}$ denote the $(i,j)$ minor of $X$ and $X_{ij}$ denote the element of $X.$ Then

\mathrm{Per}_{z}(X)=\sum_{k=1}^{n}X_{1k}z^{k-1}\mathrm{Per}_{z}(X^{1k})=\sum_{k=1}^{n}X_{jk}z^{k-1}\mathrm{Per}_{z}(X^{jk})

(21)

for $j=1,2,\ldots,n$ .

5.

For integer matrix $X$ and $n$ -th root of unity $z$ , $\mathrm{Per}_{z}(X)\in\mathbb{Z}[\zeta_{n}]$ . Thus, the minimal polynomial of $\mathrm{Per}_{z}(X)$ over $\mathbb{Q}$ has leading coefficient $1$ and its degree is at most $\phi(n)$ .

We give the explicit formula for the simplest case $n=2$ and $n=3$ : For $n=2$ ,

\displaystyle\mathrm{Per}_{z}(X)=(X_{11}X_{22}+X_{21}X_{12}z).

For $n=3$ ,

	$\displaystyle\mathrm{Per}_{z}(X)=X_{13}X_{22}X_{31}z^{3}+\mathopen{}\mathclose{{}\left(X_{12}X_{23}X_{31}+X_{13}X_{21}X_{32}}\right)z^{2}+$
	$\displaystyle\mathopen{}\mathclose{{}\left(X_{11}X_{23}X_{32}+X_{12}X_{21}X_{33}}\right)z+X_{11}X_{22}X_{33}.$

2.3 Common Tasks Related to Permanent

We recall the following task defined by Aaronson and Arkhipov [AA11]. We will discuss some of their generalizations in our paper.

Problem 1 ( $\mathrm{GPE}_{\times}$ ).

Given as input $X\sim\mathcal{N}_{\mathbb{C}}(0,1)^{n\times n}$ of i.i.d Gaussians (Complex normal distribution) and $\epsilon,\delta>0$ , estimate $\mathrm{Per}(X)$ to within error $\pm\epsilon|\mathrm{Per}(X)|$ to probability at least $1-\delta$ over $X$ .

Conjecture 1.

$\mathrm{GPE}_{\times}$ is ${\#\mathsf{P}}$ -hard. In other words, if $\mathcal{O}$ is any oracle that solves $\mathrm{GPE}_{\times}$ , then $\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}$ .

Conjecture 2.

There exists a polynomial $p$ such that for positive integer $n$ , real number $\delta>0$ ,

\displaystyle\Pr_{X}\mathopen{}\mathclose{{}\left[|\mathrm{Per}(X)|^{2}\geq\frac{\sqrt{n!}}{p(n,1/\delta)}}\right]\geq 1-\delta.

(22)

3 Hardness of $z$ -permanent for $\{0,1\}$ -matrices

In this section, we investigate the hardness of $z$ -permanent. We only consider the case that $z$ is root of a unity, i.e., there is positive integer $m$ such that $z^{m}=1$ , for the following two reasons. First, the set $\{z=e^{2\pi ia/b}:a,b\in\mathbb{N}\}$ is dense on the unit circle, so for every $z\in\mathbb{T}$ , there exists an arbitrarily close element in this set. Second, from the computational point of view, as we will see, it is more relevant and convenient to give a definition of exact computation with a rational multiple of $2\pi$ . Thus, in this paper, we always assume that $z$ is root of a unity, and write $z=\zeta_{m}$ for primitive $m$ -th root for unity for integer $m\geq 2$ .

We start with the cubic root of unity, showing that computing $z$ -permanant for $z$ satisfying $z^{3}=1$ is $\mathsf{Mod}_{3}\mathsf{P}$ -hard. Thus the existence of an algorithm for computing the $z$ -permanent implies the collapse of the polynomial hierarchy by Toda’s theorem.

3.1 Cube Roots of Unity

Recall that from algebraic number theory, for $z=\zeta_{p}$ and binary matrix $X\in\{0,1\}^{n\times n}$ , $\mathrm{Per}_{z}(X)$ can be written as a polynomial in $z$ :

\displaystyle\mathrm{Per}_{z}(X)=\sum_{k}A_{k}z^{k},

(23)

where $A_{k}:=\sum_{\sigma:\ell(\sigma)\equiv k\pmod{p}}\prod_{i=1}^{n}X_{i,\sigma(i)}$ . Furthermore, for $z=\zeta_{p}$ , $\mathrm{Per}_{z}(X)\in\mathbb{Z}[\zeta_{p}]$ , and thus is an algebraic integer in the number field $\mathbb{Q}[\zeta_{p}]$ . We will link the observation to hardness of computing $1$ -permanent and the complexity $\mathsf{Mod}_{p}\mathsf{P}$ , defined as follows.

Definition 3.1 ( $\mathsf{Mod}_{k}\mathsf{P}$ ).

For any integer $k\geq 2$ , let $\mathsf{Mod}_{k}\mathsf{P}$ be the class of decision problems solvable by a polynomial time non-deterministic machine which rejects if the number of accepting paths is divisible by $k$ , and accepts otherwise. When $k=2$ , $\mathsf{Mod}_{k}\mathsf{P}$ is also known as parity $\mathsf{P}$ , and denoted $\oplus\mathsf{P}$ .

It is well known due to Valiant that computing $\mathrm{Per}(X)\bmod p$ is $\mathsf{Mod}_{p}\mathsf{P}$ -complete for prime $p>2$ [Val79a]. Interestingly, we can reduce the problem of computing $\mathrm{Per}(X)\bmod p$ to the problem of computing $\mathrm{Per}_{\zeta_{p}}(X)$ in the special case $p=3$ .

Theorem 3.2 (Valiant [Val79a]).

The problem of computing $\mathrm{Per}(M)\bmod p$ for a square matrix $M\in\mathbb{F}_{p}^{n\times n}$ is $\mathsf{Mod}_{p}\mathsf{P}$ -complete for any prime $p>2$ .

Now we state the theorem for this section.

Theorem 3.3.

For every cube roots of unity $\zeta$ , computing $\mathrm{Per}_{\zeta}(X)$ and $|\mathrm{Per}_{\zeta}(X)|^{2}$ are both $\mathsf{Mod}_{3}\mathsf{P}$ -hard.

Proof.

For $\zeta=1$ , the theorem holds due to Valiant [Val79a], and thus it suffices to prove the theorem for $\zeta\in\{e^{i2\pi/3},e^{i4\pi/3}\}$ . For $\zeta=e^{i2\pi/3}$ , we can write $\mathrm{Per}_{\zeta}(X)$ as

$\displaystyle\mathrm{Per}_{\zeta}(X)$	$\displaystyle=A_{0}+\zeta A_{1}+\zeta^{2}A_{2}$
	$\displaystyle=A_{0}+\mathopen{}\mathclose{{}\left(-\frac{1}{2}+\frac{\sqrt{3}i}{2}}\right)A_{1}+\mathopen{}\mathclose{{}\left(-\frac{1}{2}-\frac{\sqrt{3}i}{2}}\right)A_{2}$
	$\displaystyle=\frac{2A_{0}-A_{1}-A_{2}}{2}+i\sqrt{3}\frac{A_{1}-A_{2}}{2}$	(24)

If one can compute $\mathrm{Per}_{\zeta}(X)$ , then one can compute $\mathrm{Per}(X)\bmod 3$ by taking the real part of $\mathrm{Per}_{\zeta}(X)$ since

\displaystyle 2A_{0}-A_{1}-A_{2}\equiv 2\mathrm{Per}(X)\pmod{3},

(25)

and $2$ is a unit in the ring $\mathbb{Z}_{3}$ . The same reasoning holds for $\zeta=e^{i4\pi/3}$ by interchanging $i$ and $-i$ .

It was shown in Valiant’s original paper [Val79b] that the permanent modulo $m=2^{k}$ can be computed in time $n^{O(k)}$ , but for all $m\neq 2^{k}$ , it is $\mathsf{NP}$ -hard under randomized reductions [CX15, DJ21].

For $|\mathrm{Per}_{\zeta}(X)|^{2}$ , we observe that

\displaystyle|\mathrm{Per}_{\zeta}(X)|^{2}

\displaystyle\equiv|\mathrm{Per}(X)|^{2}\pmod{3}.

Thus we can obtain $|\mathrm{Per}(X)|^{2}\bmod 3$ if $|\mathrm{Per}_{\zeta}(X)|^{2}$ can be exactly computed. ∎

The generalized Toda’s theorem [TO92] states that a few counting classes are as hard as the polynomial hierarchy.

Theorem 3.4 (Toda theorem [Tod91, TO92]).

For prime $k>2$ , let $A$ be one of the counting classes $\mathsf{Mod}_{k}\mathsf{P},\mathsf{\#P},\mathsf{PP},$ or $\mathsf{GapP}$ . Then $\mathsf{PH}\subseteq\mathsf{BPP}^{A}$ .

By Toda’s theorem, we immediately have the following theorem.

Theorem 3.5.

For $\zeta\in\{1,e^{i2\pi/3},e^{i4\pi/3}\}$ , let $\mathcal{O}$ be any oracle oracle that on input binary matrix $X\in\{0,1\}^{n\times n}$ , outputs $\mathrm{Per}_{\zeta}(X)$ . Then

\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{Mod}_{3}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}.

(26)

In other words, if there is an efficient classical simulation of $\mathcal{O}$ , then the polynomial hierarchy collapses to the second level.

If the polynomial hierarchy is infinite, Theorem 3.5 excludes the existence of an efficient classical algorithm for exactly computing $\zeta$ -permanent.

3.2 Primitive $m$ th roots of unity for prime power $m$

Next, we turn our attention to any prime number $p=n^{O(1)}$ . Since in general $\mathrm{Per}_{\zeta_{p}}(X)$ can be an irrational number in the complex plane, any truncation in finite precision only results in an approximation. In this section, we focus the hardness of computing $\mathrm{Per}_{\zeta_{p}}(X)$ exactly, and thus the first question we must clarify is how we define “computing $\mathrm{Per}_{\zeta_{p}}(X)$ exactly” for binary $X$ .

For binary matrix $X$ , $A_{k}\in\mathbb{Z}$ (see (23)). Thus $\mathrm{Per}_{\zeta_{p}}(X)$ can be written as a polynomial in $\zeta_{p}$ of degree at most $p-1$ with integer coefficients. We can define an exact representation of $\mathrm{Per}_{\zeta_{p}}(X)$ as a set of coefficients.

Definition 3.6 (Representation of an algebraic integer).

A representation of algebraic integer $\alpha\in\mathbb{Z}[\zeta_{p}]$ is a tuple of integers $(b_{0},b_{1},\ldots,b_{p-1})$ satisfying

\displaystyle\alpha=b_{0}+b_{1}\zeta_{p}+\ldots b_{p-1}\zeta_{p}^{p-1}.

(27)

Note that the representation is not unique since $\zeta_{p}$ is a root of $f(x)=1+x+\ldots+x^{p-1}$ , and thus $\alpha+cf(\zeta_{p})=\alpha$ for any integer $c\in\mathbb{Z}$ .

In general, one can define a representation of algebraic integers $\alpha\in\mathbb{Z}[\zeta_{n}]$ for general $n$ in Definition 4.5. However, in this section, the Definition 3.6 is sufficient for showing the hardness. Notice that one can also define such representation by a tuple of integers $(b_{0},b_{1},\ldots,b_{p-2})$ satisfying $\alpha=b_{0}+b_{1}\zeta_{p}+\ldots b_{p-2}\zeta_{p}^{p-2}$ since one has $\zeta_{p}^{p-1}=-1-\zeta_{p}-\zeta_{p}^{2}-...-\zeta_{p}^{p-2}.$

An algorithm which computes $\mathrm{Per}_{\zeta_{p}}(X)$ exactly outputs a tuple of coefficients $(b_{0},\ldots,b_{p-1})\in\mathbb{Z}^{p}$ such that (27) holds. This definition is without loss of generality for our purpose. In Section 4.2, we will construct an algorithm that maps an approximation in the complex plane to an exact representation using an $\mathsf{NP}$ oracle.

Theorem 3.7.

For prime $p$ , let $\zeta_{p}$ be a primitive $p$ -th root of unity and $\mathcal{O}$ be any oracle that on input a binary matrix $X\in\{0,1\}^{n\times n}$ , outputs a representation of $\mathrm{Per}_{\zeta_{p}}(X)$ . Then $\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}$ .

Proof.

For a binary matrix $X$ , let the output of $\mathcal{O}(X)$ be $(a_{0},\ldots,a_{p-1})$ . Also, let $A_{i}$ be defined as in (23). By the correctness of $\mathcal{O}$ ,

\mathrm{Per}_{\zeta_{p}}(X)=\sum_{i=0}^{p-1}A_{i}\zeta_{p}^{i}=\sum_{i=0}^{p-1}a_{i}\zeta_{p}^{i}.

(28)

Note that it does not necessarily hold that for every $i$ , $A_{i}=a_{i}$ , but the polynomials are identical congruent to the minimal polynomial of $\zeta_{p}$ . In particular, for prime $p$ , since $0=\sum_{i}(A_{i}-a_{i})\zeta_{p}^{i}$ ,

\mathopen{}\mathclose{{}\left(\sum_{i=0}^{p-1}(A_{i}-a_{i})\zeta_{p}^{i}}\right)^{p}=\sum_{i=0}^{p-1}(A_{i}-a_{i})^{p}+ph=0

(29)

where $h\in\mathbb{Z}[\omega]$ . Since the left side of the equality

\displaystyle\sum_{i=0}^{p-1}(A_{i}-a_{i})^{p}=-ph

(30)

is an integer, $h\in\mathbb{Z}[\zeta_{p}]\cap\mathbb{Q}\subseteq\mathbb{Z}$ . This means that $p$ divides $\sum_{i}(A_{i}-a_{i})^{p}$ , and

$\displaystyle 0$	$\displaystyle\equiv\sum_{i=0}^{p-1}(A_{i}-a_{i})^{p}$
	$\displaystyle\equiv\sum_{i=0}^{p-1}A_{i}^{p}-\sum_{i=0}^{p-1}a_{i}^{p}$
	$\displaystyle\equiv\sum_{i=0}^{p-1}A_{i}-a_{i}\pmod{p}.$	(31)

The last equality holds from Fermat’s little theorem (Theorem 2.13).

In summary, given access to an oracle $\mathcal{O}$ which exactly computes $\mathrm{Per}_{\zeta_{p}}(X)$ for binary $X\in\{0,1\}^{n\times n}$ , the following algorithm computes $\mathrm{Per}(X)\bmod p$ :

•

Run $(a_{0},\ldots,a_{p-1})\leftarrow\mathcal{O}(X)$ .
•

Output $\sum_{i=0}^{p-1}a_{i}\bmod p$ .

∎

By Toda’s theorem Theorem 3.4, we have the following corollary.

Corollary 3.8.

For prime $p>3$ , let $\mathcal{O}$ denote any oracle which computes $\mathrm{Per}_{\zeta_{p}}(X)$ exactly for binary matrix $X\in\{0,1\}^{n\times n}$ . Then

\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}.

(32)

We can easily extend our result to a prime power $q=p^{k}$ for prime $p$ .

Theorem 3.9.

For prime $p$ and prime power $q=p^{k}$ , let $\zeta_{q}$ be a primitive $q$ -th root of unity and $\mathcal{O}$ be any oracle that on input a binary matrix $X\in\{0,1\}^{n\times n}$ , outputs an exact representation of $\mathrm{Per}_{\zeta_{q}}(X)$ . Then $\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}$ .

Proof.

The idea basically follows from the proof of Theorem 3.9. For $\zeta_{q}=e^{2\pi ia/q}$ and $\gcd(a,p)=1$ , we have

\mathopen{}\mathclose{{}\left(\sum_{i=0}^{q-1}(A_{i}-a_{i})\zeta_{q}^{i}}\right)^{q}=\sum_{i=0}^{q-1}(A_{i}-a_{i})^{q}+ph=0

(33)

where $h\in\mathbb{Z}[\omega]\cap\mathbb{Q}\subseteq\mathbb{Z}$ . We then use Fermat’s little theorem (Theorem 2.13) which imples that $a^{q}\equiv a(\bmod p)$ , and

\sum_{i=0}^{q-1}(A_{i}-a_{i})+ph=0.

(34)

So then we have (using finite field property Theorem 2.14)

\mathrm{Per}(X)\equiv\sum_{i=0}^{q-1}A_{i}\equiv\sum_{i=0}^{q-1}a_{i}\pmod{p},

(35)

which finish the proof. ∎

We end this section by summarizing the classical hardness of $\mathrm{Per}_{z}(X)$ for such particular $z$ .

Theorem 3.10.

For odd prime $p$ and prime power $q=p^{k}$ , let $\zeta_{q}$ be a primitive $q$ -th root of unity. Exactly computing $\zeta_{q}$ -permanent for binary matrices is not in $\mathsf{PH}$ ; otherwise, the polynomial hierarchy collapses. More precisely, for any oracles $\mathcal{O}$ which computes the $\zeta_{q}$ -permanent of binary matrices, the following containments hold:

\displaystyle\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{Mod}_{p}\mathsf{P}}\subseteq\mathsf{BPP}^{\mathcal{O}}.

Unfortunately, our method does not generalize to a primitive $m$ -th root of unity for $m$ divisible by more than one prime. While our result does not rule out the existence of an efficient solver for non-prime powers, it is interesting to see whether there exists a polynomial-time algorithm for any of these points. Since it is not so relevant to our result, we leave the complexity of computing general composite numbers as future work.

For $p=2$ , we notice that our method with oracle which computes $\zeta_{2^{k}}$ -permanent implies one can compute $\mathrm{Per}(X)\pmod{2}$ . However, since $\mathrm{Per}(X)\equiv\det(X)(\bmod 2),$ we do not have the hardness results for computing $\zeta_{2^{k}}$ -permanet Indeed, it is known that permanent modulo $2^{k}$ admits an efficient algorithm [DJ21, CX15]. Any hardness results for $\zeta_{2^{k}}$ -permanent cannot be implied by the hardness of permanent modulo $2^{k}$ .

Unfortunately, our method cannot be used to establish hardness for rational numbers with a non-prime-power denominator.

3.3 Hardness of Rational Phases

Recall that for every $z\in\mathbb{T}$ , the $z$ -permanent of a binary matrix is always an integral polynomial in $z$ of degree at most $\binom{n}{2}$ . For a primitive $m$ -th root of unity $z=\zeta_{m}$ , we can further reduce the degree by taking the congruence to the minimal polynomial of the degree of $\zeta_{m}$ , when $\phi(m)<\binom{n}{2}$ . In the previous sections, we have applied these facts to reduce the problem of computing $1$ -permanent modulo $m$ to $\zeta_{m}$ -permanent for prime power $m$ .

While we do not have a general result for every non-prime-power rational phases, in this section, we consider a special case where $\phi(m)\geq\binom{n}{2}$ . In this case, since the monomials $1,\zeta_{m},\zeta_{m}^{2},\ldots,\zeta_{m}^{\binom{n}{2}}$ are linearly indepenent, $1$ -permanent can be directly obtained from $\zeta_{m}$ -permanent.

Theorem 3.11.

Let $\mathcal{O}$ denote any oracle which input are binary matrix $X$ and $m:\mathbb{N}\to\mathbb{N}$ such that $\phi(m(n))\geq\binom{n}{2}+1$ , it outputs $\mathrm{Per}_{\zeta_{m}}(X)$ exactly. Then $\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{P}^{\mathcal{O}}$ .

Proof.

Let $d:=\binom{n}{2}$ . Computing $\mathcal{O}(m,X)$ yields a tuple of coefficients $(a_{0},\ldots,a_{d})$ satisfying

\mathrm{Per}_{\zeta_{m}}(X)=\sum_{i=0}^{d}A_{i}\zeta_{m}^{i}=\sum_{i=0}^{d}a_{i}\zeta_{m}^{i}.

(36)

where $A_{i}=\sum_{\sigma\in\mathbb{S}_{N},\ell(\sigma)=i}\mathopen{}\mathclose{{}\left(\prod_{j=1}^{n}X_{j,\sigma(j)}}\right)$ . Since the monimials $1,\zeta_{m},\ldots,\zeta_{m}^{d}$ are linearly dependent for $\phi(m)\geq d+1$ , $A_{i}=a_{i}$ for every $0\leq i\leq d$ . This implies that $\sum_{i=0}^{d}a_{i}=\mathrm{Per}_{m}(X)$ . ∎

However, for cases with non-prime-power $m=O(1)$ , neither of the methods seems to work. We leave the hardness of primitive $m$ -th roots of unity for fix non-prime-power $m$ as an open question.

4 Hardness of Approximating $\zeta_{m}$ -permanent

In Section 3, we have shown that for prime power $m=p^{k}$ for odd prime $p$ , exactly computing $\mathrm{Per}_{\zeta_{m}}(X)$ is as hard as computing $\mathrm{Per}(X)\bmod p$ . The task is known to be $\mathsf{Mod}_{p}\mathsf{P}$ -hard. In this section, we show that approximating $\mathrm{Per}_{\zeta_{m}}(X)$ for integer $m$ and binary matrices is as hard as exactly computing it.

In Section 4.1, we show that approximating $|\mathrm{Per}_{\zeta_{m}}(X)|^{2}$ to multiplicative error within $g=\operatorname{poly}(n)$ is as hard as approximating $\mathrm{Per}_{\zeta_{m}}(X)$ to multiplicative error $2^{-\operatorname{poly}(n)}$ , up to a polynomial multiplicative overhead. In Section 4.2, we show that with an $\mathsf{NP}$ oracle, exactly computing $\mathrm{Per}_{\zeta_{m}}(X)$ is as hard as approximating it to error $2^{-\operatorname{poly}(n)}$ . Combining the results in these two sections, we conclude that an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy.

4.1 Reducing the Error

In this section, we show that for a prime number $m$ and an $m$ -th primitive root of unity $\zeta_{m}$ , approximating $|\mathrm{Per}_{\zeta_{m}}(X)|^{2}$ to multiplicative error $g=n^{O(1)}$ is as hard as approximating $\mathrm{Per}_{\zeta_{m}}(X)$ to multiplicative error $1+2^{-n^{O(1)}}$ .

First we prove the following lemma which will be useful later.

Lemma 4.1.

For integer $n\geq 1$ and $\delta\leq\frac{1}{2n}$ , let $\alpha_{1},\ldots,\alpha_{n}$ be complex numbers and $\tilde{\alpha}_{1},\ldots,\tilde{\alpha}_{n}$ satisfying for $i\in[n]$ ,

\displaystyle|\alpha_{i}-\tilde{\alpha}_{i}|\leq\delta|\alpha_{i}|.

(37)

Then it holds that

\displaystyle|\alpha_{1}\ldots\alpha_{n}-\tilde{\alpha}_{1}\ldots\tilde{\alpha}_{n}|\leq 2n\delta|\alpha_{1}\ldots\alpha_{n}|.

(38)

Proof.

We prove the lemma by induction. For $n=1$ , the lemma obviously hold. Suppose that the lemma holds for $n=k$ . Then for $n=k+1$ , let $A:=\alpha_{1}\ldots\alpha_{k}$ and $\tilde{A}:=\tilde{\alpha}_{1}\ldots\tilde{\alpha}_{k}$ . By the inductive hypothesis, $|\tilde{A}-A|\leq 2k\delta|A|$ . Then

$\displaystyle\frac{\|\alpha_{k+1}A-\tilde{\alpha}_{k+1}\tilde{A}\|}{\|\alpha_{k+1}A\|}$	$\displaystyle\leq\frac{\|\alpha_{k+1}-\tilde{\alpha}_{k+1}\|}{\|\alpha_{k+1}\|}+\frac{\|\tilde{\alpha}_{k+1}\|}{\|\alpha_{k}\|}\frac{\|A-\tilde{A}\|}{\|A\|}$
	$\displaystyle\leq\delta+(1+\delta)2k\delta$
	$\displaystyle\leq(2k+1)\delta+2k\delta^{2}$
	$\displaystyle\leq(2k+2)\delta.$	(39)

The first inequality holds by (37) and $|\tilde{\alpha}_{k+1}|\leq|\alpha_{k+1}-\tilde{\alpha}_{k+1}|+|\alpha_{k+1}|\leq(1+\delta)|\alpha_{k+1}|$ . The last inequality holds since $2k\delta^{2}\leq 2n\delta^{2}\leq\delta$ . ∎

We can decrease the error of our approximation algorithm from a multiplicative factor $g=n^{O(1)}$ to $1+2^{-n^{O(1)}}$ using a polynomial overhead.

Theorem 4.2.

For $g\in[1,\operatorname{poly}(n)]$ , prime number $m$ , and a primitive $m$ -th root of unity $\zeta_{m}$ , if there is an algorithm $\mathcal{O}$ which on input $X\in\{0,1\}^{n\times n}$ , approximates $|\mathrm{Per}_{\zeta_{m}}(X)|^{2}$ to within a multiplicative factor of $g$ , then there exists an algorithm which outputs an esatimate $\tilde{P}$ of $\mathrm{Per}_{\zeta_{m}}(X)$ satisfying

\displaystyle\frac{|\mathrm{Per}_{\zeta_{m}}(X)-\tilde{P}|}{|\mathrm{Per}_{\zeta_{m}}(X)|}\leq\epsilon

(40)

using $O(mn^{2}g^{4}\log n+ng^{4}\log g+ng^{4}\log(1/\epsilon))$ queries to $\mathcal{O}$ .

Proof.

Let $z=\zeta_{m}$ . We describe the algorithm $\mathcal{A}^{\mathcal{O}}$ as follows. First $\mathcal{A}^{\mathcal{O}}$ decides if $|\mathrm{Per}_{z}(X)|^{2}=0$ . If $|\mathrm{Per}_{z}(X)|^{2}\neq 0$ , then $\mathcal{O}$ returns a value

\displaystyle p\in[g^{-1}|\mathrm{Per}_{z}(X)|^{2},g|\mathrm{Per}_{z}(X)|^{2}]

(41)

for $g>1$ . This implies that $p>0$ . Otherwise, $\mathcal{O}(X)=0$ . This implies that there is an algorithm which decides if $\mathrm{Per}_{z}(X)=0$ . Furthermore, if $p=0$ , $\mathcal{A}$ outputs $0$ .

It suffices to consider the case $|\mathrm{Per}_{z}(X)|^{2}\neq 0$ . Since $X$ is binary-valued, we can write

\displaystyle|\mathrm{Per}_{z}(X)|^{2}=a_{0}+a_{1}z+\ldots+a_{m-1}z^{m-1},

(42)

where each $a_{i}$ is a non-negative integer, provided that $z$ is a primitive $m$ -th root of unity.

The algorithm $\mathcal{A}^{\mathcal{O}}$ finds a sequence of matrices $X_{0}=X,X_{1},\ldots,X_{n-1}$ such that each $X_{i}\in\mathbb{C}^{(n-i)\times(n-i)}$ and $X_{i+1}$ is a submatrix of $X_{i}$ obtained by deleting the first column and one of the rows $k$ determined as follows: starting from $k=1$ , repeat incrementing $k$ until the submatrix $W$ obtained by deleting the $k$ -th row and the first column satisfies that $|\mathrm{Per}_{z}(W)|^{2}\neq 0$ . Finally set $X_{i+1}=W$ . Since $\mathrm{Per}_{z}(X)\neq 0$ , it is guarantee that there exists $W$ such that $|\mathrm{Per}_{z}(W)|\neq 0$ . Computing the sequence of matrices takes $O(n^{2})$ queries.

The algorithm inductively approximates $\frac{\mathrm{Per}_{z}(X_{k-1})}{\mathrm{Per}_{z}(X_{k})}$ to error $O(\epsilon/n)$ using $O(mng^{4}\log n+g^{4}\log g+g^{4}\log(1/\epsilon))$ queries to $\mathcal{O}$ from $k=n-1$ to $0$ and the telescoping product

\displaystyle\mathrm{Per}_{z}(X)=\frac{\mathrm{Per}_{z}(X_{0})}{\mathrm{Per}_{z}(X_{1})}\cdot\frac{\mathrm{Per}_{z}(X_{1})}{\mathrm{Per}_{z}(X_{2})}\cdots\frac{\mathrm{Per}_{z}(X_{n-2})}{\mathrm{Per}_{z}(X_{n-1})}\cdot\mathrm{Per}_{z}(X_{n-1}).

(43)

Computing the base case $\mathrm{Per}_{z}(X_{n-1})$ is trivial. Applying Lemma 4.1, this implies that an approximation to error $\epsilon$ takes $O(mn^{2}g^{4}\log n+g^{4}n\log g)$ queries.

In the following proof, we will only consider the case from $Y:=X_{1}$ to $X_{0}$ , and the same argument applies to $k=2,\ldots,n-1$ . For simplicity, we only prove the case where $Y$ is obtained from $X$ by deleting the first row and the first column. Other cases (i.e., deleting the $i$ -th row of $X$ for $i>1$ ) can be applied using the same argument.

We consider the quantity $\mathrm{Per}_{z}(X)-\alpha\mathrm{Per}_{z}(Y)$ . Note that for a primitive root of unity $z$ , both $\mathrm{Per}_{z}(X)$ and $\mathrm{Per}_{z}(Y)$ are algebraic integers. This implies that the ratio $\alpha=\frac{\mathrm{Per}_{z}(X)}{\mathrm{Per}_{z}(Y)}$ is an algebraic number. To see there is a lower bound between two algebraic numbers, we apply a variant of the Liouville’s approximation theorem, stated in Theorem 2.12.

Since $\mathrm{Per}_{z}(X)$ and $\mathrm{Per}_{z}(Y)$ are both algebraic integers, their minimal polynomials are monic. Furthermore, for $\mathrm{Per}_{z}(X)=\mu$ , $\max|\sigma(\mu)|\leq\mathrm{Per}(X)\leq n!$ , and similarly the same upper bound holds for $Y$ . Setting $a=0$ and $b=1$ , $|\mathrm{Per}_{z}(Y)|\geq 1/M$ and $\mathrm{Per}_{z}(X)\geq 1/M$ , where $M:=(2n!+1)^{m-2}$ , and

\displaystyle\frac{1}{n!M}\leq\frac{|\mathrm{Per}_{z}(X)|}{|\mathrm{Per}_{z}(Y)|}\leq n!M.

(44)

The quantity $\mathrm{Per}_{z}(X)-t\mathrm{Per}_{z}(Y)=\mathrm{Per}_{z}(X^{[t]})$ , where $X_{ij}^{[t]}=X_{ij}-t\cdot\mathbbm{1}[i=1]\mathbbm{1}[j=1]$ , so its norm square can be approximated to multiplicative error $g$ using one call to $\mathcal{O}$ . To find an estimate of $\alpha=\frac{\mathrm{Per}_{z}(X)}{\mathrm{Per}_{z}(Y)}$ , we recursively find complex numbers $\alpha_{0},\ldots,\alpha_{\ell}$ such that the following invariant holds:

\displaystyle\mathcal{O}(X^{[\alpha_{i+1}]})\leq\frac{1}{2}\mathcal{O}(X^{[\alpha_{i}]})

(45)

for every $i$ . To see how close $\alpha_{i}$ is to $\alpha$ ,

$\displaystyle\|\alpha-\alpha_{i}\|$	$\displaystyle=\frac{\|\mathrm{Per}_{z}(X)-\alpha_{i}\mathrm{Per}_{z}(Y)\|}{\|\mathrm{Per}_{z}(Y)\|}$
	$\displaystyle\leq\frac{\sqrt{g\mathcal{O}(X^{[\alpha_{i}]})}}{\|\mathrm{Per}_{z}(Y)\|}$
	$\displaystyle\leq g\sqrt{\frac{\mathcal{O}(X^{[\alpha_{i}]})}{\mathcal{O}(Y)}}$	(46)

Also let

\displaystyle\beta_{i}:=g\sqrt{\frac{\mathcal{O}(X^{[\alpha_{i}]})}{\mathcal{O}(Y)}}.

(47)

Setting the initial guess $\alpha_{0}=0$ ,

$\displaystyle\mathcal{O}(X^{[\alpha_{0}]})$	$\displaystyle\leq g\|\mathrm{Per}_{z}(X)\|^{2}$
	$\displaystyle\leq g\|\mathrm{Per}(X)\|^{2}$
	$\displaystyle=g(n!)^{2}.$	(48)

Recall that $\mathcal{O}(Y)\geq g^{-1}|\mathrm{Per}_{z}(Y)|^{2}\geq\frac{1}{gM^{2}}$ . Then we have

$\displaystyle\|\alpha-\alpha_{i}\|$	$\displaystyle\leq g\sqrt{\frac{\mathcal{O}(X^{[\alpha_{i}]})}{\mathcal{O}(Y)}}$
	$\displaystyle\leq g\sqrt{\frac{2^{-i}\mathcal{O}(X^{[\alpha_{0}]})}{\mathcal{O}(Y)}}$
	$\displaystyle\leq g\sqrt{2^{-i}\cdot g(n!)^{2}\cdot gM^{2}}$
	$\displaystyle\leq g^{2}\cdot n!\cdot M\cdot 2^{-i/2}.$	(49)

Our goal is to get $|\alpha-\alpha_{\ell}|\leq\frac{\epsilon}{2n\cdot n!M}$ since it implies that $|\alpha-\alpha_{\ell}|\leq\frac{\epsilon|\alpha|}{2n}$ . Thus it suffices to set $2^{\ell/2}>g^{2}\cdot(n!)^{2}\cdot n\cdot M^{2}\cdot(1/\epsilon)$ and $\ell=O(mn\log n+\log g+\log(1/\epsilon))$ .

Now we give the algorithm that finds an $\alpha_{i+1}$ that satisfies (45) from $\alpha_{i}$ . By definition, $|\alpha-\alpha_{i}|\leq\beta_{i}$ . We consider the disk

\displaystyle S_{i}:=\{t:|t-\alpha_{i}|\leq\beta_{i}\},

(50)

and a grid of $O(L^{2})$ points inside the disk for integer $L$ determined later:

\displaystyle L_{i}:=\mathopen{}\mathclose{{}\left\{\alpha_{i}+(j-1)\frac{\beta_{i}}{L}+\sqrt{-1}(k-1)\frac{\beta_{i}}{L}\in S_{i}:|j|,|k|\in[L]}\right\}.

(51)

The algorithm computes $\mathcal{O}(X^{[t]})$ for every $t\in L_{i}\cap S_{i}$ and outputs $t$ for which $\mathcal{O}(X^{[t]})$ is minimized (with ties broken arbitrarily).

By definition, $\alpha\in S_{i}$ , and thus there exists $t\in L_{i}$ such that $|t-\alpha|\leq\frac{\beta_{i}}{\sqrt{2}L}$ . For such $t$ ,

$\displaystyle\mathcal{O}(X^{[t]})$	$\displaystyle\leq g\|\mathrm{Per}_{z}(X)-t\mathrm{Per}_{z}(Y)\|^{2}$
	$\displaystyle\leq g\|\alpha-t\|^{2}\|\mathrm{Per}_{z}(Y)\|^{2}$
	$\displaystyle\leq g\cdot\frac{\beta_{i}^{2}}{2L^{2}}\cdot\|\mathrm{Per}_{z}(Y)\|^{2}$
	$\displaystyle\leq g\cdot\frac{\beta_{i}^{2}}{2L^{2}}\cdot g\mathcal{O}(Y)$
	$\displaystyle=\frac{g^{4}}{2L^{2}}\mathcal{O}(X^{[\alpha_{i}]}).$	(52)

Thus for $L=g^{2}$ , the ratio $\frac{\mathcal{O}(X^{[t]})}{\mathcal{O}(X^{[\alpha_{i}]})}$ is at most $1/2$ . ∎

As a corollary, we recover a result of Aaronson and Arkhipov for $1$ -permanent (with slightly worse query complexity) by Theorem 4.2, but the same theorem can apply to a primitive root of unity $z\in\mathbb{T}$ .

Corollary 4.3 (cf. [AA11, Theorem 28]).

For $g\in[1,\operatorname{poly}(n)]$ , if there is an algorithm $\mathcal{O}$ which on input $X\in\{0,1\}^{n\times n}$ approximates $|\mathrm{Per}(X)|^{2}$ to within multiplicative factor of $g$ , then there is an algorithm which exactly computes $\mathrm{Per}(X)$ using $O(mn^{2}g^{4}\log n+ng^{4}\log g)$ queries to $\mathcal{O}$ .

Proof.

Since $\mathrm{Per}(X)$ is an integer, we apply Theorem 4.2 with $\epsilon=1/n!$ . The algorithm takes $O(mn^{2}g^{4}\log n+ng^{4}\log g)$ queries. ∎

Furthermore, obtaining an approximation to additive error within $2^{-n^{2}}$ takes $\operatorname{poly}(n)$ queries.

Corollary 4.4.

For $g\in[1,\operatorname{poly}(n)]$ , if there is an algorithm $\mathcal{O}$ which on input $X\in\{0,1\}^{n\times n}$ , approximates $|\mathrm{Per}_{\zeta_{m}}(X)|^{2}$ to within a multiplicative factor of $g$ , then there exists an algorithm which outputs an esatimate $\tilde{P}$ of $\mathrm{Per}_{\zeta_{m}}(X)$ satisfying

\displaystyle|\mathrm{Per}_{\zeta_{m}}(X)-\tilde{P}|\leq 2^{-n^{2}}

(53)

using $O(mn^{2}g^{4}\log n+ng^{4}\log n+g^{4}n^{3})$ queries to $\mathcal{O}$ .

Proof.

To approximate to additive error within $2^{-n^{2}}$ , it suffices to approximate to multiplicative error $\epsilon=\frac{1}{n!2^{n^{2}}}$ since the $|\mathrm{Per}_{\zeta_{m}}(X)|$ norm is at most $n!$ , and then by the Theorem 4.2 and it takes $O(mn^{2}g^{4}\log n+ng^{4}\log n+ng^{4}\log(\frac{1}{\epsilon}))=O(mn^{2}g^{4}\log n+ng^{4}\log n+g^{4}n^{3})$ queries. ∎

Here we see that the proof of approximate hardness relies on the fact that $z$ -permanent of given matrix $X$ can be computed from the $z$ -permanent of its submatrix (see equation (21)). Other matrix functions such as immanants do not have this property.

4.2 A Search-to-Decision Reduction

In the previous section, we have shown how to approximate $\mathrm{Per}_{\zeta_{m}}(X)$ to multiplicative error $2^{-n^{O(1)}}$ for an $m$ -th primitive root of unity $\zeta_{m}$ using an oracle that approximates $|\mathrm{Per}_{\zeta_{m}}(X)|^{2}$ to multiplicative error $g=n^{O(1)}$ . In this section, we show how to search for a representation of $\mathrm{Per}_{\zeta_{m}}(X)$ from the approximation (see Definition 3.6).

Recall that by (27), for binary matrix $X$ , $\mathrm{Per}_{\zeta_{m}}(X)$ is an element in the ring $\mathbb{Z}[\zeta_{m}]$ and can be written as a polynomial in $\zeta_{m}$ . Since $\Phi_{m}(\zeta_{m})=0$ and $\deg\Phi_{m}=\phi(m)$ , we can represent any algebraic integer in $\mathbb{Z}[\zeta_{m}]$ as a polynomial of degree at most $\phi(m)-1$ . In fact, such a representation is unique. A more detailed background can be seen Definition 2.10.

Definition 4.5 (Representation of $\mathbb{Z}[\zeta_{m}]$ ).

For integer $m\geq 1$ , the representation of an algebraic integer $\alpha\in\mathbb{Z}[\zeta_{m}]$ is a tuple $(a_{0},\ldots,a_{\phi(m)-1})$ such that

\displaystyle\alpha=\sum_{i=0}^{\phi(m)-1}a_{i}\zeta_{m}^{i}.

(54)

As a polynomial in $\zeta_{m}$ , the representation is the remainder of $\alpha$ divided by the cyclotomic polynomial $\Phi_{m}$ . A representation is said to be bounded in $[A,B]$ for integers $A,B$ if for every $0\leq i\leq\phi(m)-1$ , $A\leq a_{i}\leq B$ .

To extract a representation from an approximation, we rely on the following lemma which states that the coefficients $a_{i}$ can be represented using $n^{O(1)}$ bits.

Theorem 4.6 (Bounds on the coefficients of cyclotomic polynomials [Vau75]).

For integer $m\geq 1$ , let $\Phi_{m}(x)$ be the $m$ -th cyclotomic polynomial. The maximum absolute value of the coefficients of $\Phi_{m}(x)$ is at most $e^{\frac{1}{2}d(m)\log(m)}$ , where $d(n)$ is the divisor function which count the number of divisors of $m$ (including $1$ and $m$ ).⁴⁴4For instance $d(6)=4$ .

For $m=p_{1}^{a_{1}}\ldots,p_{k}^{a_{k}}$ , $d(m)=(a_{1}+1)\ldots(a_{k}+1)$ . Thus we can get the trivial bound $d(m)\leq m$ . By Theorem 4.6, we can represent $\phi_{m}(x)$ using at most only $O(m\log m)$ bits. Then the following lemma shows that every element of the representation of $\mathrm{Per}_{\zeta_{m}}(X)$ can be represented using $\operatorname{poly}(n)$ bits.

Lemma 4.7 ([BP86, Lemma 2]).

Let $s(x)=\sum_{i=0}^{m}s_{i}x^{i},t(x)=\sum_{i=0}^{n}t_{i}x^{i},$ be two polynomials of degrees $m\geq n$ . Also let the quotient $q(x)=\sum_{i=0}^{m-n}q_{i}x^{i}$ and the remainder $r$ be such that $s(x)=q(x)t(x)+r(x)$ . Then

\sum_{i=0}^{m-n}|q_{i}|\leq\mathopen{}\mathclose{{}\left(1+\frac{N}{t_{n}}}\right)^{m-n}\sum_{i=n}^{m}\frac{|s_{i}|}{t_{n}},

(55)

where $N=\max(|t_{n}|,|t_{n-1}|,...,|t_{2n-m}|)$ and $t_{g}=0$ if $g<0.$

For our purpose, since each $A_{i}$ satisfies

\displaystyle A_{\ell}=\sum_{\sigma:\ell(\sigma)=\ell}\prod_{i=1}^{n}X_{i,\sigma(i)}\leq n!,

(56)

by Lemma 4.7, we have the following corollary.

Corollary 4.8.

For integer $m\geq 1$ and binary $X$ , let $(a_{0},\ldots,a_{\phi(m)-1})$ be the representation of $\mathrm{Per}_{\zeta_{m}}(X)$ . Then

\displaystyle\max_{0\leq i\leq\phi(m)-1}\log|a_{i}|\leq O(m^{2}\log m+n\log n).

(57)

Proof.

Let

\displaystyle s(x):=\sum_{\ell=0}^{m-1}A_{\ell}\zeta_{m}^{\ell}.

(58)

By Theorem 4.6, the coefficients of the cyclotomic polynomial is at most $M=2^{O(m\log m)}$ . By Lemma 4.7 and the fact that $\Phi_{m}$ is monic, the summation of the coefficients of the quotient satisfies that

	$\displaystyle\sum_{i=0}^{m-1-\phi(m)}\|q_{i}\|$	$\displaystyle\leq\mathopen{}\mathclose{{}\left(1+M}\right)^{m-\phi(m)-1}\cdot n!\cdot(m-\phi(m)-1)$
		$\displaystyle\leq 2^{O((m-\phi(m))\cdot m\log m+n\log n)}.$		(59)

The representation is the remainder of $s$ devided by $\Phi_{m}$ . Let $r(x)=\sum_{i=0}^{\phi(m)-1}a_{i}x^{i}=s(x)-q(x)\Phi_{m}(x)$ . We have

$\displaystyle\|a_{i}\|$	$\displaystyle\leq\mathopen{}\mathclose{{}\left\|s_{i}-\sum_{j=0}^{i}q_{j}t_{i-j}}\right\|$
	$\displaystyle\leq\max_{i}\|s_{i}\|+(\phi(m)-1)\cdot\max_{i}\|q_{i}\|\cdot\max_{i}\|t_{i}\|$
	$\displaystyle\leq n!+(\phi(m)-1)\cdot 2^{O((m-\phi(m))\cdot m\log m+n\log n)}\cdot M.$	(60)

Thus

\displaystyle\max_{i}\log|a_{i}|\leq O((m-\phi(m))\cdot m\log m+n\log n).

(61)

Since $\phi(m)=\Omega(\frac{m}{\log\log m})$ , $m-\phi(m)=\Theta(m)$ . ∎

Let $A$ denote the maximum of the coefficients in the representation of $\mathrm{Per}_{\zeta_{m}}(X)$ . By Corollary 4.8, $\log A=O(m^{2}\log m+n\log n)$ , and thus the coefficients can be represented using $\operatorname{poly}(n)$ bits, provided $m=\operatorname{poly}(n)$ .

By Liouville’s approximation theorem (Theorem 2.12), the distance of two arbitrary algebraic integers whose representation is bounded in $[-A,A]$ are at least $\delta=2^{-n^{O(1)}}$ in the complex plane.

Corollary 4.9.

For integer $A$ , let $\alpha,\beta$ be two algebraic integers in $\mathbb{Z}[\zeta_{m}]$ whose representation is bounded in $[-A,A]$ . Then it holds that $|\alpha-\beta|\geq\frac{1}{(2A\cdot\phi(m)+1)^{\phi(m)-1}}$ .

Proof.

Since $\mathbb{Z}[\zeta_{m}]$ is an additive group, $\alpha-\beta\in\mathbb{Z}[\zeta_{m}]$ whose minimal polynomial is monic and whose representation is bounded in $[-2A,2A]$ . By Theorem 2.12 with $(a,b)=(0,1)$ , $d\leq[\mathbb{Q}(\zeta_{m}):\mathbb{Q}]=\phi(m)$ , and $|\overline{\alpha-\beta}|\leq Ad$ . These facts give

\displaystyle|\alpha-\beta|\geq\frac{1}{(2A\cdot\phi(m)+1)^{\phi(m)-1}}.

(62)

∎

Now let $M:=(2A\phi(m)+1)^{\phi(m)-1}$ . If we already know a complex number $\tilde{\alpha}$ that is $\delta$ -close to an algebraic integer $\alpha$ for $\delta\leq\frac{1}{4M}$ , then for every other algebraic integer $\beta\neq\alpha$ whose representation is also bounded in $[-A,A]$ , $|\beta-\tilde{\alpha}|>\frac{3}{4M}$ . Given the observation, we define the following problem.

Problem 2 (Close algebraic integer problem (caip)).

The close algebraic integer problem $(\textsc{caip})$ is defined as follows: given $(\alpha,L_{0},\ldots,L_{\phi(m)-1},T)$ , where $\alpha\in\mathbb{C}$ , $L_{0},\ldots,L_{\phi(m)-1},M$ are non-negative integers (all represented using $n^{O(1)}$ bits), determine if

•

there is an algebraic integer $\alpha^{\prime}\in S$ such that $|\alpha-\alpha^{\prime}|\leq 1/T$ , or
•

every $\alpha^{\prime}\in S$ satisfies $|\alpha-\alpha^{\prime}|\geq 2/T$ ,

where the set $S$ consists of algebraic integers in $\mathbb{Z}[\zeta_{m}]$ whose representation $(a_{0},\ldots,a_{\phi(m)-1})$ satisfies $0\leq a_{i}\leq L_{i}$ for $0\leq i\leq\phi(m)-1$ . It is promised that the given instance is in one of the cases.

Indeed, caip can be solved using a non-deterministic Turing machine (NTM).

Theorem 4.10.

$\textsc{caip}\in\mathsf{NP}$ .

Proof.

We can use sufficiently many bits (but still polynomial) to represent $\zeta_{m}$ as a complex number $\xi$ such that

\displaystyle|\zeta_{m}-\xi|=o\mathopen{}\mathclose{{}\left(\frac{1}{T\cdot\phi(m)^{2}\cdot\max_{i}L_{i}}}\right).

(63)

For every $\beta=b_{0}+b_{1}\zeta_{m}+\ldots+b_{\phi(m)-1}\zeta_{m}^{\phi(m)-1}$ approximated by $\tilde{\beta}=b_{0}+b_{1}\xi+\ldots+b_{\phi(m)-1}\xi^{\phi(m)-1}$ satisfying $|\beta-\tilde{\beta}|=o(1/T)$ for every $i$ and integer $b_{i}\in[L_{i}]$ .

If the NTM non-deterministically finds $b_{0},\ldots,b_{\phi(m)-1}$ satisfying $|\alpha-\tilde{\beta}|\leq 1.5/T$ , then $|\alpha-\beta|\leq 1/T$ . Otherwise, every $\beta$ satisfies $|\alpha-\beta|\geq 2/T$ . ∎

The problem caip only consider the case where each coefficient $b_{i}\in[0,L_{i}]$ . To extend it to general cases where the $i$ -th element is in $[U_{i},L_{i}]$ , we can shift $\alpha$ to $\beta=\alpha-U_{i}\zeta_{m}^{i}$ and solves caip with $\beta$ and the $i$ -th paremeter being $L_{i}-U_{i}$ . Thus it suffices to only consider the former setting.

Given an oracle for caip, we can search for a satisfying algebraic integer.

Theorem 4.11.

Let $\mathcal{O}$ be an oracle which solves caip. Then there exists an algorithm which makes $O(\log(L_{1}\ldots L_{\phi(m)-1}))$ queries to $\mathcal{O}$ and finds a satisfying algebraic integer, or returns $\bot$ if there is not.

Proof.

The algorithm $\mathcal{A}$ is basically a binary search for each coefficient.

First $\mathcal{A}$ runs $b\leftarrow\mathcal{O}(\alpha,L_{0},\ldots,L_{\phi(m)-1},T)$ ; if the output $b=0$ , then $\mathcal{A}$ returns $\bot$ . Otherwise, there must be a satisfying algebraic integer $\alpha^{\prime}$ . Then $\mathcal{A}$ runs the following steps:

1.

Set $\beta\leftarrow\alpha$ .
2.
For $j=\phi(m)-1,\ldots,0$ ,
1. (a)
  
  Set $W\leftarrow 0$ and $R\leftarrow\lfloor L_{j}/2\rfloor$ .
2. (b)
  Repeat the following steps until $R=0$ :
  1. i.
    
    Compute $b_{i}\leftarrow\mathcal{O}(\beta,L_{0},\ldots,L_{j-1},R,0,\ldots,0,T)$ .
  2. ii.
    
    If $b=0$ , set $\beta\leftarrow\beta-(R+1)\xi^{j}$ and $W\leftarrow W+R+1$ .
  3. iii.
    
    Set $R\leftarrow\lfloor R/2\rfloor$ .
3. (c)
  
  Set $a_{j}\leftarrow W$ .
3.

Output $(a_{0},\ldots,a_{\phi(m)-1})$ .

We prove the algorithm is correct for $j=\phi(m)-1$ ; for other coefficients, the correctness analysis applies similarly. First, the algorithm must terminate since in each iteration $R$ gets decreased by a factor of two. For the correctness, we note that $\beta+Wz^{\phi(m)-1}=\alpha$ holds after each iteration. In each step, let a satisfying algebraic integer denote $\beta^{\prime}$ , written as

\displaystyle\beta^{\prime}=c_{\phi(m)-1}z^{\phi(m)-1}+a_{\phi(m)-2}z^{\phi(m)-2}+\ldots+a_{0}

(64)

before Step 2(b)ii is run. It suffices to show that after Step 2(b)ii, the leading coefficient is no more than $R$ by induction. For the base case, since the leading coefficient of $\alpha^{\prime}$ is no more than $L_{\phi(m)-1}$ ; the assertion holds. If $b=0$ , then $R<c_{\phi(m)-1}\leq 2R+1$ , and $c_{\phi(m)-1}-(R+1)\geq 0$ ; otherwise, there exists a satisfying $\beta^{\prime}$ such that $c_{\phi(m)-1}\leq R$ . Thus after Step 2(b)ii, there is a satisfying algebraic integer whose leading coefficient is no more than $R$ . ∎

5 Average-case Hardness

In the context of average-case hardness, Aaronson and Arkhipov [AA11] considered the hardness of $1$ -permanent for i.i.d. Gaussian matrices. More recently, Haferkamp, Hangleiter, Eisert, and Gluza [HHEG20] considered the average-case hardness of the truncated uniform distribution.

In this section, we extend their results both to $z$ -permanent and to a wide range of distributions, provided that the distribution satisfies a property called the strong autocorrelation property.

Our idea follows from Aaronson and Arkhipov [AA11]: If one can compute a low-degree polynomial for sufficiently many points, then there is an algorithm that recovers the whole polynomial with high probability. More precisely, we use the following algorithm for noisy polynomial interpolation.

Theorem 5.1 (Berlekamp-Welch algorithm [BV]).

Let $q$ be a univariate polynomial of degree $d$ over any field $\mathbb{F}$ . Suppose we are given m pairs of $\mathbb{F}$ elements $(x_{1},y_{1}),...,(x_{m},y_{m})$ (with the $x_{i}^{\prime}s$ all distinct), and are promised that $y_{i}=q(x_{i})$ for more than $(m+d)/2$ values of i. Then there is a deterministic algorithm to reconstruct $q$ using $\operatorname{poly}(n,d)$ field operations.

Now we define the following property, under which a random self-reducibility using the Berlekamp-Welch algorithm can be applied.

Definition 5.2 (Strong autocorrelation property).

Consider a random variable $X$ with a real distribution $\mathcal{F}$ with mean $0$ and variance $1.$ We denote it as $X\sim\mathcal{F}_{\mathbb{R}}(0,1).$ We define $\mathcal{F}_{\mathbb{R}}(\mu,\sigma^{2})$ with mean $\mu$ and variance $\sigma^{2}$ by shifting and scale the random variable $X\to\mu+\sigma^{2}X.$ We pick $\epsilon<\frac{1}{2}.$ We can define complex random variable $Z=X+iY$ , $X\sim\mathcal{F}_{\mathbb{R}}(\mu_{1},1/2),Y\sim\mathcal{F}_{\mathbb{R}}(\mu_{2},1/2)$ and $X,Y$ are independent. We write $Z\sim\mathcal{F}_{\mathbb{C}}(\mu_{1}+i\mu_{2},1).$ Now we consider the following three distributions

$\displaystyle X$	$\displaystyle=\mathcal{F}_{\mathbb{C}}(0,1)^{n}$	(65)
$\displaystyle\mathcal{D}_{1}$	$\displaystyle=\mathcal{F}_{\mathbb{C}}\mathopen{}\mathclose{{}\left(0,\mathopen{}\mathclose{{}\left(1-\varepsilon}\right)^{2}}\right)^{n},$	(66)
$\displaystyle\mathcal{D}_{2}$	$\displaystyle=\prod_{i=1}^{n}\mathcal{F}_{\mathbb{C}}\mathopen{}\mathclose{{}\left(v_{i},1}\right)$	(67)

for some vector $v\in\mathbb{C}^{n}$ . A distribution is said to satisfy the strong autocorrelation property Definition 5.2 if there exists constant $M_{1},M_{2}$ independent of $n,\epsilon$ , such that

	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{1}-X}\right\\|$	$\displaystyle\leq 2nM_{1}\varepsilon,$		(68)
	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{2}-X}\right\\|$	$\displaystyle\leq\sqrt{2n}M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{2}\,.$		(69)

When $\mathcal{F}$ is complex Gaussian or truncated uniform distribution both satisfy this criterion from direct calculation [AA11, HHEG20]. In Appendix B, we give a sufficient condition under which almost all well-behaved $\mathcal{F}$ satisfies the such criterion.

Now we are ready to show that, as permanent, $z$ -permanent also has random self-reducibility.

Theorem 5.3 (Random self-reducibility of $z$ -permanent).

Assume that there is no classical efficient algorithm for computing $z$ -permanent and for all $\{0,1\}$ -matrices. For all $\delta\geq 1/\operatorname{poly}(n)$ the following problem is classically hard: Given an $n\times n$ matrix $X$ drawn from $\mathcal{F}_{\mathbb{C}}(0,1)^{n\times n}$ which satisfies the strong autocorrelation property, output $\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(X}\right)$ with probability at least ${3}/{4}+\delta$ over $\mathcal{F}_{\mathbb{C}}(0,1)^{n\times n}$ .

Proof.

Let $M=\mathopen{}\mathclose{{}\left(x_{ij}}\right)\in\mathopen{}\mathclose{{}\left\{0,1}\right\}^{n\times n}$ be an arbitrary $\{0,1\}$ -matrix. We show how to compute $\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(M}\right)$ in probabilistic polynomial time, given access to an oracle $\mathcal{O}$ such that

\Pr_{X\sim\mathcal{F}_{\mathbb{C}}(0,1)^{n\times n}}\mathopen{}\mathclose{{}\left[\mathcal{O}\mathopen{}\mathclose{{}\left(X}\right)=\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(X}\right)}\right]\geq\frac{3}{4}+\delta\,.

(70)

We choose a matrix $Y\in\mathbb{C}^{n\times n}$ from the distribution $\mathcal{F}_{\mathbb{C}}(0,1)^{n\times n}$ and define

X\mathopen{}\mathclose{{}\left(t}\right):=\mathopen{}\mathclose{{}\left(1-t}\right)Y+tM,q\mathopen{}\mathclose{{}\left(t}\right):=\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(X\mathopen{}\mathclose{{}\left(t}\right)}\right)

(71)

so that $X\mathopen{}\mathclose{{}\left(0}\right)=Y$ and $X\mathopen{}\mathclose{{}\left(1}\right)=M$ , and $q\mathopen{}\mathclose{{}\left(t}\right)$ is a univariate polynomial in $t$ of degree at most $n$ and $q\mathopen{}\mathclose{{}\left(1}\right)=\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(X\mathopen{}\mathclose{{}\left(1}\right)}\right)=\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(M}\right)$ . Now let

L:=\mathopen{}\mathclose{{}\left\lceil\frac{n}{\delta}}\right\rceil\quad\text{and}\quad\varepsilon:=\frac{\delta}{\mathopen{}\mathclose{{}\left(4n^{2}M_{1}+4n^{2}M_{2}}\right)L}\,.

For each $\ell\in\mathopen{}\mathclose{{}\left[L}\right]$ call the oracle $\mathcal{O}$ on input matrix $X\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)$ . Then, using the Berlekamp-Welch algorithm (Theorem 5.1), attempt to find a degree- $n$ polynomial $q^{\prime}:\mathbb{C}\rightarrow\mathbb{C}$ such that

q^{\prime}\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)=\mathcal{O}\mathopen{}\mathclose{{}\left(X\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)}\right)

(72)

for at least a ${3}/{4}+\delta$ fraction of $\ell\in\mathopen{}\mathclose{{}\left[L}\right]$ . If no such $q^{\prime}$ is found, then fail; otherwise, output $q^{\prime}\mathopen{}\mathclose{{}\left(1}\right)$ as the guessed value of $\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(M}\right)$ . Now we show that the above algorithm succeeds (that is, outputs $q^{\prime}\mathopen{}\mathclose{{}\left(1}\right)=\mathrm{Per}_{z}\mathopen{}\mathclose{{}\left(M}\right)$ ) with probability at least ${1}/{2}+{\delta}/{2}$ over $Y$ . Provided that holds, it is clear that the success probability can be boosted to (say) $2/3$ by simply repeating the algorithm $O\mathopen{}\mathclose{{}\left(1/\delta^{2}}\right)$ times with different choices of $Y$ and then outputting the majority result. To prove the claim, note that for each $\ell\in\mathopen{}\mathclose{{}\left[L}\right]$ one can think of the matrix $X\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)$ as having been drawn from the distribution

\mathcal{D}_{\ell}:=\prod_{i,j=1}^{n}\mathcal{F}_{\mathbb{C}}\mathopen{}\mathclose{{}\left(\varepsilon\ell a_{ij},\mathopen{}\mathclose{{}\left(1-\varepsilon\ell}\right)^{2}}\right)\,.

(73)

Let

\mathcal{D}_{\ell}^{\prime}:=\prod_{i,j=1}^{n}\mathcal{F}_{\mathbb{C}}\mathopen{}\mathclose{{}\left(\varepsilon\ell a_{ij},1}\right).

(74)

Then by the triangle inequality together with Definition 5.2 ( $X\sim\mathcal{F}_{\mathbb{C}}(0,1)^{n\times n}$ ),

$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{\ell}-X}\right\\|$	$\displaystyle\leq\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{\ell}-\mathcal{D}_{\ell}^{\prime}}\right\\|+\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{\ell}^{\prime}-X}\right\\|$
	$\displaystyle\leq 2n^{2}M_{1}\varepsilon\ell+\sqrt{2n^{2}}M_{2}\sqrt{n^{2}\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)^{2}}$
	$\displaystyle\leq\mathopen{}\mathclose{{}\left(2n^{2}M_{1}+2n^{2}M_{2}}\right)\varepsilon l\leq(2n^{2}M_{1}+2n^{2}M_{2})\varepsilon L$
	$\displaystyle\leq\frac{\delta}{2}\,.$	(75)

We have

	$\displaystyle\Pr\mathopen{}\mathclose{{}\left[\mathcal{O}\mathopen{}\mathclose{{}\left(X\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)}\right)=q\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)}\right]$	$\displaystyle\geq\frac{3}{4}+\delta-\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{\ell}-X}\right\\|$
		$\displaystyle\geq\frac{3}{4}+\frac{\delta}{2}\,.$		(76)

Now let $S$ be the set of all $\ell\in\mathopen{}\mathclose{{}\left[L}\right]$ such that $\mathcal{O}\mathopen{}\mathclose{{}\left(X\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)}\right)=q\mathopen{}\mathclose{{}\left(\varepsilon\ell}\right)$ . Then by the reverse Markov’s inequality [EG01],

\Pr\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left|S}\right|\geq\mathopen{}\mathclose{{}\left(\frac{1}{2}+\frac{\delta}{2}}\right)L}\right]\geq 1-\frac{\frac{1}{4}-\frac{\delta}{2}}{\frac{1}{2}-\frac{\delta}{2}}\geq\frac{1}{2}+\frac{\delta}{2}\,.

(77)

So we then just run the above algorithm $O(\frac{1}{\delta^{2}})$ times to amplify the success probability. After that, with high probability, we have

\mathopen{}\mathclose{{}\left|S}\right|\geq\mathopen{}\mathclose{{}\left(\frac{1}{2}+\frac{\delta}{2}}\right)L\,.

Then by Theorem 5.1, the Berlekamp-Welch algorithm succeeds; It will output polynomial $q^{\prime}$ will be equal to $q$ . This proves the claim. ∎

6 Average-case Hardness of Approximation

Since Aaronson and Arkhipov’s seminal work on Boson Sampling [AA11] appeared, approximating $1$ -permanent in the average case has been investigated for particular distributions [AA11, HHEG20]. In particular, Aaronson and Arkhipov [AA11] conjectured a problem called Gaussian Permanent Estimation (also denoted $\mathrm{GPE}_{\times}$ ) is ${\#\mathsf{P}}$ -hard. The problem $\mathrm{GPE}_{\times}$ asks to compute $\mathrm{Per}(X)$ to multiplicative error $\epsilon$ with probability at least $1-\delta$ over matrix $X$ whose each element is sampled independently from the normalized Gaussian distribution. For quantum supremacy from Boson Sampling, the ultimate goal was to prove the additive version of $\mathrm{GPE}_{\times}$ , denoted $\mathrm{GPE}_{\pm}$ , is also hard. Based on another conjecture, called the Permanent Anti-Concentration Conjecture (PACC), one can deduce that $\mathrm{GPE}_{\pm}$ is as hard as $\mathrm{GPE}_{\times}$ . In the following, we denote $\mathcal{G}=\mathcal{N}_{\mathbb{C}}(0,1)^{n\times n}$ the distribution of an $n\times n$ i.i.d. Gaussian matrix with zero mean and unit variance.

Problem 3 ( $\mathrm{GPE}_{\times}$ ).

Given as input $X\sim\mathcal{N}_{\mathbb{C}}(0,1)^{n\times n}$ of i.i.d. Gaussians (complex normal distribution) and $\epsilon,\delta>0$ , estimate $\mathrm{Per}(X)$ to within error $\pm\epsilon|\mathrm{Per}(X)|$ to probability at least $1-\delta$ over $X$ .

Problem 4 ( $\mathrm{GPE}_{\pm}$ ).

Given as input $X\sim\mathcal{N}_{\mathbb{C}}(0,1)^{n\times n}$ of i.i.d. Gaussians (complex normal distribution) and $\epsilon,\delta>0$ , estimate $\mathrm{Per}(X)$ additively (i.e., to within error $\pm\epsilon\sqrt{n!}$ ), with probability at least $1-\delta$ over $X$

In this section, we consider the hardness of $z$ -permanent for matrices sampled from a general distribution $\mathcal{H}$ whose each entry is i.i.d. sampled. We first define the multiplicative and the additive versions of Permanent Estimation (PE) for distribution $\mathcal{H}$ .

Problem 5 ( $\mathrm{PE}_{\mathcal{H},z,\times}$ ).

Given as input $X\sim\mathcal{H}$ and $\epsilon,\delta>0$ , estimate $\mathrm{Per}(X)$ to within error $\pm\epsilon|\mathrm{Per}(X)|$ to probability at least $1-\delta$ over $X$ .

For convenience, $\mathrm{PE}_{\mathcal{H},1,\times}$ is also denoted $\mathrm{PE}_{\mathcal{H},\times}$ . Similarly, we can define an additive version of the above problem.

Problem 6 ( $\mathrm{PE}_{\mathcal{H},z,\pm}$ ).

Given as input $X\sim\mathcal{H}$ and $\epsilon,\delta>0$ , estimate $\mathrm{Per}_{z}(X)$ to within error $\pm\epsilon g(n)$ to probability at least $1-\delta$ over $X$ . For convenience, $\mathrm{PE}_{\mathcal{H},1,\pm}$ is also denoted $\mathrm{PE}_{\mathcal{H},\pm}$ .

From the definition, we have $\mathrm{GPE}_{\times}=\mathrm{PE}_{\mathcal{G},\times}$ and $\mathrm{GPE}_{\pm}=\mathrm{PE}_{\mathcal{G},\pm}$ with $g=\sqrt{n!}$ . Let $d=\binom{n}{2}$ For $r\in(0,\frac{1}{d+1})$ , let $S_{r}:=\{z=e^{i2\pi r}\zeta_{d+1}^{i-1}:i\in[d+1]\}$ , where $\zeta_{k}:=e^{i2\pi/k}$ is a primitive $k$ -th root of unity. Let $\mathcal{O}$ be an oracle, given $X\sim\mathcal{H}$ , outputs the approximations of $z$ -permanent of $d+1$ points, i.e., $\mathrm{Per}_{z_{1}}(X),\ldots,\mathrm{Per}_{z_{d+1}}(X)$ for $z_{1},\ldots,z_{d+1}\in S_{r}$ . More formally, we define $\mathcal{O}_{\times}$ and $\mathcal{O}_{\pm}$ to be oracles that approximate to multiplicative and additive errors, respectively:

Definition 6.1 ( $\mathcal{O}_{\times},\mathcal{O}_{\pm}$ ).

The oracles $\mathcal{O}_{\times}$ and $\mathcal{O}_{\pm}$ are defined as follows:

•

Given $X\sim\mathcal{H},$ $\mathcal{O}_{\times}(X,\epsilon,\delta)$ is the oracle that outputs a vector $y=(y_{1},\ldots,y_{d+1})^{\top}$ such that for every $i\in[d+1]$ , $|y_{i}-\mathrm{Per}_{z_{i}}(X)|\leq\epsilon|\mathrm{Per}_{z_{i}}(X)|$ with probability at least $1-\delta$ over choices of $X$ .
•

Given $X\sim\mathcal{H}$ and efficiently computable function $g$ , $\mathcal{O}_{\pm}(X,\epsilon,\delta)$ is the oracle that outputs a vector $y=(y_{1},\ldots,y_{d+1})^{\top}$ such that for every $i\in[d+1],$ we have: $|y_{i}-\mathrm{Per}_{z_{i}}(X)|\leq\epsilon g(n)$ with probability at least $1-\delta$ over choices of $X$ .

The rest of this section is devoted to showing that if $\mathcal{O}_{\times}$ can be classically simulated, then $\mathrm{PE}_{\mathcal{H},\times}$ can be solved efficiently, and similarly holds for $\mathcal{O}_{\pm}$ and $\mathrm{PE}_{\mathcal{H},\pm}$ in place of $\mathcal{O}_{\times}$ and $\mathrm{PE}_{\mathcal{H},\pm}$ . The proof is similar to Lipton’s proof [Lip91] for the average hardness of permanent over a finite field $\mathbb{F}_{p}$ for $p>n$ . In our case, we can approximate $\mathrm{Per}(X)$ given an approximation of $\Omega(n^{2})$ points on the unit circle.

First, we show the following two lemmas for polynomial interpolation. One is for multiplicative error and one is for additive error.

Lemma 6.2.

For integer $d\geq 1$ , let $f$ be a degree- $d$ complex-valued polynomial and $\mathcal{A}$ be an algorithm that approximates $f$ to additive error $\epsilon$ on points $x_{1},\ldots,x_{d+1}$ . There exists an algorithm which, on input $x\in\mathbb{T}$ , makes $d+1$ calls to $\mathcal{A}$ and outputs an estimate of $f(x)$ to additive error $(d+1)\|V^{-1}\|\epsilon$ , where $V=V(x_{1},\ldots,x_{d+1})$ is the Vandermonde matrix with nodes $x_{1},\ldots,x_{d+1}$ .

Proof.

Let $\tilde{y}_{1},\ldots,\tilde{y}_{d+1}$ be the estimate of $\mathcal{A}$ on $x_{1},\ldots,x_{d+1}$ respectively. Let $\tilde{y}=(\tilde{y}_{1},\ldots,\tilde{y}_{d+1})^{\top}$ and $x=(x_{1},\ldots,x_{d+1})^{\top}$ be the associated column vectors. Since for each $i\in[d+1]$ , $|\tilde{y}_{i}-y_{i}|\leq\epsilon$ , $\|\tilde{y}-y\|\leq\epsilon\sqrt{d+1}$ .

Let $c=(c_{0},\ldots,c_{d})^{\top}$ be the vector of the coefficients of $f(x)=\sum_{i=0}^{d}c_{i}x^{i}$ . Solving the linear equation $V\tilde{c}=\tilde{y}$ yields an estimate of the coefficients. For $x\in\mathbb{T}$ , let $v=(1,x,x^{2},\ldots,x^{d})$ be the vector of monomials evaluated on $x$ . Our goal is to bound the distance

\displaystyle|v\cdot(\tilde{c}-c)|\leq\|(V^{-1})^{\top}v\|\|V(c-c^{\prime})\|\leq\|v\|\|V^{-1}\|\|\tilde{y}-y\|\leq(d+1)\|V^{-1}\|\epsilon.

(78)

The first inequality holds by Cauchy-Schwarz inequality. The second holds by the definition of matrix norm. The last holds because $\|\tilde{y}-y\|\leq\epsilon$ and $\|v\|=\sqrt{d+1}$ . ∎

If we restrict our problem to approximating $f(1)$ for polynomials with non-negative coefficients, we can do better. In particular, we show that if $\mathcal{A}$ approximates $x_{1},\ldots,x_{d+1}$ for polynomial $f$ with non-negative coefficients to multiplicative error $\epsilon$ , then there is an algorithm that approximates $f(1)$ to the multiplicative error as above.

Lemma 6.3.

For integer $d\geq 1$ , let $f$ be a degree- $d$ polynomial with non-negative coefficients and $\mathcal{A}$ be an algorithm that approximates $f$ to multiplicative error $\epsilon$ on $x_{1},\ldots,x_{d+1}\in\mathbb{T}$ . Then there exists an algorithm which approximates $f(1)$ to multiplicative error $(d+1)\|V^{-1}\|\epsilon$ , where $V=V(x_{1},\ldots,x_{d+1})$ is the Vandermonde matrix with nodes $x_{1},\ldots,x_{d+1}$ .

Proof.

Let $\tilde{y}_{1},\ldots,\tilde{y}_{d+1}$ be the estimate of $\mathcal{A}$ on $x_{1},\ldots,x_{d+1}$ and $y=(\tilde{y}_{1},\ldots,\tilde{y}_{d+1})^{\top}$ . Solving the linear equation $V\tilde{c}=\tilde{y}$ yields $\tilde{c}=V^{-1}\tilde{y}$ . Also let $\tilde{f}(z):=\sum_{i=0}^{d}\tilde{c}_{i}z^{i}$ be the approximated polynomial obtained by solving the linear system.

Since $f$ has non-negative coefficients, $|f(x)|\leq f(1)=\langle 1^{d+1},c\rangle$ for every $x\in\mathbb{T}$ . Since $\|\tilde{y}-y\|\leq\epsilon\|y\|\leq\epsilon\sqrt{d+1}\cdot f(1)$ ,

\displaystyle|\tilde{f}(1)-f(1)|=|\langle 1^{d+1},\tilde{c}-c\rangle|\leq\sqrt{d+1}\|\tilde{c}-c\|\leq(d+1)\|V^{-1}\|\cdot\epsilon\cdot|f(1)|.

(79)

The first inequality holds by Cauchy-Schwarz inequality. Thus an algorithm which outputs $|\tilde{c}|_{1}$ as the approximation with multiplicative error $(d+1)\epsilon\|V^{-1}\|$ . ∎

Now we are ready to prove Theorem 6.4. By Lemma 6.2 and Lemma 6.3, we separate them into two cases.

Theorem 6.4.

The following statements hold:

1.

Suppose $\mathrm{PE}_{\mathcal{H},\times}$ is ${\#\mathsf{P}}$ -hard and $\mathcal{H}$ is non-negative distribution, and the polynomial hierarchy is infinite, then $\mathcal{O}_{\times}$ does not admit a classical efficient algorithm, i.e., there is no simulation of $\mathcal{O}_{\times}$ running in time $\operatorname{poly}(n,\frac{1}{\epsilon},\frac{1}{\delta})$ .
2.

Suppose $(\mathrm{PE}_{\mathcal{H},\pm},g)$ is ${\#\mathsf{P}}$ -hard and the polynomial hierarchy is infinite, then $\mathcal{O}_{\pm}$ does not admit a classical efficient algorithm, i.e., there is no classical simulation of $\mathcal{O}_{\pm}$ running in time $\operatorname{poly}(n,\frac{1}{\epsilon},\frac{1}{\delta})$ ).

Proof.

For (1), we give non-constructive proof. Let $d=\binom{n}{2}$ . For $r\in(0,\frac{1}{d+1})$ , let $S_{r}:=\{z=e^{i2\pi r}\zeta_{d+1}^{i-1}:i\in[d+1]\}$ , where $\zeta_{k}:=e^{i2\pi/k}$ is a primitive $k$ -th root of unity. We show that the number of points $z\in S_{r}$ such that $\mathrm{Per}_{z}(X)$ is efficiently computable cannot be more than $d$ . Suppose toward contradiction this is not the case. Then let $\mathcal{O}_{\times}$ be algorithms that runs in time $\operatorname{poly}(n,1/\epsilon,1/\delta)$ and approximates $\mathrm{Per}_{z_{1}}(X),\ldots,\mathrm{Per}_{z_{d+1}}(X)$ to precision $\epsilon$ with probability $1-\delta$ , for $S_{r}=\{z_{1},\ldots,z_{d+1}\}$ . Applying the algorithm in the proof of Lemma 6.3, we apply the oracle $\mathcal{O}_{\times}(X,\epsilon,\delta)$ for $\mathcal{H}_{\times}$ by the following algorithm:

1.

Get $y=(y_{1},\ldots,y_{d+1})^{\top}\leftarrow\mathcal{O}_{\times}(X,\epsilon(d+1)^{-1/2},\delta/(d+1))$ ;
2.

Solving the linear system $Vc=y$ , where $V=V(z_{1},\ldots,z_{d+1})$ .
3.

Output the summation of elements of $c$ as the approximation of $\mathrm{Per}(X)$ .

By the assumption, for each $i\in[d+1],$ with probability at least $1-\frac{\delta}{d+1}$ , $|y_{i}-\mathrm{Per}_{z_{i}}(X)|\leq\frac{\epsilon}{\sqrt{d+1}}|\mathrm{Per}_{z_{i}}(X)|$ . Since points in $S_{r}$ is equally spaced, $\frac{1}{\sqrt{d+1}}V$ is a unitary matrix, and so is $\sqrt{d+1}V^{-1}$ . This implies that the matrix norm $\|V^{-1}\|=(d+1)^{-1/2}$ . By Lemma 6.3 and union bound, the algorithm outputs an approximation of $\mathrm{Per}(X)$ to multiplicative error $\epsilon$ with probability at least $1-\delta$ . By the assumption $\mathrm{PE}_{\mathcal{H},\times}$ is hard, we conclude $\mathsf{P}^{{\#\mathsf{P}}}\subseteq\mathsf{BPP}^{\mathcal{O}_{\times}}\subseteq\mathsf{BPP}$ and a collapse of the polynomial hierarchy.

For (2), we use the same $S_{r}$ , then let $\mathcal{O}_{\pm}$ be algorithms that runs in time $\operatorname{poly}(n,1/\epsilon,1/\delta)$ and approximates $\mathrm{Per}_{z_{1}}(X),\ldots,\mathrm{Per}_{z_{d+1}}(X)$ to precision $\epsilon$ with probability $1-\delta$ , respectively for $S_{r}=\{z_{1},\ldots,z_{d+1}\}$ . Applying the algorithm in the proof of Lemma 6.2, we apply the oracle $\mathcal{O}_{\pm}(X,\epsilon,\delta)$ for $\mathcal{H}_{\pm}$ by the following algorithm:

1.

Get $y=(y_{1},\ldots,y_{d+1})^{\top}\leftarrow\mathcal{O}_{\pm}(X,\epsilon(d+1)^{-1/2},\delta/(d+1))$ .
2.

Solving the linear system $Vc=y$ , where $V=V(z_{1},\ldots,z_{d+1})$ .
3.

Output the summation of elements of $c$ as the approximation of $\mathrm{Per}(X)$ .

By the assumption, for each $i\in[d+1],$ with probability at least $1-\frac{\delta}{d+1}$ , $|y_{i}-\mathrm{Per}_{z_{i}}(X)|\leq\frac{\epsilon}{\sqrt{d+1}}g(n)$ . Since points in $S_{r}$ is equally spaced, $\frac{1}{\sqrt{d+1}}V$ is a unitary matrix, and so is $\sqrt{d+1}V^{-1}$ . This implies that the matrix norm $\|V^{-1}\|=(d+1)^{-1/2}$ . By Lemma 6.2 and a union bound, the algorithm outputs an approximation of $\mathrm{Per}(X)$ to additive error $\epsilon g(n)$ with probability at least $1-\delta$ . By our assumption $(\mathrm{PE}_{\mathcal{H},\times},g)$ ${\#\mathsf{P}}$ -hard, we conclude that $\mathsf{P}^{{\#\mathsf{P}}}\subseteq\mathsf{BPP}^{\mathcal{O}_{\pm}}\subseteq\mathsf{BPP}$ and the collapse of the polynomial hierarchy. ∎

At first glance, it seems like our result does not work for an i.i.d. Gaussian matrix since it is not positive except with exponentially small probability. However, similarly as in [AA11], we prove that $\mathrm{PE}_{\mathcal{G},z,\pm}$ with $g(n)=\sqrt{n!}$ can be reduced to $\mathrm{PE}_{\mathcal{G},z,\times}$ .

Lemma 6.5.

$(\mathrm{PE}_{\mathcal{G},z,\pm})$ with $g=\sqrt{n!}$ is polynomial-time reducible to $\mathrm{PE}_{\mathcal{G},z,\times}$ .

Proof.

Suppose we have a polynomial-time algorithm $M$ outputs a good multiplicative approximation to $\mathrm{Per}_{z}(X)$ —that is, a $w$ such that:

|w-\mathrm{Per}_{z}(X)|\leq\epsilon|\mathrm{Per}_{z}(X)|.

(80)

with probability at least $1-\delta$ over $X$ by Markov’s inequality ( $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{2}]=n!,$ see Lemma A.1):

\Pr_{X\sim\mathcal{G}}\mathopen{}\mathclose{{}\left[|w-\mathrm{Per}_{z}(X)|>k\sqrt{n!}}\right]<\frac{1}{k^{2}}

(81)

by the union bound,

	$\displaystyle\Pr_{X\sim\mathcal{G}}\mathopen{}\mathclose{{}\left[\|w-\mathrm{Per}_{z}(X)\|>\epsilon k\sqrt{n!}}\right]$	$\displaystyle\leq\Pr_{X\sim\mathcal{G}}\Big{[}\|w-\mathrm{Per}_{z}(X)\|>\epsilon\|\mathrm{Per}_{z}(X)\|\Big{]}+\Pr_{X\sim\mathcal{G}}\Big{[}\epsilon\|\mathrm{Per}_{z}(X)\|>\epsilon k\sqrt{n!}\Big{]}$
		$\displaystyle\leq\delta+\frac{1}{k^{2}}.$

Letting $\delta=\frac{\delta^{\prime}}{2},k=\sqrt{\frac{2}{\delta}}$ and $\epsilon=\frac{\epsilon^{\prime}}{k}$ , we have $\delta+\frac{1}{k^{2}}=\delta^{\prime}$ which finishes the proof. ∎

We now introduce the conjecture that generalize the original permanent anti-concentration conjecture.

Conjecture 3 ( $z$ -permanent anti-concentration conjecture ( $z$ -PACC)).

There exists a polynomial $p$ such that for positive integer $n$ , real number $\delta>0$ and $z\in\mathbb{T}$ ,

\displaystyle\Pr_{X\sim\mathcal{G}}\mathopen{}\mathclose{{}\left[|\mathrm{Per}_{z}(X)|^{2}\geq\frac{\sqrt{n!}}{p(n,1/\delta)}}\right]\geq 1-\delta.

(82)

In particular, $z=-1$ is proved by Aaronson [AA11] and $z=1$ is standard conjecture that widely believed to be True.

Corollary 6.6.

Assume that the $1$ -PACC holds. Suppose $\mathrm{GPE}_{\times}$ is ${\#\mathsf{P}}$ -hard and the polynomial hierarchy is infinite, then $\mathcal{O}_{\times}$ does not admit a classical efficient algorithm, i.e., there is no simulation of $\mathcal{O}_{\times}$ running in time $\operatorname{poly}(n,\frac{1}{\epsilon},\frac{1}{\delta})$ .

Proof.

Suppose $\mathrm{PE}_{\mathcal{G},z,\times}$ admit a classical efficient algorithm in $\operatorname{poly}(n,\frac{1}{\epsilon},\frac{1}{\delta})$ . Then one can solve $\mathrm{PE}_{\mathcal{G},z,\times}$ then solving $\mathrm{GPE}_{z,\times}$ for $d+1$ points. By Lemma 6.5, it solves $(\mathrm{PE}_{\mathcal{G},z,\pm})$ with $\sqrt{n!}$ for $d+1$ points which solves $\mathrm{GPE}_{\pm}$ . Assuming $1$ -PACC [AA11], $\mathrm{GPE}_{\pm}$ is polynomial equivalent to $\mathrm{GPE}_{\times}.$ Hence there is classical polynomial solves $\mathrm{GPE}_{\times}$ which contradicts our assumption that polynomial hierarchy is infinite. ∎

Finally, we show that approximating $\mathrm{Per}_{z}(X)$ is as hard as approximating $\mathrm{Per}_{z^{*}}(X)$ for any distribution $X$ such that $X,X^{*}$ are identically distributed. A similar proof idea applies to $|\mathrm{Per}_{z}(X)|^{2}$ as well.

Lemma 6.7.

For any distribution $X$ such that $X,X^{*}$ are identically distributed, if there is an algorithm running in time $\operatorname{poly}(n,1/\delta,1/\epsilon)$ for approximating $\mathrm{Per}_{z}(X)$ to within multiplicative (resp. additive) error $\epsilon$ with probability $1-\delta$ , then there is an algorithm which approximates $\mathrm{Per}_{z^{*}}(X)$ to within multiplicative (resp. additive) error $\epsilon$ with probability $1-\delta$ .

Proof.

By the assumption, let $\mathcal{A}(X,0^{1/\epsilon},0^{1/\delta})$ be an algorithm that approximates $\mathrm{Per}_{z}(X)$ to error $\epsilon$ with probability $1-\delta$ .

Since $\mathrm{Per}_{z^{*}}(X)^{*}=\mathrm{Per}_{z}(X^{*})$ and $X,X^{*}$ are identically distributed, for computing $\mathrm{Per}_{z^{*}}(X)$ , the algorithm $\mathcal{B}$ runs $\mathcal{A}(X^{*},0^{1/\epsilon},0^{1/\delta})$ to obtain an approximation $\tilde{P}$ of $\mathrm{Per}_{z}(X^{*})$ with probability $1-\delta$ over $X^{*}$ . Then since the absolute value of a complex number does not change by taking complex conjugate,

	$\displaystyle\Pr_{X}[\|\tilde{P}-\mathrm{Per}_{z}(X^{})\|\leq\alpha(z,X^{})]$	$\displaystyle=\Pr_{X}[\|\tilde{P}^{}-\mathrm{Per}_{z^{}}(X)\|\leq\alpha(z^{*},X)]$
		$\displaystyle\geq 1-\delta.$		(83)

Here for multiplicative error

\displaystyle\alpha(z,X^{*})=\epsilon|\mathrm{Per}_{z}(X^{*})|=\epsilon|\mathrm{Per}_{z^{*}}(X)|=\alpha(z^{*},X).

(84)

For additive error,

\displaystyle\alpha(z,X^{*})=\epsilon\sqrt{n!}=\alpha(z^{*},X).

(85)

∎

7 Open Problems and Discussion

In this paper, we studied the computational complexity of quantum determinants, a $q$ -deformation of matrix permanents. The $q$ -permanent of a matrix $X$ is defined and it generalizes both determinant and permanent. It is shown that computing the $q$ -permanent is $\mathsf{Mod}_{p}\mathsf{P}$ -hard for a primitive $m$ -th root of unity $q$ for odd prime power $m=p^{k}$ . This result implies that an efficient algorithm for computing $q$ -permanent would result in a collapse of the polynomial hierarchy. We also showed that an efficient approximation algorithm for $q$ -permanent would also imply a collapse of the polynomial hierarchy. The hardness of computing $q$ -permanent remains to hold for a wide range of distributions by random self-reducibility. The techniques developed for the hardness of permanent can be generalized to $z$ -permanents for both worst and average cases.

Here we include a few interesting questions that are not solved in this paper.

•

It is known that there is a polynomial-time algorithm for determining whether $\mathrm{Per}(X)\neq 0$ for $\{0,1\}$ -matrix $X$ by determining if there is a perfect matching in a bipartite graph whose adjacent matrix is $X$ . Is the property about $z$ -permanent efficiently computable for $z\neq 1$ , i.e., is there a polynomial-time algorithm for determining whether $\mathrm{Per}_{z}(X)\neq 0$ ?
•

We have shown that Problem 2 is in $\mathsf{NP}$ . Does Problem 2 have polynomial-time algorithm?
•

In this work, we have discussed the computational complexity of $z$ -permanent for $z\in\mathbb{T}$ . It is natural to consider other subsets of the complex numbers. For example, what is the computational complexity of $z$ -permanent for real $z$ ?
•

As explained in Section 3.2, the techniques we used for proving the hardness of $\zeta_{m}$ -permanent can only work for the special case where $m$ is a prime power. Thus our result does not rule out the existence of an efficient algorithm for non-prime-power $m$ . Is there a polynomial-time algorithm computing $\zeta_{m}$ -permanent where $m$ is not prime power?
•

First proposed by Aaronson and Arkhipov, the permanent anti-concentration conjecture is crucial for showing the equivalence of additive and multiplicative approximation of $1$ -permanent for Gaussian matrices.

Relation between the permanent anti-concentration conjecture and the $z$ -permanent anti-concentration Conjecture 3. Can one prove one from another or use polynomial interpolation to give multiple-to-one reduction?
•

Higher moment of $|\mathrm{Per}_{z}(X)|^{2}$ when $X$ is drawn from complex Gaussian $\mathcal{G}$ .

Acknowledgement

We thank Scott Aaronson, Mohammad Hafezi, and Dominik Hangleiter for useful discussions. EJ was supported by ARO W911NF-15-1-0397, National Science Foundation QLCI grant OMA-2120757, AFOSRMURI FA9550-19-1-0399, Department of Energy QSA program, and the Simons Foundation. SHH acknowledges the support from Simons Investigator in Computer Science award, award number 510817.

References

[AA11] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333–342, 2011.
[Ben87] Georgia Benkart. Abstract algebra, by in herstein. The American Mathematical Monthly, 94(8):804–806, 1987.
[BKW19] Andreas Björklund, Petteri Kaski, and Ryan Williams. Generalized kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica, 81(10):4010–4028, 2019.
[BL94] RB Bapat and AK Lal. Inequalities for the q-permanent. Linear Algebra and its Applications, 197:397–409, 1994.
[BLW17] Marek Bożejko, Eugene Lytvynov, and Janusz Wysoczański. Fock representations of q-deformed commutation relations. Journal of Mathematical Physics, 58(7):073501, 2017.
[BP86] Dario Bini and Victor Pan. Polynomial division and its computational complexity. Journal of Complexity, 2(3):179–203, 1986.
[Bro86] Andrei Z Broder. How hard is it to marry at random?(on the approximation of the permanent). In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 50–58, 1986.
[BS91] Marek Bożejko and Roland Speicher. An example of a generalized brownian motion. Communications in Mathematical Physics, 137(3):519–531, 1991.
[Bür00] Peter Bürgisser. The computational complexity of immanants. SIAM Journal on Computing, 30(3):1023–1040, 2000.
[BV] ODYSSEAS BAKAS and MARCO VITTURI. The polynomial method lecture 4 applications in technology.
[Cur21] Radu Curticapean. A full complexity dichotomy for immanant families. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1770–1783, 2021.
[CX15] Radu Curticapean and Mingji Xia. Parameterizing the permanent: Genus, apices, minors, evaluation mod 2k. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 994–1009. IEEE, 2015.
[CX21] Radu Curticapean and Mingji Xia. Parameterizing the permanent: Hardness for $k\_8$ -minor-free graphs. arXiv preprint arXiv:2108.12879, 2021.
[DF10] CM Da Fonseca. The $\mu$ -permanent of a tridiagonal matrix, orthogonal polynomials, and chain sequences. Linear algebra and its applications, 432(5):1258–1266, 2010.
[dF18] Carlos M da Fonseca. The $\mu$ -permanent revisited. arXiv preprint arXiv:1804.02231, 2018.
[DJ21] Samir Datta and Kishlaya Jaiswal. Parallel polynomial permanent mod powers of 2 and shortest disjoint cycles. arXiv preprint arXiv:2106.00714, 2021.
[dRA13] Nicolas de Rugy-Altherre. Determinant versus permanent: salvation via generalization? the algebraic complexity of the fermionant and the immanant. arXiv preprint arXiv:1309.2156, 2013.
[DS] EDUARDO MARQUES DE SA. On q-permanent expansions and a theorem on cycle surgery.
[dS18] Eduardo Marques de Sá. Noncrossing partitions, noncrossing graphs, and q-permanental equations. Linear Algebra and its Applications, 541:36–53, 2018.
[EG01] Bennett Eisenberg and BK Ghosh. A generalization of markov’s inequality. Statistics & probability letters, 53(1):59–65, 2001.
[EM18] Lior Eldar and Saeed Mehraban. Approximating the permanent of a random matrix with vanishing mean, 2018.
[ER98] Pavel Etingof and Vladimir Retakh. Quantum determinants and quasideterminants. arXiv preprint math/9808065, 1998.
[FK06] Jürg Fröhlich and Thomas Kerler. Quantum groups, quantum categories and quantum field theory. Springer, 2006.
[GM04] Gerald A Goldin and Shahn Majid. On the fock space for nonrelativistic anyon fields and braided tensor products. Journal of mathematical physics, 45(10):3770–3787, 2004.
[GRASRA96] César Gómez, Martí Ruiz-Altaba, Germán Sierra, and Marti Ruiz-Altaba. Quantum groups in two-dimensional physics, volume 139. Cambridge University Press Cambridge, 1996.
[Har85] Werner Hartmann. On the complexity of immanants. Linear and Multilinear Algebra, 18(2):127–140, 1985.
[HHEG20] Jonas Haferkamp, Dominik Hangleiter, Jens Eisert, and Marek Gluza. Contracting projected entangled pair states is average-case hard. Physical Review Research, 2(1):013010, 2020.
[HJ12] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[Lal98] AK Lal. Inequalities for the q-permanent. ii. Linear algebra and its applications, 274(1-3):1–16, 1998.
[Lan12] Serge Lang. Cyclotomic fields I and II, volume 121. Springer Science & Business Media, 2012.
[Lan13] Serge Lang. Algebraic number theory, volume 110. Springer Science & Business Media, 2013.
[Lip91] Richard Lipton. New directions in testing. Distributed computing and cryptography, 2:191–202, 1991.
[LW12] Claude Levesque and Michel Waldschmidt. Approximation of an algebraic number by products of rational numbers and units. Journal of the Australian Mathematical Society, 93(1-2):121–131, 2012.
[M⁺97] Meena Mahajan et al. Determinant: Combinatorics, algorithms, and complexity. Chicago Journal of Theoretical Computer Science, 1997(5), 1997.
[Maj00] Shahn Majid. Foundations of quantum group theory. Cambridge university press, 2000.
[MM11] Stephan Mertens and Cristopher Moore. The complexity of the fermionant, and immanants of constant width. arXiv preprint arXiv:1110.1821, 2011.
[Neu13] Jürgen Neukirch. Algebraic number theory, volume 322. Springer Science & Business Media, 2013.
[Nez21] Sepehr Nezami. Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling. arXiv preprint arXiv:2104.06423, 2021.
[PS90] V Pasquier and H Saleur. Common structures between finite systems and conformal field theories through quantum groups. Nuclear Physics B, 330(2-3):523–556, 1990.
[R⁺76] Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
[RA13] Nicolas de Rugy-Altherre. Determinant versus permanent: salvation via generalization? In Conference on Computability in Europe, pages 87–96. Springer, 2013.
[RS62] J Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6(1):64–94, 1962.
[Spi20] Dylan Spivak. Immanants and their applications in quantum optics. PhD thesis, 2020.
[TAG93] Hiroyuki TAGAWA. q-analogues of determinants and symmetric chain decompositions. Tokyo Journal of Mathematics, 16(2):311–320, 1993.
[TO92] Seinosuke Toda and Mitsunori Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 21(2):316–328, 1992.
[Tod91] Seinosuke Toda. Pp is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865–877, 1991.
[Val79a] Leslie G Valiant. Completeness classes in algebra. In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 249–261, 1979.
[Val79b] Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189–201, 1979.
[Vau75] RC Vaughan. Bounds for the coefficients of cyclotomic polynomials. Michigan Mathematical Journal, 21(4):289–295, 1975.
[Wei98] Edwin Weiss. Algebraic number theory. Courier Corporation, 1998.
[Wei04] Eric W Weisstein. Fermat’s little theorem. https://mathworld. wolfram. com/, 2004.
[Yan91] Kung-Wei Yang. q–determinants and permutations. The Fibonacci Quarterly, 29:160–163, 1991.

Appendix A Moments of $z$ -permanents and Anti-Concentration Conjecture

Anti-concentration not only plays an important rule in the Boson Sampling [AA11] but also has its own interests in random matrix theory [EM18, Nez21]. In this section, we discuss the moments of $z$ -permanents drawn from i.i.d complex Gaussian and anti-concentration conjecture of $z$ -permanent.

First, we explicitly calculate the first moment of $|\mathrm{Per}_{z}(X)|^{2}$ . Interestingly, the result does not depend on $z$ .

Lemma A.1.

For $z\in\mathbb{T}$ , $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{2}]=n!$

Proof.

By direct calculation,

$\displaystyle\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[\|\mathrm{Per}_{z}(X)\|^{2}]$	$\displaystyle=\sum_{\sigma,\alpha}z^{\ell(\sigma)-\ell(\alpha)}\operatorname{\mathbb{E}}_{X\sim\mathcal{G}}\mathopen{}\mathclose{{}\left[\prod_{i}X_{i,\sigma(i)}X^{}_{i,\alpha(i)}}\right]$
	$\displaystyle=\sum_{\sigma,\alpha}z^{\ell(\sigma)-\ell(\alpha)}\prod_{i}\mathbbm{1}[\sigma(i)=\alpha(i)]$
	$\displaystyle=\sum_{\sigma,\alpha}z^{\ell(\sigma)-\ell(\alpha)}\cdot\mathbbm{1}[\sigma=\alpha]$
	$\displaystyle=\sum_{\sigma}1=n!.$	(86)

∎

In fact, if we replace $\mathcal{G}$ with a random matrix whose each entry is independently sampled from any distribution of zero mean and unit variance, the second moment is $n!$ . Now we want to calculate $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]$ . We first recall the computation of $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}(X)|^{4}]$ in [AA11].

Lemma A.2.

For $z=1$ , $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]=(n!)^{2}(n+1)$ .

Proof.

By direction calculation,

\displaystyle\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]

\displaystyle=\sum_{\sigma,\tau,\alpha,\beta}z^{\ell(\sigma)+\ell(\tau)-\ell(\alpha)-\ell(\beta)}\cdot M(\sigma,\tau,\alpha,\beta),

(87)

where

\displaystyle M(\sigma,\tau,\alpha,\beta):=\prod_{i}\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[X_{i,\sigma(i)}X_{i,\tau(i)}X_{i,\alpha(i)}^{*}X_{i,\beta(i)}^{*}].

(88)

If $\sigma\cup\tau\neq\alpha\cup\beta$ , $M(\sigma,\tau,\alpha,\beta)=0$ .

To compute $M(\sigma,\tau,\alpha,\beta)$ , we first provide some intuition: if $\tau=1$ and $\sigma=\gamma_{1}\ldots\gamma_{m}$ , where each $\gamma_{i}$ is a cycle of length greater than 1. Then either $\alpha$ has $\gamma_{i}$ and $\beta$ has the identity, or $\alpha$ has the identity and $\beta$ has $\gamma_{i}$ . This implies that $\beta\alpha=\sigma$ and there are $2^{m}$ choices of $\alpha$ . For arbitrary $\tau$ , we can “shift” each permutation by multiplying $\tau^{-1}$ to the right and reducing to the above simpler case. Since $\sigma\tau^{-1}$ and $\tau\sigma^{-1}$ have the same cycle type, the above argument is symmetric with respect to swapping the roles of $\sigma$ and $\tau$ (i.e., we can start with $\sigma=1$ and get the same result).

More formally, if $\sigma\tau^{-1}$ is of cycle type $\lambda=(\lambda_{1},\ldots,\lambda_{k})$ with $\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{m}>\lambda_{m+1}=\ldots=\lambda_{k}=1$ , we may write in the form

\displaystyle\sigma\tau^{-1}=\gamma_{1}\gamma_{2}\ldots\gamma_{m}.

(89)

Then if $\sigma\cup\tau=\alpha\cup\beta$ , it holds that

\displaystyle(\alpha,\beta)\in A(\sigma,\tau)

(90)

where

\displaystyle A(\sigma,\tau)=\mathopen{}\mathclose{{}\left\{(\alpha,\beta):\alpha=\gamma_{1}^{b_{1}}\ldots\gamma_{m}^{b_{m}}\tau,\beta=\tau\alpha^{-1}\sigma,b_{1},\ldots,b_{m}\in\{0,1\}}\right\}.

(91)

Clearly for every $(\sigma,\tau)$ such that $\sigma\tau^{-1}$ is of type $\lambda$ , $|A(\sigma,\tau)|=2^{m}$ since there are $2^{m}$ choice of $\alpha$ and $\beta$ is uniquely determined once $\alpha$ is fixed.

Furthermore, for each fixed point $i$ , $\sigma(i)=\tau(i)=\alpha(i)=\beta(i)$ , and thus $\prod_{i:\sigma(i)=\tau(i)}\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|X_{i,\sigma(i)}|^{4}]=2^{k-m}$ . Therefore, we have shown that

\displaystyle M(\sigma,\tau,\alpha,\beta)=2^{F(\sigma\tau^{-1})}\cdot\mathbbm{1}[(\alpha,\beta)\in A(\sigma,\tau)]

(92)

and

\displaystyle\sum_{\alpha,\beta}M(\sigma,\tau,\alpha,\beta)=2^{C(\sigma\tau^{-1})},

(93)

where $F(\xi)$ is the number of fixed points, and $C(\xi)$ is the number of cycles in $\xi\in S_{n}$ . For $z=1$ ,

\displaystyle\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}(X)|^{4}]

\displaystyle=\sum_{\sigma,\tau,\alpha,\beta}M(\sigma,\tau,\alpha,\beta)=\sum_{\sigma,\tau}2^{C(\sigma\tau^{-1})}=(n!)^{2}(n+1).

(94)

Here we have applied the fact that $\sum_{\xi\in S_{n}}2^{C(\xi)}=(n+1)!$ . ∎

However, we can not get the explicit formula for the $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]$ because when $\sigma\cup\tau=\alpha\cup\beta$ , the inversion number can be nonzero: namely $\ell(\sigma)+\ell(\tau)-\ell(\alpha)-\ell(\beta)\neq 0$ . But we can still get the following result:

Lemma A.3.

For $z\in\mathbb{T}$ , $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]\leq\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}(X)|^{4}].$

The proof is simple since $M(\sigma,\tau,\alpha,\beta)\geq 0$ and $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]$ must be a positive number. So we have

$\displaystyle\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[\|\mathrm{Per}_{z}(X)\|^{4}]$	$\displaystyle=\sum_{\sigma,\tau,\alpha,\beta}z^{\ell(\sigma)+\ell(\tau)-\ell(\alpha)-\ell(\beta)}\cdot M(\sigma,\tau,\alpha,\beta)$
	$\displaystyle\leq\sum_{\sigma,\tau,\alpha,\beta}M(\sigma,\tau,\alpha,\beta)$
	$\displaystyle=\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[\|\mathrm{Per}(X)\|^{4}].$	(95)

More generally, we have the following inequality.

Lemma A.4.

For $z\in\mathbb{T}$ and $k\geq 2$ , $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{2k}]\leq\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}(X)|^{2k}].$

Due to the lack of efficient formula for computing permanent, showing anti-concentration conjecture of permanent is hard. As we show in the paper, There is no efficient formula for general $z$ -permanent. So we believe that showing the anti-concentration conjecture of $z$ -permanent is also a hard problem. However, the higher moment of $z$ -permanent is less than permanent (but with the same first moment). This gives us a hint that anti-concentration is also true for $z$ -permanent. We have the following similar as $z=1$ .

Theorem A.5 (Weak Anti-Concentration of $z$ -Permanent).

For $\alpha<1,$

\Pr_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{2}>\alpha\cdot n!]>\frac{(1-\alpha)^{2}}{n+1}.

(96)

Proof.

By Chebyshev’s inequality using $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{2}]=n!$ and $\operatorname*{\mathbb{E}}_{X\sim\mathcal{G}}[|\mathrm{Per}_{z}(X)|^{4}]\leq n!^{2}(n+1)$ , the bound immediately follows. ∎

Appendix B Strong Autocorrelation Property

Consider a random variable $X$ with a real distribution $\mathcal{F}$ with mean $0$ and variance $1.$ We denote it as $X\sim\mathcal{F}_{\mathbb{R}}(0,1).$ We define $\mathcal{F}_{\mathbb{R}}(\mu,\sigma^{2})$ with mean $\mu$ and variance $\sigma^{2}$ by shifting and scale the random variable $X\to\mu+\sigma^{2}X.$ We denote such distribution $\mathcal{F}_{\mathbb{R}}(\mu,\sigma^{2})$ . We pick $\epsilon$ such that $\epsilon<\frac{1}{2}.$

$\displaystyle X$	$\displaystyle=\mathcal{F}_{\mathbb{R}}(0,1)^{n}$	(97)
$\displaystyle\mathcal{D}_{1}$	$\displaystyle=\mathcal{F}_{\mathbb{R}}\mathopen{}\mathclose{{}\left(0,\mathopen{}\mathclose{{}\left(1-\varepsilon}\right)^{2}}\right)^{n},$	(98)
$\displaystyle\mathcal{D}_{2}$	$\displaystyle=\prod_{i=1}^{n}\mathcal{F}_{\mathbb{R}}\mathopen{}\mathclose{{}\left(v_{i},1}\right)$	(99)

We define

G(\epsilon)=\mathopen{}\mathclose{{}\left\|\mathcal{F}_{\mathbb{R}}(0,1)-\mathcal{F}_{\mathbb{R}}(0,(1-\epsilon)^{2})}\right\|,H(v_{i})=\mathopen{}\mathclose{{}\left\|\mathcal{F}_{\mathbb{R}}(0,1)-\mathcal{F}_{\mathbb{R}}(v_{i},1)}\right\|.

(100)

Lemma B.1.

If $G(\epsilon),\frac{dG(\epsilon)}{d\epsilon}$ are both continuous when $\epsilon\in[0,\frac{1}{2}]$ and $H(x),\frac{dH(x)}{dx}$ are both continuous when $x\in[0,1]$ . Then,

	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{1}-X}\right\\|$	$\displaystyle\leq nM_{1}\epsilon,\forall\epsilon\in[0,1/2]$
	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{2}-X}\right\\|$	$\displaystyle\leq M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{1},\,$

where $M_{1},M_{2}$ are independent of $\epsilon,v_{i}$ for every $i$ .

Proof.

We first prove the first inequality:

\displaystyle\mathopen{}\mathclose{{}\left\|\mathcal{D}_{1}-X}\right\|\leq n\mathopen{}\mathclose{{}\left\|\mathcal{F}_{\mathbb{R}}(0,1)-\mathcal{F}_{\mathbb{R}}(0,(1-\epsilon)^{2})}\right\|=n|G(\epsilon)|\leq n\epsilon M_{1}.

In order to bound the difference, we use the mean value theorem on variable $\epsilon$ . Notice that $G(0)=0$ . For all $\epsilon\in[0,\frac{1}{2}]$ we have:

|G(\epsilon)-G(0)|\leq\epsilon\max_{\epsilon\in[0,\frac{1}{2}]}\mathopen{}\mathclose{{}\left|\frac{dG(\epsilon)}{d\epsilon}}\right|\leq\epsilon M_{1}.

(101)

Here $M_{1}$ is defined to be $\mathopen{}\mathclose{{}\left|\frac{dG(\epsilon)}{d\epsilon}}\right|$ . The existence is guaranteed due to the continuity of $\mathopen{}\mathclose{{}\left|\frac{dG(\epsilon)}{d\epsilon}}\right|$ and the following lemma.

Lemma B.2 (Extreme value theorem [R⁺76]).

A continuous function from a non-empty compact space to a subset of the real numbers attains a maximum and a minimum.

So finish the proof of the first inequality.

The second inequality follows using again the triangle inequality:

\displaystyle\mathopen{}\mathclose{{}\left\|\mathcal{D}_{2}-X}\right\|\leq\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\|\mathcal{F}_{\mathbb{R}}(0,1)-\mathcal{F}_{\mathbb{R}}(v_{i},1)}\right\|\leq\sum_{i=1}^{n}|v_{i}|M_{2}\leq M_{2}\mathopen{}\mathclose{{}\left\|v}\right\|_{1}

Here we use the same trick (notice $H(0)=0$ , without loss of generality, we can assume $v_{i}\geq 0.$ )

|H(v_{i})-H(0)|\leq|v_{i}|\max_{x\in[0,1]}\mathopen{}\mathclose{{}\left|\frac{dH(x)}{dx}}\right|\leq|v_{i}|M_{2}.

(102)

Here $M_{2}$ is defined to be $\mathopen{}\mathclose{{}\left|\frac{dH(x)}{dx}}\right|$ . ∎

We can define complex random variable $Z=X+iY$ , $X\sim\mathcal{F}_{\mathbb{R}}(\mu_{1},1/2),Y\sim\mathcal{F}_{\mathbb{R}}(\mu_{2},1/2)$ and $X,Y$ are independent. So then $Z\sim\mathcal{F}_{\mathbb{C}}(\mu_{1}+i\mu_{2},1).$ It will be helpful to think of each complex coordinate as two real coordinates and $v$ is a vector in $\mathbb{R}^{2N}$ .

Corollary B.3.

If we consider the complex version composed by real and with same condition:

$\displaystyle X$	$\displaystyle=\mathcal{F}_{\mathbb{C}}(0,1)^{n}=\mathcal{F}_{\mathbb{R}}(0,1/2)^{2n}$	(103)
$\displaystyle\mathcal{D}_{1}$	$\displaystyle=\mathcal{F}_{\mathbb{C}}\mathopen{}\mathclose{{}\left(0,\mathopen{}\mathclose{{}\left(1-\varepsilon}\right)^{2}}\right)^{n}=\mathcal{F}_{\mathbb{R}}(0,(1-\epsilon)^{2}/2)^{2n},$	(104)
$\displaystyle\mathcal{D}_{2}$	$\displaystyle=\prod_{i=1}^{n}\mathcal{F}_{\mathbb{C}}\mathopen{}\mathclose{{}\left(v_{i},1}\right)$	(105)

We have:

	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{1}-X}\right\\|$	$\displaystyle\leq 2nM_{1}\epsilon,\forall\epsilon\in[0,\frac{1}{2}]$
	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{2}-X}\right\\|$	$\displaystyle\leq M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{1}\leq\sqrt{2n}M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{2}.$

In the final line, we use $1$ - and $2$ -norm inequalities. Notice that for the $1$ -norm, we imagine $\nu$ as an $\mathbb{R}^{2n}$ vectors but for $2$ -norm, we pack them into $\mathbb{C}^{n}$ .

Notice that in [AA11], one can use rotational invariance to get the tighter bound for Gaussian matrices. But it is enough for our purpose.

$\displaystyle\|\alpha-\alpha_{i}\|$	$\displaystyle=\frac{\|\mathrm{Per}_{z}(X)-\alpha_{i}\mathrm{Per}_{z}(Y)\|}{\|\mathrm{Per}_{z}(Y)\|}$
	$\displaystyle\leq\frac{\sqrt{g\mathcal{O}(X^{[\alpha_{i}]})}}{\|\mathrm{Per}_{z}(Y)\|}$
	$\displaystyle\leq g\sqrt{\frac{\mathcal{O}(X^{[\alpha_{i}]})}{\mathcal{O}(Y)}}$	(46)

$\displaystyle\|a_{i}\|$	$\displaystyle\leq\mathopen{}\mathclose{{}\left\|s_{i}-\sum_{j=0}^{i}q_{j}t_{i-j}}\right\|$
	$\displaystyle\leq\max_{i}\|s_{i}\|+(\phi(m)-1)\cdot\max_{i}\|q_{i}\|\cdot\max_{i}\|t_{i}\|$
	$\displaystyle\leq n!+(\phi(m)-1)\cdot 2^{O((m-\phi(m))\cdot m\log m+n\log n)}\cdot M.$	(60)

	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{1}-X}\right\\|$	$\displaystyle\leq nM_{1}\epsilon,\forall\epsilon\in[0,1/2]$
	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{2}-X}\right\\|$	$\displaystyle\leq M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{1},\,$

	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{1}-X}\right\\|$	$\displaystyle\leq 2nM_{1}\epsilon,\forall\epsilon\in[0,\frac{1}{2}]$
	$\displaystyle\mathopen{}\mathclose{{}\left\\|\mathcal{D}_{2}-X}\right\\|$	$\displaystyle\leq M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{1}\leq\sqrt{2n}M_{2}\mathopen{}\mathclose{{}\left\\|v}\right\\|_{2}.$

The Computational Complexity of Quantum Determinants

Abstract

1 Introduction

1.1 Our Contributions

1.1.1 Worst-case Hardness

Theorem 1.1 (Hardness of zz-permanent, informal).

1.1.2 Hardness of Approximation

Theorem 1.2 (Hardness of approximation, informal).

1.1.3 Average-Case Hardness of Exactly Computing zz-Permanent

1.1.4 Average-Case Hardness of Approximating zz-Permanent

1.2 Related Work

1.3 Organization

2 Preliminaries

2.1 Introduction to Algebraic Number Theory

Definition 2.1.

Definition 2.2.

Definition 2.3.

Theorem 2.4 ([Lan13]).

Definition 2.5 (Ring of integers).

Definition 2.6 (Cyclotomic fields).

Theorem 2.7 ([Lan13]).

Definition 2.8 (Euler’s totient function [Lan13]).

Theorem 2.9 ([RS62]).

Definition 2.10 ([Lan12]).

Theorem 2.11 (Bounds for the coefficients of cyclotomic polynomials [Vau75]).

Theorem 2.12 (Liouville’s approximation theorem [LW12]).

Theorem 2.13 (Fermat’s little theorem [Wei04]).

Theorem 2.14.

Proof.

2.2 Properties of zz-permanent

2.3 Common Tasks Related to Permanent

Problem 1 (GPE×\mathrm{GPE}_{\times}).

Conjecture 1.

Conjecture 2.

3 Hardness of zz-permanent for {0,1}\{0,1\}-matrices

3.1 Cube Roots of Unity

Definition 3.1 (𝖬𝗈𝖽k​𝖯\mathsf{Mod}_{k}\mathsf{P}).

Theorem 3.2 (Valiant [Val79a]).

Theorem 3.3.

Proof.

Theorem 3.4 (Toda theorem [Tod91, TO92]).

Theorem 3.5.

3.2 Primitive mmth roots of unity for prime power mm

Definition 3.6 (Representation of an algebraic integer).

Theorem 3.7.

Proof.

Corollary 3.8.

Theorem 3.9.

Proof.

Theorem 3.10.

3.3 Hardness of Rational Phases

Theorem 3.11.

Proof.

4 Hardness of Approximating ζm\zeta_{m}-permanent

4.1 Reducing the Error

Lemma 4.1.

Proof.

Theorem 4.2.

Proof.

Corollary 4.3 (cf. [AA11, Theorem 28]).

Proof.

Corollary 4.4.

Proof.

4.2 A Search-to-Decision Reduction

Definition 4.5 (Representation of ℤ​[ζm]\mathbb{Z}[\zeta_{m}]).

Theorem 4.6 (Bounds on the coefficients of cyclotomic polynomials [Vau75]).

Lemma 4.7 ([BP86, Lemma 2]).

Corollary 4.8.

Proof.

Corollary 4.9.

Proof.

Problem 2 (Close algebraic integer problem (caip)).

Theorem 4.10.

Proof.

Theorem 4.11.

Proof.

5 Average-case Hardness

Theorem 5.1 (Berlekamp-Welch algorithm [BV]).

Definition 5.2 (Strong autocorrelation property).

Theorem 5.3 (Random self-reducibility of zz-permanent).

Theorem 1.1 (Hardness of $z$ -permanent, informal).

1.1.3 Average-Case Hardness of Exactly Computing $z$ -Permanent

1.1.4 Average-Case Hardness of Approximating $z$ -Permanent

2.2 Properties of $z$ -permanent

Problem 1 ( $\mathrm{GPE}_{\times}$ ).

3 Hardness of $z$ -permanent for $\{0,1\}$ -matrices

Definition 3.1 ( $\mathsf{Mod}_{k}\mathsf{P}$ ).

3.2 Primitive $m$ th roots of unity for prime power $m$

4 Hardness of Approximating $\zeta_{m}$ -permanent

Definition 4.5 (Representation of $\mathbb{Z}[\zeta_{m}]$ ).

Theorem 5.3 (Random self-reducibility of $z$ -permanent).

Problem 3 ( $\mathrm{GPE}_{\times}$ ).

Problem 4 ( $\mathrm{GPE}_{\pm}$ ).

Problem 5 ( $\mathrm{PE}_{\mathcal{H},z,\times}$ ).

Problem 6 ( $\mathrm{PE}_{\mathcal{H},z,\pm}$ ).

Definition 6.1 ( $\mathcal{O}_{\times},\mathcal{O}_{\pm}$ ).

Conjecture 3 ( $z$ -permanent anti-concentration conjecture ( $z$ -PACC)).

Appendix A Moments of $z$ -permanents and Anti-Concentration Conjecture

Theorem A.5 (Weak Anti-Concentration of $z$ -Permanent).

Lemma B.2 (Extreme value theorem [R⁺76]).