# An overview of generalized entropic forms

V. Ilić  Mathematical Institute of the Serbian Academy of Sciences and Arts,
Kneza Mihaila 36, 11000 Beograd, Serbia  J. Korbel  Section for Science of
Complex Systems, CeMSIIS, Medical University of Vienna, Vienna, Austria;
Complexity Science Hub Vienna, Josefstädterstrasse 39, 1080 Vienna, Austria;
Faculty of Nuclear Sciences and Physical Engineering, Czech Technical
University in Prague, Břehová 7, 115 19 Prague, Czech Republic  S. Gupta
Department of Physics, Ramakrishna Mission Vivekananda Educational and
Research Institute, Belur Math, India  A.M. Scarfone  Istituto dei Sistemi
Complessi (ISC-CNR) c/o Politecnico di Torino
Corso Duca degli Abruzzi 24, 10129 Torino, Italy.
<EMAIL_ADDRESS>
###### Abstract

The aim of this focus letter is to present a comprehensive classification of
the main entropic forms introduced in the last fifty years in the framework of
statistical physics and information theory. Most of them can be grouped into
three families, characterized by two-deformation parameters, introduced
respectively by Sharma, Taneja, and Mittal (entropies of degree
$(\alpha,\,\beta$)), by Sharma and Mittal (entropies of order
$(\alpha,\,\beta)$), and by Hanel and Thurner (entropies of class $(c,\,d)$).
Many entropic forms examined will be characterized systematically by means of
important concepts such as their axiomatic foundations à la Shannon-Khinchin
and the consequent composability rule for statistically independent systems.
Other critical aspects related to the Lesche stability of information measures
and their consistency with the Shore-Johnson axioms will be briefly discussed
on a general ground.

###### pacs:

05.20.-y, 89.70.+c, 05.90.+m

##  1 Historical introduction

The history of entropy begins around the nineteenth century in the then-
emerging thermodynamics theory following the studies of Carnot aimed at the
attempt to optimize the efficiency of the conversion of heat into mechanical
work. This concept was formalized by Clausius [1] which introduces the word
entropy, whose meaning derives from “transformation produced from within”, a
physical quantity whose variation is defined in

$\displaystyle dS=\int{\delta Q_{\rm rev}\over T}\ ,$

for any reversible thermodynamic transformation. The function $S$, implicitly
introduced in this way, is named thermodynamic entropy and the validity of
this relation has never been questioned.

In the same period, Boltzmann began the development of the kinetic theory of
gas by introducing the idea of monads in a modern key and by highlighting in
this way the necessity of employing statistical methods in physics. Boltzmann
studies on the approach to equilibrium of a system deal with the introduction
of the so-called $H$-functional

$\displaystyle H[f]=-\int
f({\mbox{\boldmath${v}$},\,t})\,\ln\big{(}f({\mbox{\boldmath${v}$}},\,t)\big{)}\,d{\mbox{\boldmath${v}$}}\
,$

for a single-particle probability distribution function
$f({\mbox{\boldmath${v}$}},\,t)$ that, together with the relation $dH/dt\geq
0$, states the celebrated $H$-theorem [2].
Boltzmann results have then been generalized by Gibbs [3] to the case of a
canonical ensemble, i.e., a collection of $W$ microstates with a discrete set
of energy levels $E_{i}$ belonging to the same macrostate
$E=\sum_{i}E_{i}\,p_{i}$, where $p_{i}$ is the probability that occurs during
the system’s fluctuations. In this context, he introduced the well-known
expression

$\displaystyle S[{\mbox{\boldmath${p}$}}]=-k_{\rm
B}\sum_{i=1}^{W}p_{i}\,\ln(p_{i})\ ,$ (1)

with $k_{\rm B}$ the Boltzmann constant, today known as Boltzmann-Gibbs
entropy, recognized in statistical mechanics to measure the microscopic
disorder or randomness of a system with a large number of constituents. The
legitimacy of this last statement finds validity in the expression

$\displaystyle S=k_{B}\,\ln W\ ,$

written explicitly in this form by Planck [4] during his studies on the black-
body radiation. Nowadays, this last relation is known as the Boltzmann-Plank
formula of entropy and it is a pillar in the framework of thermostatistics.

Roughly half-century after Boltzmann-Gibbs developments, entropy has been
further conceptualized by Shannon [5] who, to quantify the information carried
by a message, introduced the functional

$\displaystyle H[{\mbox{\boldmath${p}$}}]=-K\sum_{i=1}^{W}p_{i}\,\ln(p_{i})\
,$ (2)

where the constant $K$ is fixed by the choice of the measure unity, being
$p_{i}$ the probability that the $i$-th symbol of $W$ symbols alphabet has to
occur. The functional (2) is named entropy information in analogy with
expression (1) and is recognized in information theory as a quantity that
measures the uncertainty contained in an encoded message.
Shannon entropy has been systematically characterized by Shannon himself and
successively by Khinchin [6] through the introduction of four basic
requirements, nowadays known as the Shannon-Khinchin axioms, which fix
univocally the expression of the information functional.
About ten years after the appearance of the Shannon entropy, by replacing the
standard linear average with the nonlinear (o quasi-linear) average introduced
by Kolmogorov and Nagumo, [7, 8] Rényi [9] proposed the $\alpha$-order
entropic form

$\displaystyle S_{\alpha}[{\mbox{\boldmath${p}$}}]={1\over
1-\alpha}\ln\sum_{i=1}^{W}p_{i}^{\alpha}\ ,$ (3)

a generalization of (2) which is recovered in the $\alpha\to 1$ limit.
After Rényi, a galore of different generalizations of entropy has been
proposed in the framework of information theory. Among the many, the Havrda-
Charvát and Daroczy[10, 11] entropy information

$\displaystyle S_{\beta}[{\mbox{\boldmath${p}$}}]={1\over
1-\beta}\left(\sum_{i=1}^{W}p_{i}^{\beta}-1\right)\ ,$ (4)

for a real deformation parameter $\beta>0$, has been introduced in the late
sixties of the twentieth century.
Near twenty years later, this entropic form has been employed in statistical
physics [12] to obtain an alternative formulation of classical statistical
mechanics, a new border-line research field in statistical physics named
nonextensive statistical mechanics. One of the main reasons to replace the
Shannon-Boltzmann-Gibbs entropy (in the following, Shannon entropy) with its
generalized version, although not fully accepted by the statistical physics
community, is motivated by the loss of ergodicity observed in complex systems,
often not at the thermodynamical limit, governed by strong interactions and
correlations, which show statistical properties that are hardly captured by
the orthodox statistical mechanics theory.

Today, entropy is undoubtedly one of the most general and important concepts
in statistical physics and information theory. It appears with different
meanings in different fields. Many of the generalized expressions found
interesting applications in coding theory, cryptography, statistical inference
theory, non-ergodic systems, fractal dynamics, stochastic thermodynamics,
complex systems, and others. As for its importance, entropy is the protagonist
of the second law of thermodynamics associated with the arrow of time while
the related entropic force may be at the origin of emergent phenomena like
gravity and the space-time structure, as conjectured in the holographic
theories.

##  2 A galore of generalized entropic forms

As known, the Shannon entropy is characterized by a set of four axioms that
univocally define its form [5, 6]. The Shannon-Khinchin (SK) axioms read as:

  * •

A1: Entropy must be an analytically continue function depending only on the
probability $[{\mbox{\boldmath${p}$}}]=(p_{1},\,p_{2},\ldots,\,p_{W})$.

  * •

A2: Entropy must be maximal for uniform distribution
$[{\mbox{\boldmath${p}$}}]=(1/W,\,1/W,\ldots,\,1/W)$.

  * •

A3: Entropy must be invariant under the inclusion of null events with zero
probability.

  * •

A4: Entropy must be strongly additive under the composition of subsystems,
that is

$\displaystyle S(A\cap B)=S(A)+S(B/A)\ .$

Among these, the last one is the most relevant to fix the entropy form. In
fact, let $p_{ij}$ the joint probability distribution of the composed system
$A\cap B$, $p_{i}=\sum_{j}p_{ij}$ the marginal probability distribution of the
system $A$ and $p_{j}=\sum_{i}p_{ij}$ that of the system $B$ then, for a
trace-form entropy $S=\sum_{i}s(p_{i})$, axiom (A4) becomes

$\displaystyle S(A\cap B)=S(A)+\sum_{i=1}^{W}p_{i}\,S\big{(}B/A_{i}\big{)}\ ,$
(5)

where $S(A\cap B)=\sum_{ij}s(p_{ij})$ and
$S(B/A_{i})=\sum_{j}s(p_{ij}/p_{i})$.
Together with the other axioms, (5) has the unique solution given by
$s(x)=x\,\ln(1/x)$, modulo a multiplicative constant. In this way, Shannon
entropy (2) [or (1)] is obtained.
In particular, for statistically independent (SI) systems, axiom (A4)
simplifies in

$\displaystyle S(A\cap B)=S(A)+S(B)\ ,$ (6)

which states the additivity property of the Boltzmann-Gibbs entropy (and in a
certain sense its extensivity).

###  2.1 Havrda-Charvát-Daroczy-Tsallis entropy

In presence of correlations, (5) can be relaxed in a way that allows the
introduction of other possible expressions for the entropic functional. In
[13] it has been advanced the following relation in place of (5)

$\displaystyle S(A\cap
B)=S(A)+\sum_{i=1}^{W}p_{i}^{\beta}\,S\big{(}B/A_{i}\big{)}\ ,$ (7)

that, together with the other axioms, has the unique solution
$s(x)=x\,\ln_{\beta}(1/x)$, where

$\displaystyle\ln_{\beta}(x)={x^{1-\beta}-1\over 1-\beta}\ ,$ (8)

is a generalized version of logarithm controlled by the deformation parameter
$\beta$, such that it reduces to the standard logarithm in the $\beta\to 1$
limit: $\ln_{1}(x)\equiv\ln(x)$. The corresponding entropic form coincides
with (4).
For SI systems (7) becomes

$\displaystyle S(A\cap B)=S(A)+S(B)+(1-\beta)\,S(A)\,S(B)\ ,$ (9)

stating, in this case, the nonadditivity of entropy (4) and it has been one of
the main reasons that led to calling non-extensive statistical mechanics the
physical theory based on the entropic form (4).

###  2.2 Sharma-Taneja-Mittal entropy

A step further in generalizing axiom (A4) has been proposed in [14] and reads

$\displaystyle S(A\cap
B)=\sum_{i=1}^{W}s(p_{i})\sum_{j=1}^{W_{i}}\left({p_{ij}\over
p_{i}}\right)^{\beta}+\sum_{i=1}^{W}p_{i}^{\alpha}\,S(B/A_{i})\ ,$ (10)

that, together with the other axioms has the unique solution
$s(x)=x\,\ln_{\alpha,\beta}(1/x)$, where

$\displaystyle\ln_{\alpha,\beta}(x)={x^{1-\beta}-x^{1-\alpha}\over\alpha-\beta}\
,$

is another generalized version of logarithm by means of two deformation
parameters $\alpha$ and $\beta$. It reduces to the deformed logarithm (8) in
the $\alpha\to 1$ limit: $\ln_{1,\beta}(x)\equiv\ln_{\beta}(x)$ and to the
standard logarithm in the $(\alpha,\,\beta)\to(1,\,1)$ limit:
$\ln_{1,1}(x)\equiv\ln(x)$. The resulting entropic form

$\displaystyle
S_{\alpha,\,\beta}[{\mbox{\boldmath${p}$}}]=\sum_{i=1}^{W}{p_{i}^{\beta}-p_{i}^{\alpha}\over\alpha-\beta}\
.$ (11)

has been introduced independently by Sharma and Taneja [15], and Mittal [16],
as the unique solution of relation

$\displaystyle S(A\cap
B)=S(A)\sum_{j=1}^{W^{\prime}}p_{j}^{\beta}+\sum_{i=1}^{W}p_{i}^{\alpha}\,S(B)\
,$

which follows from (10) for SI systems. In this case it dictates the
composition law of entropy (11).

Sharma-Taneja-Mittal entropy, also named entropies of degree
$(\alpha,\,\beta$), captures some interesting one-parameter entropic forms
obtained by fixing opportunely the parameters $\alpha$ and $\beta$, as
reported in Table 1.

Table 1: Entropic forms of degree $(\alpha,\,\beta$) Parameters | Entropy | Ref.
---|---|---
$\alpha=1,\quad\quad\beta=1$ | $-\sum_{i}p_{i}\,\ln(p_{i})$ | [5]
$\alpha=1$ | $\sum_{i}{p_{i}^{\beta}-1\over 1-\beta}$ | [10, 11, 12]
$\alpha=1+\kappa,\quad\beta=1-\kappa\hskip 28.45274pt$ | $-\sum_{i}{p_{i}^{1+\kappa}-p_{i}^{1-\kappa}\over 2\,\kappa}\hskip 28.45274pt$ | [17]
$\alpha=\beta$ | $-\sum_{i}p_{i}^{\alpha}\,\ln(p_{i})$ | [18]
$\alpha=q,\quad\quad\beta=1/q\ \ \ \ \ $ | $-\sum_{i}{p_{i}^{q}-p_{i}^{1/q}\over q-1/q}\hskip 36.98857pt$ | [19]

###  2.3 Rényi entropy

In general, trace-form entropies like the ones introduced above can be viewed
as linear average of an appropriate Hartley function $I(x)$ representing the
elementary information gained, according to

$\displaystyle S[{\mbox{\boldmath${p}$}}]=\mathbbm{E}_{\rm
lin}\big{(}I[{\mbox{\boldmath${p}$}}]\big{)}\ ,$ (12)

with $\mathbbm{E}_{\rm lin}(x)=\sum_{i}x_{i}\,p_{i}$. In particular, the
family of Sharma-Taneja-Mital entropies follows from
$I(x)=\ln_{\alpha,\beta}(1/x)$.
A different approach to derive generalized entropies can be obtained following
Rényi. In the seminal work [9], searching for the most general expression of a
functional that satisfies axioms (A1)-(A3) and the more soft composability
condition given by (6), he replaced (12) with the quasi-linear average

$\displaystyle S[{\mbox{\boldmath${p}$}}]=\mathbbm{E}_{\rm
KN}\big{(}I[{\mbox{\boldmath${p}$}}]\big{)}\ ,$ (13)

introduced by Kolmogorov-Nagumo, where $\mathbbm{E}_{\rm
KN}({\mbox{\boldmath${x}$}})=f^{-1}\left(\mathbbm{E}_{\rm
lin}\big{(}f({\mbox{\boldmath${x}$}})\big{)}\right)$ for an arbitrary strictly
monotonic and continuous function $f(x)$.
Rényi entropy follows for $f(x)=\ln_{\alpha}(e^{x})$ with $I(x)=\ln(1/x)$,
which gives the entropy of order $\alpha$ given in (3).
Actually, Rényi entropy can be derived from SK axioms by posing in (A4)

$\displaystyle
S(B/A)=f^{-1}\left({\sum_{i=1}^{W}p_{i}^{\alpha}\,f\big{(}S(B/A_{i})\big{)}\over\sum_{i=1}^{W}p_{i}^{\alpha}}\right)\
.$

as shown in [20], and (6) is a direct consequence for SI systems.

###  2.4 Sharma-Mittal entropy

By following the same road, we can introduce more general expressions for a
different choice of $f(x)$ and/or $I(x)$, and by replacing the linear
composability condition (6) with the nonlinear one given in (9).
A possibility follows by posing
$f(x)=\ln_{\alpha}\big{(}\exp_{\beta}(x)\big{)}$ and $I(x)=\ln_{\beta}(1/x)$,
where

$\displaystyle\exp_{\beta}(x)=[1+(1-\beta)\,x]^{1\over 1-\beta}\ ,$

is the inverse function of $\ln_{\beta}(x)$. In this way we obtain the two-
parameters entropy

$\displaystyle S_{\alpha,\beta}[{\mbox{\boldmath${p}$}}]={1\over
1-\beta}\,\left[\left(\sum_{i=1}^{W}p_{i}^{\alpha}\right)^{1-\beta\over
1-\alpha}-1\right]\ ,$ (14)

originally introduced by Sharma-Mittal [21], also named entropy of order
$(\alpha,\,\beta)$.
Quite interesting, (14) follows from the SK axioms by replacing (A4) with the
relation

$\displaystyle S(A\cap
B)=S(A)+\left(\sum_{i=1}^{W}p_{i}^{\alpha}\right)^{1-\beta\over
1-\alpha}\,S(B/A)\ ,$

where the conditional entropy $S(B/A)$ is now defined in

$\displaystyle
S(B/A)=f^{-1}\left({\sum_{i=1}^{W}p_{i}^{\alpha}\,f\big{(}S(B/A_{i})\big{)}\over\sum_{i=1}^{W}p_{i}^{\alpha}}\right)\
,$

so that (9) is recovered in the case of SI systems.
Again, several entropic forms introduced in literature in different contexts
belong to the Sharma-Mittal family as shown in Table 2.

Table 2: Entropic forms of order $(\alpha,\,\beta)$ Parameters | Entropy | Ref.
---|---|---
$\alpha=1,\qquad\quad\beta=1$ | $-\sum_{i}p_{i}\,\ln(p_{i})$ | [5]
$\qquad\qquad\ \ \beta=1$ | ${1\over 1-\alpha}\ln\sum_{i}p_{i}^{\alpha}$ | [9]
$\alpha=\beta$ | $\sum_{i}{p_{i}^{\beta}-1\over 1-\beta}$ | [10, 11, 12]
$\alpha=1$ | ${1\over 1-\beta}\left[e^{(\beta-1)\,\sum_{i}p_{i}\,\ln(p_{i})}-1\right]\hskip 17.07164pt$ | [21]
$\alpha=r-m+1,\ \ \beta=1$ | ${1\over m-r}\ln\left(\sum_{i}p_{i}^{r-m+1}\right)$ | [22]
$\alpha=1/t,\quad\quad\ \beta=2-t$ | ${1\over t-1}\left[\left(\sum_{i}p_{i}^{1/t}\right)^{t}-1\right]$ | [23]
$\alpha=1/\beta$ | ${1\over 1-\beta}\left[\left(\sum_{i}p_{i}^{1/\beta}\right)^{-\beta}-1\right]$ | [24]
$\alpha=2-\beta$ | ${1\over 1-\alpha}\left(1-{1\over\sum_{i}p_{i}^{\alpha}}\right)$ | [25]

###  2.5 Entropic forms as averages of information

By using the so-called escort average instead of other average prescriptions
we can obtain new families of entropic forms defined as certain average of a
given information function. They can formally be written in

$\displaystyle
S[{\mbox{\boldmath${p}$}}]=\mathbbm{E}^{\varphi}\left(I[{\mbox{\boldmath${p}$}}]\right)\
,$ (15)

or also

$\displaystyle S[{\mbox{\boldmath${p}$}}]=\mathbbm{E}^{\varphi}_{\rm
KN}\left(I[{\mbox{\boldmath${p}$}}]\right)\ ,$ (16)

where

$\displaystyle\mathbbm{E}^{\varphi}\left({\mbox{\boldmath${x}$}}\right)={\sum_{i=1}^{W}x_{i}\,\varphi(p_{i})\over\sum_{i=1}^{W}\varphi(p_{i})}\
,$

and

$\displaystyle\mathbbm{E}_{\rm
KN}^{\varphi}({\mbox{\boldmath${x}$}})=f^{-1}\left(\mathbbm{E}^{\varphi}\big{(}f({\mbox{\boldmath${x}$}})\big{)}\right)\
,$

for a given function $\varphi(x)$.
Clearly definitions (15) is a special case of (16) obtained for $f(x)=x$ and,
more in general, (12) and (13) follow from (15) and (16) for $\varphi(x)=x$,
respectively.
Posed $\varphi(x)=x^{q}$, a choice often employed in certain versions of the
nonextensive statistical mechanics, and using
$I(x)=x\,\ln_{\alpha,\beta}(1/x)$ in (15) or $I(x)=\ln_{\beta}(1/x)$ and
$f(x)=\ln_{\beta}\left(\exp_{\alpha}(x)\right)$ in (16), we obtain several
known entropies reported in Table 3, some of them belong also to the family of
order $(\alpha,\,\beta)$.

Table 3: Entropic forms as averages of information Parameters | Entropy | Ref.
---|---|---
$\alpha=2-1/\beta,\quad q=1/\beta$ | ${1\over 1-\beta}\left[\left(\sum_{i}p_{i}^{1/\beta}\right)^{-\beta}-1\right]$ | [24]
$\alpha=2-q,\qquad\beta=2-q$ | ${1\over 1-q}\left(1-{1\over\sum_{i}p_{i}^{q}}\right)$ | [25]
$\alpha=1,\qquad\quad\beta=1$ | $-{\sum_{i}p^{q}\,\ln(p_{i})\over\sum_{i}p_{i}^{q}}$ | [26]
$\alpha=r-q+1,\quad\beta=1\hskip 17.07164pt$ | ${1\over q-r}\,\ln\left({\sum_{i}p^{r}\over\sum_{i}p_{i}^{q}}\right)$ | [26]
$\alpha=1,\qquad\quad\beta=q$ | ${1\over 1-q}\left(e^{(q-1)\,{\sum_{i}p_{i}^{q}\,\ln(p_{i})\over\sum_{i}p_{i}^{q}}}-1\right)$ | [27]
$\beta=1,\qquad\quad q=s_{i}$ | ${1\over 1-\alpha}\,\ln\left({\sum_{i}p^{\alpha+s_{i}-1}\over\sum_{i}p_{i}^{s_{i}}}\right)$ | [28]

In addition, if $I(x)=h(-\ln\big{(}x)\big{)}$ and
$f\big{(}h(x)\big{)}=\exp_{\alpha}(x)$, for an increasing, continuous function
such that $h(0)=0$, (16) reduces to the class of strongly pseudo-additive
entropies $h\big{(}S_{\alpha}[{p}]\big{)}$ introduced from generalized
Shannon-Khinchin axioms in [29] and considered latter in [30] under the name
of $Z$-entropies.
Furthermore, if entropy and information content in (16) decompose according to
the same pseudoadditivity rule

$\displaystyle S(A\cap B)=h(h^{-1}(S(A))+h^{-1}(S(B))\ ,$ (17) $\displaystyle
I(x\,y)=h(h^{-1}(x)+h^{-1}(y))\ ,$

then we obtain the class of weakly pseudo-additive entropies introduced in
[31] which contains a number of previously listed entropic forms (see Table I
in [31]).
It is worthy to cite a more general approach proposed in[32], where it is
suggested to replace axiom (A4) with the only composability rule $S(A\cap
B)=\Phi(S(A),\,S(B))$ for a given function $\Phi(x,\,y)$ that is symmetric
$\Phi(x,\,y)=\Phi(y,\,x)$, associative
$\Phi(x,\,\Phi(y,\,z))=\Phi(\Phi(x,\,y),\,z)$ and admits a null element
$\Phi(x,\,0)=\Phi(0,\,x)=x$. In this way, for opportunely choosen functions
$\Phi(x,\,y)$ a wide class of generalized entropic forms can be obtained.
Clearly, relation (17) implies the existence of an underlying algebraic
structure that, under certain assumptions, can be derived starting from the
expression of the entropy itself [33].

###  2.6 Hanel-Thurner entropy

In [34], by relaxing completely axiom (A4) and following scaling
argumentations for the asymptotic behavior of the entropy summarized in
$S(\lambda\,W)/S(W)\sim\lambda^{c}$ and
$W^{a(c-1)}\,S(W^{1+a})/S(W)\sim(1+a)^{d}$, for $W\to\infty$, a new family of
two-parameters entropies has been proposed

$\displaystyle
S_{c,d}[{\mbox{\boldmath${p}$}}]={e\,\sum_{i=1}^{W}\Gamma(1+d,\,1-c\,\ln(p_{i}))-c\over
1-c+c\,d}\ .$ (18)

The pair of numbers $(c,\,d)$, that characterizes the asymptotic scaling
behavior of entropy, univocally defines an equivalent class of entropy in the
thermodynamic limit.
Once mores, several generalized entropies, obtained independently in other
contexts of statistical physics, have asymptotical scaling that can be found
inside to the $S_{c,d}$ family for a particular value of the scaling
parameters, as reported in Table 4.

Table 4: Entropic forms of class $(c,\,d)$ Parameters | Entropy | Ref.
---|---|---
$c=1,\quad\quad d=1$ | $-\sum_{i}p_{i}\,\ln(p_{i})$ | [5]
$c=\beta,\quad\quad d=0$ | $-\sum_{i}{p_{i}^{\beta}-1\over 1-\beta}$ | [10, 11, 12]
$c=1-\kappa,\quad d=0$ | $-\sum_{i}{p_{i}^{1+\kappa}-p_{i}^{1-\kappa}\over 2\,\kappa}$ | [17]
$c=\alpha,\quad\quad d=1$ | $-\sum_{i}p_{i}^{\alpha}\,\ln(p_{i})$ | [18]
$c=1,\quad\quad d=\beta$ | $\sum_{i}p_{i}\,\left(-\ln(p_{i})\right)^{\beta}$ | [35]
$c=\alpha,\quad\quad d=\beta$ | $\sum_{i}p_{i}^{\alpha}\,\left(-\ln(p_{i})\right)^{\beta}$ | [36]
$c=1,\quad\quad d=1$ | $\pm\sum_{i}\left(1-p_{i}^{\pm p_{i}}\right)$ | [37]
$c=1,\quad\quad d=0$ | $\sum_{i}p_{i}\,\left(1-e^{1-1/p_{i}}\right)$ | [38]
$c=1,\quad\quad d=0$ | $\sum_{i}\left(1-e^{-b\,p_{i}}\right)+e^{-b}-1$ | [39]
$c=r,\quad\quad d=0$ | ${1\over r-1}\left[1-\sum_{i}e^{r\,W\,\left(p_{i}^{p_{i}}-1\right)}\right]$ | [40]
$c=1,\quad\quad d=1/\eta$ | $\sum_{i}\Gamma\left(1+{1\over\eta},\,-\ln(p_{i})\right)-\Gamma\left(1+{1\over\eta}\right)\hskip 14.22636pt$ | [41]

Entropic forms of class $(c,\,d)$, as well as those of degree
$(\alpha,\,\beta)$, take into account a sub-exponential asymptotic behaviour
of the system where the number of possible configurations $W$ grows according
to a certain power law of the system sized $N$. However, complex systems may
also be characterized by a super-exponential asymptotic trend. In this case, a
statistical description based on entropic forms (11) or (18) fails to make a
correct prediction. To overcame this lack, in [42, 43] a generalization of
(18) has been advanced

$\displaystyle
S[{\mbox{\boldmath${p}$}}]=\sum_{i=1}^{W}\int\limits_{0}\limits^{p_{i}}\ln_{c,d}(\mu_{l}(x))\,dx\
,$

where

$\displaystyle\ln_{c,d}(x)=r\,\left[x^{c}\left(1+{1-c\,r\over
d\,r}\,\ln(x)\right)^{d}-1\right]\ ,$

and $\mu_{l}(x)$ is the neasted logarithm defined in
$\mu_{l}(x)=[1+\ln]^{(l)}(x)$. The $l=0$ case reproduces the entropic forms of
class $(c,\,d)$.

##  3 Final comments

On the basis of the previous analysis, it emerges that most of the entropic
forms introduced in the literature can be grouped into two large groups.
The first group is formed by the trace-form entropies. This group includes the
entropies of degree $(\alpha,\,\beta)$ and the entropies of class $(c,\,d)$,
obtained starting from certain considerations on the decomposition rule or on
the asymptotic behavior of entropy in the thermodynamics limit. Clearly, the
$(\alpha,\,\beta)$ or $(c,\,d)$ families are not exhaustive in this group and
many other trace-form entropies, not yet characterized at all, can be found
inside the literature relevant to physics or statistics. For instance, in
[44], in the framework of the basic algebra it has been proposed the following
entropy $S_{q}[{\mbox{\boldmath${p}$}}]=-\sum_{i=1}^{W}p_{i}\,{\rm
Ln}_{q}(p_{i})$, where Ln${}_{q}(x)$ is the inverse function of the well-known
basic exponential, which does not found collocation in the two main families
discussed in this review.
For sake of completeness, trace-form entropies including several examples not
listed in the previous tables are reported in Table 5.

Table 5: Trace-form entropies Entropy | Ref.
---|---
$-\sum_{i}p_{i}\,\ln(p_{i})$ | [5]
$-\sum_{i}{p_{i}^{\alpha}-p_{i}^{\beta}\over\alpha-\beta}$ | [15, 16]
${1\over 1-c+c\,d}\left(\sum_{i}e\,\Gamma(1+d,\,1-c\,\ln(p_{i}))-c\right)$ | [34]
${4\over q}\sum_{i}p_{i}\,\arctan(p_{i}^{q/2})-{\pi\over q}$ | [38]
$\sum_{i}\int_{0}^{p_{i}}r\,\left[\mu_{l}(x)^{c}\left(1+{1-c\,r\over d\,r}\,\ln(\mu_{l}(x))\right)^{d}-1\right]\,dx$ | [42, 43]
$-\sum_{i}p_{i}\,{\rm Ln}_{q}(p_{i})$ | [44]
$-{1\over\sin(s)}\sum_{i}p_{i}^{r}\,\sin(s\,\ln(p_{i}))$ | [45]
$-\sum_{i}p_{i}\,\ln\left({\sin(s\,p_{i})\over 2\,\sin(s/2)}\right)$ | [46]
$-\sum_{i}{\sin(s\,p_{i})\over 2\,\sin(s/2)}\,\ln\left({\sin(s\,p_{i})\over 2\,\sin(s/2)}\right)$ | [46]
$\sum_{i}{\sin(s\,p_{i})\over 2\,\sin(s/2)}$ | [46]
$-{1\over\lambda}\,\sum_{i}(1+\lambda\,p_{i})\,\ln(1+\lambda\,p_{i})+\left(1+{1\over\lambda}\right)\,\ln(1+\lambda)$ | [47]
$-\sum_{i}\left(p_{i}\,\ln(p_{i})+({1\over\lambda}+p_{i})\,\ln(1+\lambda\,p_{i})\right)+\left(1+{1\over\lambda}\right)\,\ln(1+\lambda)\hskip 5.69054pt$ | [48]
$\sum_{i}\left(p_{i}+\ln\left(2-p_{i}^{p_{i}}\right)\right)$ | [49]
$-\sum_{i}\ln\big{(}\Gamma(1+p_{i})\big{)}$ | [50]
${1\over 1-q^{\prime}}\sum_{i}p_{i}\left[e^{{1-q^{\prime}\over 1-q}(p_{i}^{q-1}-1)}-1\right]$ | [51]
$\sum_{i}p_{i}\left(-\ln_{\beta}p_{i}\right)^{\delta}$ | [52]
$\sum_{i}{2\,p_{i}\,(p_{i}^{r}-1)\over-a\,(p_{i}^{r}-1)\pm\sqrt{a^{2}+4\,b}\,(p_{i}^{r}+1)}$ | [53]

The second group is given by the kernels-form entropies, which is obtained
starting from certain considerations on the average prescription of the
information content. This group includes the entropies of order
$(\alpha,\,\beta)$ as well as the strongly- and weakly-pseudo additive
entropies.
In general, kernel-entropies are expressed by a given analytical composition
of different kernel-blocks, each one formed by a certain function of the
information content. The easiest case is given by the $(h,\,\Phi)$-entropies
[54] defined in

$\displaystyle
S[{\mbox{\boldmath${p}$}}]=h\left(\sum_{i=1}^{W}\Phi(p_{i})\right)\ ,$ (19)

with a single kernel-block given by the quantity $\sum_{i}\Phi(p_{i})$.
Clearly, (19) is completely equivalent, in form, to (13) which follows for
$h(x)=f^{-1}(x)$ and $\Phi(x)\equiv x\,f\big{(}I(x)\big{)}$. However, while
for certain “exotic” entropies the pair of functions $(h,\,\Phi)$ is readily
determinable, not so immediate is derive the corresponding pair of functions
$(f,\,I)$.
More general is the class of entropies proposed in [55]

$\displaystyle
S[{\mbox{\boldmath${p}$}}]=h\left({\sum_{i=1}^{W}\Phi_{1}(p_{i})\over\sum_{i=1}^{W}\Phi_{2}(p_{i})}\right)\
,$

which is a generalized kernel-entropy with two kernel-blocks. It includes
entropic forms (15) and (16), as particular cases.
Examples of kernel-like entropies are showed in Table 6.

Table 6: Kernel-like entropic forms Entropy | Ref.
---|---
${1\over 1-s}\,\left[\left(\sum_{i}p_{i}^{r}\right)^{1-s\over 1-r}-1\right]$ | [21]
${1\over s}\arctan\left({\sum_{i}p_{i}^{r}\,\sin\big{(}s\,\ln(p_{i})\big{)}\over\sum_{i}p_{i}^{r}\,\cos\big{(}s\,\ln(p_{i})\big{)}}\right)\hskip 85.35826pt$ | [26]
$\exp\left(\sum_{i}\ln\left(2-p_{i}^{p_{i}}\right)\right)$ | [49]
${1\over 1-s}\left\\{\left[1+{1-r\over 1-s}\,\ln\left(\sum_{i}p_{i}^{s}\right)\right]^{1-s\over 1-r}-1\right\\}\hskip 85.35826pt$ | [56]
$\exp\left(L\left({\ln\sum_{i}p_{i}^{r}\over\gamma\,(1-r)}\right)-1\right)$ | [57]
${1\over r-s}\,\log\left({\big{(}\sum_{i}p_{i}^{s}\big{)}^{r}\over\big{(}\sum_{i}p_{i}^{r}\big{)}^{s}}\right)$ | [58]
${1\over r-s}\,\left[{\big{(}\sum_{i}p_{i}^{s}\big{)}^{r}\over\big{(}\sum_{i}p_{i}^{r}\big{)}^{s}}-1\right]$ | [58]

In conclusion, it is worthy to observe that, in general, entropy must
necessarily to respect further additional criteria that may pose several
restrictions to the form of the functional $S[{\bf p}]$.

For instance, the Lesche inequality [59], a necessary requirement that an
entropic functional must satisfy to make physical sense. Shortly, it requires
that a small perturbation of the set of probabilities to a new set
$[{\mbox{\boldmath${p}$}}]\to[{\mbox{\boldmath${p}$}^{\prime}}]$ should have
only a small effect on the value of entropy reported to the thermodynamic
state of the uniform distribution, i.e.
$\sum_{i}|p_{i}-p_{j}^{\prime}|\leq\delta\Rightarrow{|S[{\mbox{\boldmath${p}$}}]-S[{\mbox{\boldmath${p}$}}^{\prime}]|\over
S^{\rm max}}\leq\epsilon$.
This should, in particular, be true in the thermodynamical limit $W\to\infty$.
It is known that trace-form entropies like the Sharma-Taneja-Mittal family or
the Hanel-Turner family pass the Lesche inequality [60, 34] while the question
turns out to be more problematic for the Sharma-Mittal family since some of
its members, like Rényi and others, seems to be not Lesche stable [61],
although this problem has still to be fully clarified [62, 63].

A further relationships can be related to the Shore-Johnson axioms [64] that,
differently from the SK axioms, routed to the information theory, concern the
statistical estimation theory and seem to pose stringent limitations to the
form of entropy may have.
The question is strictly related to the maximal entropy principle introduced
in [65], which is the main bridge between information theory, statistical
physics and statistical inference. It is a powerful method widely employed in
statistical sciences to derive the probability distribution of a system
described by a given entropy, subjected by certain constraints given by the
prior information on the system itself.
With the introduction of new entropic forms, it has been natural to extend the
maximal entropy principle in these cases, to obtain distributions different
from Boltzmann-Gibbs ones. However, several criticisms on the consistency of
the maximal entropy principle with generalized entropic forms have been
recently advanced [66] since in the original paper, Shore and Johnson conclude
that their axioms yield only one admissible measure, namely Shannon entropy.
It has been shown in [67] that the Shore-Johnson axiomatization of the
inference rule actually does account for a substantially wider class of
entropic functionals than just the Shannon entropy. In particular, at least
the Uffink class of entropies [68]

$\displaystyle
S[{\mbox{\boldmath${p}$}}]=f^{-1}\left(\left(\sum_{i=1}^{W}p_{i}^{\alpha}\right)^{1/(1-\alpha)}\right)\
,$

which corresponds to the strong pseudoadditive entropy presented above, is
compatible with the conditions stated in the Shore-Johnson axioms. In [69] the
Uffink class of entropic functional has been characterized by means of a
suitable generalization of the SK axioms, re-establishing, in this way, in
part, the “broken” entropic parallelism between information theory and
statistical inference.

Acknowledgments

V.I. was supported by the Serbian Ministry of Education, Science and
Technological Development through the Mathematical Institute of the Serbian
Academy of Sciences and Arts.

J.K. acknowledges support by the Czech Science Foundation (GAČR), Grant No.
19-16066S. and by the Austrian Science Fund (FWF) under Project no. I3073.

References

## References

  * [1] Clausius R., The Mechanical Theory of Heat: With Its Application to the Steam Engine and to the Physical Properties of Bodies (J. Van Voorst, London, UK) 1867.
  * [2] Boltzmann L., Sitz. Ber. Akad. Wiss. Wien (II), 66 (1872) 275; 75 (1877) 67.
  * [3] Gibbs J.W., Elementary Principles in Statistical Mechanics (Charles Scribner’s Sons, New York, US) 1902.
  * [4] Planck, M., Ann. Phy., 309 (1901) 553.
  * [5] Shannon C.E., Bell Syst. Techn. J., 3 (1948) 379.
  * [6] Khinchin A.I., Mathematical Foundations of Information Theory (Dover Pub., New York, US) 1957.
  * [7] Kolmogorov A.N., Atti R. Accad. Naz. Lincei, 12 (1930) 388.
  * [8] Nagumo M., Jpn. J. Math. 7 (1930) 71.
  * [9] Rényi A., Proc. Fourth Berk. Symp. Math. Stat. Prob., 1 (1961) 547.
  * [10] Havrda J. and Charvát F., Kybernetika, 3 (1967) 30.
  * [11] Daróczy Z., Inf. Contr., 16 (1970) 36.
  * [12] Tsallis C., J. Stat. Phys., 52 (1988) 479.
  * [13] Suyari H., IEEE Trans. Inf. Theor., 50 (2004) 1783.
  * [14] Wada T. and Suyari H., Phys. Lett. A, 368 (2007) 199.
  * [15] Sharma B.D. and Taneja I.J., Metrica, 22 (1975) 205.
  * [16] Mittal P.D., Metrika 22 (1975) 35.
  * [17] Kaniadakis G., Physica A, 296 (2001) 405.
  * [18] Shafee F., IMA J. Appl. Math., 72 (2007) 785.
  * [19] Abe S., Phys. Lett. A, 224 (1997) 326.
  * [20] Jizba P. and Arimitsu T., Ann. Phys., 312 (2004) 17.
  * [21] Sharma B.D. and Mittal D.P., J. Math. Sci., 10 (1975) 122.
  * [22] Varma R.S., J. Math. Sci., 1 (1966) 34.
  * [23] Arimoto S., Inf. Cont., 19 (1971) 181.
  * [24] Tsallis C., Mendes R.S. and Plastino A.R., Physica A, 261 (1998) 534.
  * [25] Landsberg P.T. and Vedral V., Phys. Lett. A 247 (1998) 211.
  * [26] Aczél J. and Daróczy Z., Pub. Math., 10 (1963) 171.
  * [27] Jizba P and Korbel J., Physica A, 444 (2016) 808.
  * [28] Rathie P.N., J. Appl. Probl., 7 (1970) 124.
  * [29] Ilić V.M. and Stanković M.S., Physica A, 411 (2014) 138.
  * [30] Tempesta P., Proc. R. Soc. A: Math. Phys. Eng. Sci., 472 (2016) 20160143.
  * [31] Ilić V.M. and Stanković M.S., Physica A, 415 (2014) 229.
  * [32] Tempesta P. and Jensen H.J., Sci. Rep., 10 (2020), 5951.
  * [33] Scarfone A.M., Entropy, 15 (2013) 624.
  * [34] Hanel R. and Thurner S., Eur. Phys. Lett., 93 (2011) 20006.
  * [35] Ubriaco M.R., Phys. Lett. A, 373 (2009) 2516.
  * [36] Radhakrishnan C., Chinnarasu R. and Jambulingam S., Int. J. Stat. Mech., 2014 (2014) 460364.
  * [37] Obregón O., Entropy, 12 (2010) 2067.
  * [38] Tsekouras G.A. And Tsallis C., Phys. Rev. E, 71 (2005) 046144.
  * [39] Curado E.M.F. and Nobre F.D., Physica A, 335 (2004) 94.
  * [40] Bizet N.C., Fuentes J. and Obregón O., Eur. Phys. Lett., 128 (2019) 60004.
  * [41] Anteneodo C. and Plastino A.R., J. Phys. A: Math. Gen., 32 (1999) 1089.
  * [42] Korbel J., Hanel R. and Thurner S., New J. Phys. 20 (2018) 093007.
  * [43] Korbel J., Hanel R. and Thurner S., Eur. Phys. J. ST, 229, (2020) 787.
  * [44] Lavagno A., Scarfone A.M. and Swamy P.N., J. Phys. A: Math. Theo., 40 (2007) 8635.
  * [45] Sharma B.D. and Taneja I.J., Elec. Inform. Kybern., 13 (1977) 419.
  * [46] Sant’anna A.P. and Taneja I.J., Inf. Sci, 35 (1985) 145.
  * [47] Ferrari C., Statistica, 40 (1980) 155.
  * [48] Kaniadakis G., Lavagno A. and Quarati P., Nucl. Phys. B, 466 (1996) 527.
  * [49] Amigó J.M., Balogh S.G. and Hernández S., Entropy, 20 (2018) 813.
  * [50] Kapur J.N., Boll. U.M.I., 7, 2-B (1988) 253.
  * [51] Schwämmle V. and Tsallis C., J. Math. Phys., 48 (2007) 113301.
  * [52] Tsallis C. and Cirto L.J.L., Eur. Phys. J. C, 73 (2013) 2487.
  * [53] Curado E.M.F., Tempesta P. and Tsallis C., Ann. Phys., 366 (2016) 22.
  * [54] Salicrú M, Menéndez M.L., Morales D. and Pardo L., Comm. Stat., 22 (1993) 2015.
  * [55] Esteban M.D. and Morales D., Kybernetika, 31 (1995) 337.
  * [56] Masi M., Phys. Lett. A, 338 (2005) 217.
  * [57] Jensen H.J., Pazuki R.H., Pruessner G, and Tempesta P., J. Phys. A: Math. Gen., 51 (2018) 375002.
  * [58] Bercher J.-F., Phys. Lett. A, 375 (2011) 2969.
  * [59] Lesche B., J. Stat. Phys., 27 (1982) 419.
  * [60] Kaniadakis G., Lissia M. and Scarfone A.M., Phys. Rev. E, 71 (2005) 046128.
  * [61] Tsallis C. and Brigatti E., Cont. Mech. Thermodyn., 16 (2004) 223.
  * [62] Jizba P. and Arimitsu T., Phys. Rev. E, 69 (2004) 026128.
  * [63] Bashkirov A.G., Phys. Rev. E, 72 (2005) 028101.
  * [64] Shore J.E. and Johnson R.W., IEEE Trans. Inf. Theor., 26 (1980) 26.
  * [65] Jaynes F.T., Phys. Rev., 108 (1957) 171.
  * [66] Pressé S., Ghosh K., Lee J. and Dill K.A., Phys. Rev. Lett., 111 (2013) 180604.
  * [67] Jizba P. and Korbel J., Phys. Rev. Lett., 122 (2019) 120601.
  * [68] Uffink J., Stud. Hist. Phil. Mod. Phys., 26 (1995) 223.
  * [69] Jizba P. and Korbel J., Phys. Rev. E, 101 (2020) 042126.


# Stabilizer rank and higher-order Fourier analysis

Farrokh Labib  CWI, QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands.
Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch
Research Council (NWO<EMAIL_ADDRESS>
###### Abstract

We establish a link between stabilizer states, stabilizer rank and higher-
order Fourier analysis—a still-developing area of mathematics that grew out of
Gowers’s celebrated Fourier-analytic proof of Szemerédi’s theorem [10]. We
observe that $n$-qudit stabilizer states are so-called _nonclassical quadratic
phase functions_ (defined on affine subspaces of $\mathbb{F}_{p}^{n}$ where
$p$ is the dimension of the qudit) which are fundamental objects in higher-
order Fourier analysis. This allows us to import tools from this theory to
analyze the stabilizer rank of quantum states. Quite recently, in [20] it was
shown that the $n$-qubit magic state has stabilizer rank $\Omega(n)$. Here we
show that the qudit analogue of the $n$-qubit magic state has stabilizer rank
$\Omega(n)$, generalizing their result to qudits of any prime dimension. Our
proof techniques use explicitly tools from higher-order Fourier analysis. We
believe this example motivates the further exploration of applications of
higher-order Fourier analysis in quantum information theory.

##  1 Introduction

The Gottesman-Knill Theorem [9, 18] states that any quantum circuit consisting
of Clifford gates can be efficiently classically simulated. The Clifford group
on $n$ qubits is generated by the Hadamard gate $H$, the $\pi/4$ phase gate
$S$ and the entangling $\mathrm{CNOT}$ gate. In particular, this means that
circuits consisting only of Clifford gates cannot provide computational
advantage over classical computers. We can promote such circuits to universal
quantum computers by having access to a non-Clifford gate or (equivalently) a
“magic state” [3]. It is widely believed that universal quantum computers
cannot be efficiently simulated by classical computers: state-of-the-art
simulators using modern day supercomputers are only able to simulate a few
dozens of qubits [6, 12, 19, 22]. So it has to be this magic state that fuels
the computational hardness of simulation by classical computers. It is
therefore important to understand how much this resource costs in terms of
free (efficiently simulatable) resources. These costs are quantified by
“measures of magic” [16] an example of which is _stabilizer rank_ , first
introduced in [4]. Here, the free resources are states obtained from the
canonical all-zero state by applying only Clifford operations, which are the
well-known stabilizer states. To increase our understanding of non-
stabilizerness, or the amount of “magic” a quantum state has, a valid approach
might be to find a different characterization of these objects. This might
introduce new techniques in analyzing measures of magic. It is well known that
stabilizer states are quadratic forms defined on affine subspaces [7, 14, 11].
Here we observe that these objects are so-called _nonclassical quadratic phase
functions_ defined on affine subspaces which are well-studied objects in
higher-order Fourier analysis.

Higher-order Fourier analysis, a still nascent area of mathematics, grew out
of a Fourier-analytic proof of Szemerédi’s Theorem [23] by Gowers [10].
Whereas in Fourier analysis one studies how functions correlate with
characters, in higher-order Fourier analysis one studies correlations with
functions that resemble polynomials (where characters correspond to linear
functions). These polynomial-like functions are known as _polynomial phase
functions_.

It turns out that Boolean functions giving the (unnormalised) amplitudes of
graph states are examples of quadratic phase functions. In general, quadratic
phase functions can be defined using “multiplicative derivatives”: for
$h\in\mathbb{F}_{2}^{n}$, the multiplicative derivative of
$f\colon\mathbb{F}_{2}^{n}\to\mathbb{C}$ in direction $h$ is

$\displaystyle{\vphantom{\Delta}\mathchoice{\ooalign{$\displaystyle\mkern-1.0mu\cdot$\cr$\displaystyle\Delta$\cr}}{\ooalign{$\textstyle\mkern-1.0mu\cdot$\cr$\textstyle\Delta$\cr}}{\ooalign{$\scriptstyle\mkern-1.0mu\cdot$\cr$\scriptstyle\Delta$\cr}}{\ooalign{$\scriptscriptstyle\mkern-1.0mu\cdot$\cr$\scriptscriptstyle\Delta$\cr}}}_{h}f(x):=f(x+h)\overline{f(x)}.$

_Nonclassical_ polynomial phase functions of degree $d$ are those functions
that are constant after taking $d+1$ multiplicative derivatives. It is not
difficult to check that graph states, whose amplitude function always has the
form $f(x)=(-1)^{q(x)}$ where $q$ is a quadratic polynomial, satisfies this
property with $d=2$. These are referred to as the _classical_ quadratic phase
functions. However, the nonclassical quadratic phase functions are not
exhausted by these examples. It turns out that stabilizer states correspond to
functions in this broader class. This establishes a surprising link between
higher-order Fourier analysis and quantum information theory. It was shown in
[7] (see also [2]) that stabilizer states are _quadratic forms_ taking values
in $\mathbb{Z}_{8}$ defined on affine subspaces. We will see that they are
nonclassical quadratic phase function on affine subspaces.

Let $p$ be an odd prime and consider qudits of dimension $p$. Then, the
amplitudes of $n$-qudit stabilizer states are also quadratic phase functions
defined on affine subspaces of $\mathbb{F}_{p}^{n}$ [14], see also [11]. It is
interesting to note that for primes $p>2$ the $n$-qudit stabilizer states are
given by classical quadratic polynomials while there are no nonclassical
polynomials of degree two, contrary to the case $p=2$.

#### Stabilizer rank.

_Stabilizer rank_ is a measure of magic which was recently extensively
analysed by Bravyi et al. [5]. The stabilizer rank of a quantum state
$|\psi\rangle$, denoted $\chi(|\psi\rangle)$, is the minimal number $r$ such
that $|\psi\rangle$ can be written as a linear combination of $r$ stabilizer
states. As is well known, any circuit $\mathcal{C}$ consisting of Clifford
gates and $n$ copies of the $T$-gate, given by $|0\rangle\\!\langle
0|+e^{i\pi/4}|1\rangle\\!\langle 1|$, can be implemented using Clifford
operations on the $n$-qubit magic state $|T\rangle^{\otimes n}$, where
$|T\rangle=\frac{|0\rangle+e^{i\pi/4}|1\rangle}{\sqrt{2}}$. Then, the
stabilizer rank of $|T\rangle^{\otimes n}$ upper bounds the simulation cost of
the circuit $\mathcal{C}$. Bravyi, Smith and Smolin [4] showed that the
stabilizer rank of the $n$-qubit magic state is $\Omega(\sqrt{n})$. Very
recently Peleg, Shpilka and Volk [20] showed a lower bound of $\Omega(n)$ for
the stabilizer rank of the $n$-qubit magic state, which is a quadratic
improvement. Here we give the same lower bound but generalize to qudits of any
prime dimension.

Adding any non-Clifford gate to the Clifford gate set could in principle
promote it to universal quantum computation. However, we use the
generalization of the $T$ gate for qudits from [15]. Let us call this gate $U$
and define
$|+\rangle:=\frac{|0\rangle+|1\rangle+\dots+|p-1\rangle}{\sqrt{p}}$. Then, the
single qudit magic state over $\mathbb{F}_{p}$ is defined to be

$\displaystyle|\psi_{U}\rangle=U|+\rangle.$

Our main result is the following.

######  Theorem 1.1.

Let $p$ be any prime and let $|\psi_{U}\rangle^{\otimes n}$ be the $n$-qudit
magic state over $\mathbb{F}_{p}$. We have that
$\chi(|\psi_{U}\rangle^{\otimes n})\geq\Omega(n)$.

This result generalizes [20], but our techniques are completely different and
use explicitly tools from higher-order Fourier analysis. Roughly speaking, we
show that the function giving the amplitudes of the $n$-qudit magic state is a
cubic nonclassical polynomial phase function for which the polynomial “in the
phase” has high rank (see Definition 3.9). We then prove that the lower bound
for this rank is also a lower bound for the stabilizer rank. In this step we
use a lemma from [20] (Claim 3.3 in that paper) to get a handle on the affine
subspaces that appear from the stabilizer states. Apart from this lemma, the
techniques are different.

We think that the techniques used here might pave the way to super-linear
lower bounds for decompositions in terms of stabilizer states defined on the
full space $\mathbb{F}_{p}^{n}$.

#### Higher-order Fourier analysis and quantum information theory.

We believe that the application we found motivate the further study of tools
in higher-order Fourier analysis in quantum information theory. A work that
connected to this area is [1], where the “Gowers Inverse Theorem” is utilised
to analyze certain Bell inequalities. This current work is yet another
example.

Higher-order Fourier analysis has already found many applications in classical
theoretical computer science, such as in property testing, coding theory and
complexity theory [13]. In analogy with analysis of Boolean functions, we hope
that higher-order Fourier analysis proves equally useful in quantum
information theory.

#### Acknowledgements

I would like to thank Jop Briët for his guidance and many fruitful discussions
in this project. Also thanks to Michael Walter for the fruitful discussions on
stabilizer and magic states in odd prime dimension.

##  2 Preliminaries

For a finite non-empty set $S$, we write $\operatorname*{\mathbb{E}}_{s\in S}$
to mean $\frac{1}{|S|}\sum_{s\in S}$. Let $p$ be a prime. We denote by
$\mathbb{F}_{p}$ the field of $p$ elements, $\mathbb{T}=\mathbb{R}/\mathbb{Z}$
and $\mathbb{Z}_{n}$ is the ring of integers mod $n$.

Let $|\cdot|\colon\mathbb{F}_{p}\to\\{0,1,\dots,p-1\\}$ be the natural map.
This map has the property that for $a,b\in\mathbb{F}_{2}$,

$\displaystyle|a+b|=|a|+|b|-2|ab|.$ (1)

And for $a,b\in\mathbb{F}_{3}$,

$\displaystyle|a+b|=|a|+|b|+3(|a^{2}b|+|ab^{2}|)-6|ab|\mod 9.$ (2)

We also define $|\cdot|\colon\mathbb{F}_{p}^{n}\to\mathbb{Z}_{\geq
0}:x\mapsto|x_{1}|+\dots+|x_{n}|$, this is an abuse of notation, but it should
be clear from context what the domain of the map $|\cdot|$ is. Define $\iota$
to be the map given by

$\displaystyle\iota\colon\mathbb{F}_{p}\to\mathbb{T}\colon x\mapsto|x|/p\mod
1.$

The exponential map $e\colon\mathbb{T}\to\mathbb{C}$ is defined $e(t):=e^{2\pi
it}$.

For an affine subspace $H\subset\mathbb{F}_{p}^{n}$, we write $H=L(H)+v$ for
some vector $v\in\mathbb{F}_{p}^{n}$ and a linear subspace $L(H)$. The vector
$v$ is not unique, but $L(H)$ is uniquely determined by $H$, namely
$L(H)=\\{x-y\colon x,y\in H\\}$.

Let $G$ be an abelian group, $H\subset\mathbb{F}_{p}^{n}$ an affine subspace
and $P\colon H\to G$ a map. The additive derivative $\Delta_{h}$ is defined to
be $\Delta_{h}P(x):=P(x+h)-P(x)$, where $h\in L(H)$ and $x\in H$.

For a subset $A\subset\mathbb{F}_{p}^{n}$, write
$1_{A}\colon\mathbb{F}_{p}^{n}\to\\{0,1\\}$ for the indicator function of $A$,
i.e. $1_{A}(x)=1$ if $x\in A$ and 0 otherwise.

We also need some basic definitions for the Fourier transform. Let
$\omega_{p}:=e^{2\pi i/p}$. For functions
$f,g\colon\mathbb{F}_{p}^{n}\to\mathbb{C}$, their inner product is defined by

$\displaystyle\langle
f,g\rangle:=\operatorname*{\mathbb{E}}_{x\in\mathbb{F}_{p}^{n}}f(x)\overline{g(x)}=p^{-n}\sum_{x\in\mathbb{F}_{p}^{n}}f(x)\overline{g(x)}.$

Denote by $\hat{f}$ the Fourier transform of $f$, i.e.

$\displaystyle\hat{f}(\alpha)=\operatorname*{\mathbb{E}}_{x\in\mathbb{F}_{p}^{n}}f(x)\omega_{p}^{\langle\alpha,x\rangle},\quad\alpha\in\mathbb{F}_{p}^{n}.$

The inner product for the Fourier transforms is defined by

$\displaystyle\langle\hat{f},\hat{g}\rangle=\sum_{\alpha\in\mathbb{F}_{p}^{n}}\hat{f}(\alpha)\overline{\hat{g}(\alpha)}.$

Using this definition, Parseval’s theorem becomes

$\displaystyle\langle f,g\rangle=\langle\hat{f},\hat{g}\rangle.$

##  3 Techniques

In this section, we introduce all the definitions necessary for the proof of
our main result. Our main result generalizes the recent result of [20], but we
use completely different techniques that we explain here as well.

###  3.1 Stabilizer states

In [2], a succinct representation of an $n$-qubit stabilizer states is given
in terms of quadratic forms on affine subspaces of $\mathbb{F}_{2}^{n}$. For
this, they introduced the following definition.

######  Definition 3.1.

For an affine subspace $H\subset\mathbb{F}_{2}^{n}$, a map $Q\colon
H\to\frac{1}{8}\mathbb{Z}/\mathbb{Z}$ is called a quadratic form if
$\Delta_{h_{1}}\Delta_{h_{2}}Q(x)$ is independent of $x\in H$ for all
$h_{1},h_{2}\in L(H)$.

######  Theorem 3.2 ([2]).

For any $n$-qubit stabilizer state $|\phi\rangle$, there exists a unique
affine subspace $H\subset\mathbb{F}_{2}^{n}$ and a quadratic form $Q\colon
H\to\frac{1}{8}\mathbb{Z}/\mathbb{Z}$ such that

$\displaystyle|\phi\rangle=2^{-\dim{H}/2}\sum_{x\in H}e(Q(x))|x\rangle.$ (3)

In [2] quadratic forms are considered that are maps $Q\colon
H\to\frac{1}{8}\mathbb{Z}/\mathbb{Z}$. We will show that the only way that
such a map has the property $\Delta_{h_{1}}\Delta_{h_{2}}Q(x)$ being
independent of $x\in H$ for all $h_{1},h_{2}\in L(H)$, is if $Q$ actually take
values in
$\frac{1}{4}\mathbb{Z}/\mathbb{Z}\subset\frac{1}{8}\mathbb{Z}/\mathbb{Z}$. We
will also see that such functions are known as _nonclassical_ polynomials of
degree two in the literature of higher-order Fourier analysis. Making this
explicit link with higher-order Fourier analysis allows us to import tools
from that theory to use in lower bounding the stabilizer rank of quantum
states.

Next, qudit stabilizer states where the dimension of the qudit is an odd prime
$p$ are somewhat simpler as they are given by quadratic polynomials taking
values in $\mathbb{F}_{p}$ on affine subspaces in $\mathbb{F}_{p}^{n}$. Let
$\omega_{p}=e^{2\pi i/p}$ be a $p$-th root of unity. A map $Q\colon
H\to\mathbb{F}_{p}$ is a quadratic polynomial on an affine subspace
$H\subset\mathbb{F}_{p}^{n}$ if $\Delta_{h_{1}}\Delta_{h_{2}}Q(x)$ is
independent of $x\in H$ for all $h_{1},h_{2}\in L(H)$.

######  Theorem 3.3 ([14], see also [11]).

Let $p$ be an odd prime and $|\phi\rangle$ an $n$-qudit stabilizer state where
the dimension of the qudit is $p$. Then, there is an affine subspace
$H\subset\mathbb{F}_{p}^{n}$ and a quadratic polynomial $Q\colon
H\to\mathbb{F}_{p}$ such that

$|\phi\rangle=p^{-\dim(H)/2}\sum_{x\in H}\omega_{p}^{Q(x)}|x\rangle.$ (4)

######  Definition 3.4.

For an $n$-qudit quantum state $|\psi\rangle$ define its stabilizer rank,
denoted $\chi(|\psi\rangle)$, to be the minimal number $r$ needed to write
$|\psi\rangle$ as a linear combination of $r$ stabilizer states.

###  3.2 Nonclassical polynomials

We will now define what _nonclassical_ polynomials are. First, let
$P\in\mathbb{F}_{p}[x_{1},\dots,x_{n}]$ be a “classical” polynomial of degree
$d\geq 1$. One can show that $\Delta_{h}P(x)=P(x+h)-P(x)$ is again a
polynomial but of degree at most $d-1$. So after taking $d+1$ derivatives, the
resulting polynomial will be the zero polynomial. Using this observation, we
can define a broader class of polynomials as functions that take values in
$\mathbb{T}$ and satisfy a condition on its derivatives.

######  Definition 3.5.

For an integer $d\geq 1$, a map $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ is a
nonclassical polynomial of degree at most $d$ if for all
$h_{1},\dots,h_{d+1}\in\mathbb{F}_{p}^{n}$ we have

$\displaystyle\Delta_{h_{d+1}}\cdots\Delta_{h_{1}}P(x)=0.$ (5)

The degree of $P$ is the smallest such $d$.

Using the map $\iota\colon\mathbb{F}_{p}\to\mathbb{T}\colon x\to|x|/p$, one
can view a polynomial $P\in\mathbb{F}_{p}[x_{1},\dots,x_{n}]$ as a map
$\iota(P)\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$. Nonclassical polynomials that
arise in this way are called classical polynomials and they are a subset of
the nonclassical polynomials. Note that they take values in
$\frac{1}{p}\mathbb{Z}/\mathbb{Z}$. This confusing terminology has
unfortunately become standard in the literature. Below, all polynomials are
assumed to be nonclassical if it is not explicitly stated. The following
example shows that this containment of classical polynomials in the set of
nonclassical polynomials is indeed proper.

######  Example 3.6.

Let $p=2$ and consider $P\colon\mathbb{F}_{2}^{n}\to\mathbb{T}$ be given by
$x\mapsto|x|/4$. This is a nonclassical polynomial of degree two. To show
this, we take derivatives:

$\displaystyle|x+h|/4-|x|/4=|x|/4+|h|/4-|x\circ h|/2-|x|/4=|h|/4-|x\circ
h|/2\mod 1,$

where $\circ$ is entry-wise product of vectors. In the first equality we used
the property in (1). Taking one more derivative

$\displaystyle\Delta_{h^{\prime}}\Delta_{h}P(x)=-|x\circ h+h^{\prime}\circ
h|/2+|x\circ h|/2=-|h^{\prime}\circ h|/2\mod 1.$

Indeed, $P(x)=|x|/4$ is a nonclassical polynomial of degree two. Note that it
is _not_ a classical polynomial since it takes values in
$\frac{1}{4}\mathbb{Z}/\mathbb{Z}$.
In general, the polynomial $P(x)=|x|/2^{k}$ is a nonclassical polynomial of
degree $k$. We will see later (Section 4.1) that for $k=3$, this polynomial
corresponds to the $n$-qubit magic state.

Let $p=3$ and consider the polynomial
$P\colon\mathbb{F}_{3}^{n}\to\mathbb{T}\colon x\to|x|/9$. This is a
nonclassical polynomial of degree three: let $h\in\mathbb{F}_{3}^{n}$, then by
the property in (2)

$\displaystyle\Delta_{h}P(x)=|x+h|/9-|x|/9=|h|/9+(|x^{2}\circ h|+|x\circ
h^{2}|)/3-2|x\circ h|/3\mod 1.$

Here $x^{2}=x\circ x$, i.e. the entry-wise product of $x$ with itself. The
above is (up to a shift) a classical polynomial of degree two, hence $P$ is
cubic. We will see in Section 4.1 that this polynomial $P$ corresponds to the
$n$-qudit magic state where the qudit has dimension three.

The above is a local definition of nonclassical polynomials. A global
definition of classical polynomials of degree at most $d$ is that they take
the form $\sum_{i_{1}+\dots+i_{n}\leq
d}c_{i_{1},\dots,i_{n}}x_{1}^{i_{1}}\cdots x_{n}^{i_{n}}$. Similarly,
nonclassical polynomials have the following global description.

######  Proposition 3.7 ([24]).

$P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ is a nonclassical polynomial of
degree at most $d$ if and only if it has a representation of the form

$\displaystyle P(x_{1},\dots,x_{n})=\alpha+\sum_{\begin{subarray}{c}0\leq
i_{1},\dots i_{n}\leq p-1;j\geq 0:\\\ 0<i_{1}+\dots+i_{n}\leq
d-j(p-1)\end{subarray}}\frac{c_{i_{1},\dots,i_{n},j}|x_{1}|^{i_{1}}\cdots|x_{n}|^{i_{n}}}{p^{j+1}},$
(6)

for some coefficients $c_{i_{1},\dots,i_{n},j}\in\\{0,1,\dots,p-1\\}$ and
$\alpha\in\mathbb{T}$, these coefficients are unique. The maximal $j$ in this
decomposition is called the _depth_ of $P$.

Note that the depth of a nonclassical polynomial is always at most $\lceil
d/(p-1)\rceil-1$ since at least one of the indices $i_{1},\dots,i_{n}$ must be
positive. Using this proposition, one quickly sees that the polynomial
$x\mapsto|x|/4$ for $x\in\mathbb{F}_{2}^{n}$ from the example above has degree
two and depth 1. The polynomial $x\mapsto|x|/2^{k}$ has degree $k$ and depth
$k-1$.

Let $H\subset\mathbb{F}_{p}^{n}$ be an affine subspace and $Q\colon
H\to\mathbb{T}$ a map. Let
$A\colon\mathbb{F}_{p}^{\dim(H)}\to\mathbb{F}_{p}^{n}$ be an affine linear
transformation such that $A$ maps surjectively on $H$. We can view $Q$ in its
“local coordinate system”: for $y\in\mathbb{F}_{p}^{\dim(H)}$ define
$Q^{\prime}(y)=Q(A(y))$.

Let $p=2$. If $Q$ is a quadratic form (Definition 3.1), then $Q^{\prime}$ is a
nonclassical polynomial of degree at most two. Proposition 3.7 implies that
its depth is at most 1. In other words, $Q^{\prime}$ takes values in
$\frac{1}{4}\mathbb{Z}/\mathbb{Z}$ and so does $Q$.

Similarly, for $p>2$ a quadratic polynomial $Q\colon H\to\mathbb{F}_{p}$ on an
affine subspace $H\subset\mathbb{F}_{p}^{n}$, is simply a quadratic polynomial
in local coordinates, i.e. the map
$Q^{\prime}\colon\mathbb{F}_{p}^{\dim(H)}\to\mathbb{F}_{p}$ is a polynomial of
degree two in the $\dim(H)$ variables.

The following is a simple observation that we will need later, it follows
directly from Proposition 3.7.

######  Lemma 3.8.

Let $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be a nonclassical polynomial of
degree at most one. Then $P$ is classical (up to some shift).

###  3.3 Rank of nonclassical polynomials

In this section we introduce a notion of rank for nonclassical polynomials.
The main reference is again [13].

######  Definition 3.9.

Let $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be a nonclassical polynomial. For
an integer $d\geq 1$, we define the $d$-rank, denoted by
$\mathrm{rank}_{d}(P)$, to be the minimal number $r$ such that there are
nonclassical polynomials $Q_{1},\dots,Q_{r}$ all of degree at most $d-1$ and a
function $\Gamma\colon\mathbb{T}^{r}\to\mathbb{T}$ such that for all
$x\in\mathbb{F}_{p}^{n}$

$\displaystyle\Gamma(Q_{1}(x),\dots,Q_{r}(x))=P(x).$

If $d=1$, the $d$-rank will be $\infty$ if $P$ is non-constant and 0
otherwise. The rank of $P$, denoted $\mathrm{rank}(P)$, is the $\deg(P)$-rank
of $P$.

The next result [13, Corollary 7.16] is a standard application of Fourier
analysis and can be thought of as a kind of “inverse theorem”. We give the
proof here for convenience.

######  Proposition 3.10.

Let $d\geq 2$ and $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ a polynomial with
$r:=\mathrm{rank}_{d}(P)$. Then there exists a polynomial $Q$ of degree at
most $d-1$ such that

$|\langle e(P),e(Q)\rangle|\geq p^{-(1+\lceil(d-1)/(p-1)\rceil)r}.$

###### Proof.

Let $\Gamma\colon\mathbb{T}^{r}\to\mathbb{T}$ be a map and $Q_{1},\dots,Q_{r}$
be polynomials of degree at most $d-1$ such that

$\displaystyle P(x)=\Gamma(Q_{1}(x),\dots,Q_{r}(x)).$

We can assume that $\Gamma$ is a map with domain
$G:=\prod_{i=1}^{r}\frac{1}{p^{k_{i}+1}}\mathbb{Z}/\mathbb{Z}$, where $k_{i}$
is the depth of $Q_{i}$. Let $\hat{G}=\prod_{i=1}^{r}\mathbb{Z}_{p^{k_{i}+1}}$
be the dual of $G$, so that the Fourier decomposition of $e(\Gamma)$ becomes

$\displaystyle
e(\Gamma(z))=\sum_{\alpha\in\hat{G}}\hat{\Gamma}_{\alpha}e(\langle\alpha,z\rangle).$

The Fourier decomposition of $e(\Gamma)$ gives a “higher-order” Fourier
decomposition of $e(P)$: for $\alpha\in~{}\hat{G}$ define
$Q_{\alpha}(x):=\sum_{i=1}^{r}\alpha_{i}Q_{i}(x)$, then

$\displaystyle
e(P(x))=\sum_{\alpha\in\hat{G}}\hat{\Gamma}_{\alpha}e(Q_{\alpha}(x)).$

So

$\displaystyle 1=|\langle e(P),e(P)\rangle|\leq\sum_{\alpha\in\hat{G}}|\langle
e(P),e(Q_{\alpha})\rangle|.$

Indeed, there is an $\alpha^{*}$ such that

$\displaystyle|\langle e(P),e(Q_{\alpha^{*}})\rangle|\geq|\hat{G}|^{-1}.$

Since the degree of the polynomials $Q_{i}$ is at most $d-1$, it follows that
$k_{i}(p-1)\leq d-1$. This implies that

$\displaystyle|\hat{G}|=p^{k_{1}+1+\dots+k_{r}+1}\leq
p^{(1+\lceil(d-1)/(p-1)\rceil)r}.$

∎

The next lemma [13, Lemma 7.2] tells us how the rank changes if we restrict a
polynomial to an affine subspace.

######  Lemma 3.11.

Let $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be a polynomial of degree $d\geq
2$ and $r:=\mathrm{rank}(P)$. Let $U\subset\mathbb{F}_{p}^{n}$ be an affine
subspace of codimension $k$ and define $P^{\prime}$ to be the restriction of
$P$ to $U$. If $r>pk+1$ then $P^{\prime}$ is a polynomial of degree $d$ and
$\mathrm{rank}(P^{\prime})\geq r-pk$.

###### Proof.

We will prove the statement for $k=1$. The general case will follow after
repeated application of the proof for $k=1$.

Since rank and degree do not change under invertible affine linear
transformations, we can assume without loss of generality that
$U=\\{x\in\mathbb{F}_{p}^{n}\colon x_{n}=0\\}$. Let
$\pi\colon\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$ be the projection onto $U$,
so $\pi(x_{1},\dots,x_{n})=(x_{1},\dots,x_{n-1},0)$. Define
$P^{\prime\prime}=P-P^{\prime}\circ\pi$. For $x\in U$ we have
$P^{\prime\prime}(x)=0$. Let $a\in\mathbb{F}_{p}\setminus\\{0\\}$ and
$h_{a}=(0,\dots,0,a)\in\mathbb{F}_{p}^{n}$. We have that
$\Delta_{h_{a}}P^{\prime\prime}$ has degree at most $d-1$ and that
$\Delta_{h_{a}}P^{\prime\prime}(y)=P^{\prime\prime}(y+h)$ for all $y\in U$. So
$P^{\prime\prime}$ agrees with a polynomial $Q_{a}$ of degree at most $d-1$ on
$U+h_{a}$. This implies there is a function
$\Gamma\colon\mathbb{T}^{p+1}\to\mathbb{T}$ such that
$P(x)=\Gamma(|x_{n}|/p,P^{\prime}(x),Q_{1}(x),\dots,Q_{p-1}(x))$.

Now, if $P^{\prime}$ has degree at most $d-1$, then $\mathrm{rank}(P)\leq
p+1<r$, which is a contradiction. If $P^{\prime}$ has rank $<r-p$, we get that
$\mathrm{rank}(P)<r$ which is again a contradiction. ∎

Next, we define the _Fourier rank_ of a function which is a new notion of rank
for functions and prove straightforward properties of it.

######  Definition 3.12.

Let $f\colon\mathbb{F}_{p}^{n}\to\mathbb{C}$ be a function and $d\geq 1$. The
degree-$d$ Fourier rank of $f$, denoted $\mathrm{frank}_{d}(f)$, is the
minimal $r$ such that there are polynomials $Q_{1},\dots,Q_{r}$ of degree at
most $d-1$ such that for all $x\in\mathbb{F}_{p}^{n}$

$\displaystyle f(x)=\sum_{i=1}^{r}c_{i}e(Q_{i}(x)).$ (7)

The degree-2 Fourier rank of a function $f$ is also known as the _Fourier
sparsity_ of $f$. The following lemma relates the notion of rank of a
polynomial and its Fourier rank.

######  Lemma 3.13.

Let $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be a polynomial and $d\geq 2$.
Then $\mathrm{frank}_{d}(e(P))\geq\mathrm{rank}_{d}(P)$.

###### Proof.

Denote by $r^{\prime}$ the degree $d$ Fourier rank of $e(P)$. So there are
polynomials $Q_{1},\dots,Q_{r^{\prime}}$ of degree at most $d-1$ such that we
have a decomposition

$\displaystyle e(P(x))=\sum_{i=1}^{r^{\prime}}c_{i}e(Q_{i}(x)).$ (8)

We will now define a function
$\Gamma\colon\mathbb{T}^{r^{\prime}}\to\mathbb{T}$ as follows. Let
$Q\colon\mathbb{F}_{p}^{n}\to\mathbb{T}^{r^{\prime}}$ be defined by
$Q(x)=~{}(Q_{1}(x),\dots,Q_{r^{\prime}}(x))$. The map $\Gamma$ on the image of
$Q$ is defined by

$\displaystyle
e(\Gamma(Q_{1}(x),\dots,Q_{r^{\prime}}(x)))=\sum_{i=1}^{r^{\prime}}c_{i}e(Q_{i}(x)).$

For a point $z$ in the complement of the image of $Q$, we simply set
$\Gamma(z)=0$ or any other constant value would do. But the $\Gamma$ we just
defined has the property that $\Gamma(Q_{1}(x),\dots,Q_{r^{\prime}}(x))=P(x)$
by (8). Hence $r^{\prime}\geq r$, proving the statement. ∎

For $d=2$, Sanyal [21] shows that
$\mathrm{frank}_{2}(e(P))\geq\mathrm{rank}_{2}(P)^{2}$. This is quadratically
better than the above lemma. See Section 6 for a discussion for the case
$d>2$.

In the other direction, we have the following lemma.

######  Lemma 3.14.

Let $d\geq 2$ and $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ a polynomial. Then

$\mathrm{frank}_{d}(e(P))\leq
p^{(1+\lceil(d-1)/(p-1)\rceil)\mathrm{rank}_{d}(P)}.$

###### Proof.

Let $r:=\mathrm{rank}_{d}(P)$. Then there is a function
$\Gamma\colon\mathbb{T}^{r}\to\mathbb{T}$ and polynomials $Q_{1},\dots,Q_{r}$
of degree at most $d-1$ such that $\Gamma(Q_{1}(x),\dots,Q_{r}(x))=P(x)$. The
Fourier expansion of $\Gamma$ gives us a degree $d-1$ Fourier expansion of
$P$, namely

$\displaystyle e(\Gamma(Q_{1}(x),\dots,Q_{r}(x)))$
$\displaystyle=\sum_{\alpha\in\widehat{G}}\widehat{\Gamma}(\alpha)e(Q_{\alpha}(x))$
$\displaystyle=e(P(x)),$

where $Q_{\alpha}(x)=\sum_{i=1}^{r}\alpha_{i}Q_{i}(x)$ and
$\widehat{G}=\prod_{i=1}^{r}\mathbb{Z}_{p^{k_{i}+1}}$ is the dual of the group
$G=~{}\prod_{i=1}^{r}\frac{1}{p^{k_{i}+1}}\mathbb{Z}/\mathbb{Z}$ and $k_{i}$
is the depth of $Q_{i}$. Since there are at most

$|\widehat{G}|\leq~{}p^{(1+\lceil(d-1)/(p-1)\rceil)r}$

Fourier coefficients in the above expression, the result follows. ∎

##  4 Magic states in prime dimension

In this section we will give the explicit form of the magic state that we
obtain by using the generalization of the $T$ gate in odd prime dimensions
[15]. We will then proceed to show that these magic states have exponentially
small correlation with quadratic phase functions.

###  4.1 Generalization of the $T$ gate

The generalization of the $T$ gate, and hence the corresponding magic state,
curiously enough depends on whether the prime dimension $p$ is equal to three
or $p>3$.

  * •

But first, let us consider the case $p=2$. In this case, the $T$-gate is given
by $T=\begin{pmatrix}1&0\\\ 0&e^{i\pi/4}\end{pmatrix}$ and the corresponding
single qubit magic state is given by
$T|+\rangle=|T\rangle=\frac{|0\rangle+e^{i\pi/4}|1\rangle}{\sqrt{2}}$, hence
the $n$-qubit magic state is

$|T\rangle^{\otimes
n}=\frac{1}{2^{n/2}}\sum_{x\in\mathbb{F}_{2}^{n}}e(|x|/8)|x\rangle.$ (9)

Here, the polynomial $P\colon\mathbb{F}_{2}^{n}\to\mathbb{T}\colon
x\mapsto|x|/8$ is a nonclassical polynomial of degree exactly three. This
follows immediately from Proposition 3.7, see also Example 3.6. We will see a
similar phenomenon in other prime dimensions.

  * •

In the case that $p=3$, let $\xi=e^{2\pi i/9}$ be a ninth-root of unity. The
generalization of the $T$-gate for $p=3$, denoted by $U$, is given by

$U=\begin{pmatrix}1&0&0\\\ 0&\xi&0\\\ 0&0&\xi^{2}\end{pmatrix}.$

The corresponding single qudit magic state is then

$|\psi_{U}\rangle=U|+\rangle=\frac{|0\rangle+\xi|1\rangle+\xi^{2}|3\rangle}{\sqrt{3}}.$

The $n$-qudit magic state in this case is

$|\psi_{U}\rangle^{\otimes
n}=\frac{1}{3^{n/2}}\sum_{x\in\mathbb{F}_{3}^{n}}e(|x|/9)|x\rangle.$ (10)

The polynomial $P\colon\mathbb{F}_{3}^{n}\to\mathbb{T}\colon x\mapsto|x|/9$ is
again a nonclassical polynomial of degree three which follows from Proposition
3.7, see also Example 3.6.

  * •

The case $p>3$ are all similar, but different from the previous two cases. In
this case, let $\omega_{p}=e^{2\pi i/p}$ be a $p$-th root of unity and
$P\colon\mathbb{F}_{p}\to\mathbb{F}_{p}$ a classical polynomial of degree
three. Define

$U:=\sum_{x\in\mathbb{F}_{p}}\omega_{p}^{P(x)}|x\rangle\langle x|.$

This gate is then a non-clifford gate [15] and could serve as a generalization
of the $T$ gate. The condition that $P$ has degree three is important: if $P$
has degree two, then $U$ is a Clifford gate. The corresponding $n$-qudit magic
state is then

$|\psi_{U}\rangle^{\otimes
n}=\frac{1}{p^{n/2}}\sum_{x\in\mathbb{F}_{p}^{n}}\omega_{p}^{P_{n}(x)}|x\rangle,$
(11)

where $P_{n}(x)=\sum_{i=1}^{n}P(x_{i})$. Unlike the $p=2,3$ case, the
polynomial $P_{n}$ is a _classical_ polynomial of degree three.
Coincidentally, there are no cubic nonclassical polynomials for $p>3$.

###  4.2 Correlation with quadratic phase functions

We will now show that for the $n$-qudit magic states defined as above, the
correlation with quantum states whose amplitudes are given by a quadratic
phase functions is exponentially small. We need the following basic lemma, see
[17]. We will state and prove it here for convenience.

######  Lemma 4.1.

For any two functions $f,g\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$, we have

$\displaystyle|\langle
e(f),e(g)\rangle|^{4}\leq\operatorname*{\mathbb{E}}_{h\in\mathbb{F}_{p}^{n}}|\langle
e(\Delta_{h}f),e(\Delta_{h}g)\rangle|^{2}.$

###### Proof.

By the Cauchy-Schwarz inequality,

$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{h}|\langle
e(\Delta_{h}f),e(\Delta_{h}g)\rangle|^{2}}$
$\displaystyle\geq|\operatorname*{\mathbb{E}}_{h}\langle
e(\Delta_{h}f),e(\Delta_{h}g)\rangle|$
$\displaystyle=|\operatorname*{\mathbb{E}}_{x,h}e(f(x+h)-f(x)-(g(x+h)-g(x)))|$
$\displaystyle=|\langle e(f),e(g)\rangle|^{2}.$

∎

In other words, we can compute the correlation between two phase functions by
computing the correlations between their derivatives and taking their average.
If the derivatives are easier to work with, this will become useful.

######  Proposition 4.2.

Let $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be the polynomial in the phase of
the amplitudes in either Equation (9), (10) or (11). Then, for any
nonclassical polynomial $Q\colon\mathbb{F}_{p}^{n}\to~{}\mathbb{T}$ of degree
at most two,

$\displaystyle|\langle e(P),e(Q)\rangle|\leq 2^{-cn},$

for some $c>0$ depending on $p$.

###### Proof.

We will only prove it for the case $p=2$, since the other case $p>2$ is very
similar. We will show that the polynomial phase function $e(|x|/8)$, giving
the amplitudes of the $n$-qubit magic state (see (9)), has exponentially small
correlation with quadratic phase functions. First we compute the derivative of
$P$; let $h\in\mathbb{F}_{2}^{n}$. Then

$\displaystyle P(x+h)-P(x)$
$\displaystyle=|x+h|/8-|x|/8=\sum_{i}|x_{i}+h_{i}|/8-|x|/8$
$\displaystyle=\sum_{i}(|x_{i}|+|h_{i}|-2|x_{i}||h_{i}|)/8-|x|/8$
$\displaystyle=|h|/8-|x\circ h|/4.$

In the second line, we used the property (1). Let $f\colon x\mapsto e(|x\circ
h|/4)$. We need the magnitudes of the Fourier coefficients of $f$; we have for
$\alpha\in\mathbb{F}_{2}^{n}$

$\displaystyle\hat{f}(\alpha)=\operatorname*{\mathbb{E}}_{x}e^{i\pi(|x\circ
h|-2|\alpha\circ x|)/2},$

so

$\displaystyle|\hat{f}(\alpha)|^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}e^{i\pi(|x\circ h|-|y\circ
h|-2|\alpha\circ x|+2|\alpha\circ y|)/2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{y,z}e^{i\pi(|y\circ h|+|z\circ
h|-2|y\circ z\circ h|-|y\circ h|-2|\alpha\circ z|)/2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{y,z}e^{i\pi(|z\circ h|-2|y\circ
z\circ h|-2|\alpha\circ z|)/2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{z}e^{i\pi(|z\circ h|-2|\alpha\circ
z|)/2}\operatorname*{\mathbb{E}}_{y}(-1)^{|y\circ z\circ h|}.$

In the second line we used a change of variables $x=y+z$ and the property in
(1) so that

$\displaystyle|x\circ h|$ $\displaystyle=|(y+z)\circ h|=|y\circ h+z\circ
h|=|y\circ h|+|z\circ h|-2|(y\circ h)\circ(z\circ h)|$ $\displaystyle=|y\circ
h|+|z\circ h|-2|y\circ z\circ h|.$

The expectation over $y$ is 0 unless $h_{i}=1\Rightarrow z_{i}=0$ in which
case it is equal to 1. So continuing where we left off

$\displaystyle=\frac{1}{2^{n}}\sum_{z:h_{i}=1\Rightarrow
z_{i}=0}e^{i\pi(|z\circ h|-2|\alpha\circ z|)/2}$
$\displaystyle=\frac{1}{2^{n}}\sum_{z:h_{i}=1\Rightarrow
z_{i}=0}(-1)^{|\alpha\circ z|}$

which is 0 unless $h_{i}=0\Rightarrow\alpha_{i}=0$, in which case it equals
$2^{-|h|}$. So the non-zero Fourier coefficients of $f$ are at those
$\alpha\in\mathbb{F}_{2}^{n}$ for which it holds that
$h_{i}=0\Rightarrow\alpha_{i}=0$.

We will now show that there is exponentially small correlation between $e(P)$
and any nonclassical polynomial phase function $e(Q)$ of degree two. By Lemma
4.1 and Parseval, we have that

$\displaystyle|\langle e(P),e(Q)\rangle|^{4}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{h}|\langle
e(\Delta_{h}P),e(\Delta_{h}Q)\rangle|^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{h}|\langle\widehat{e(\Delta_{h}P)},\widehat{e(\Delta_{h}Q)}\rangle|^{2}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{h}2^{-|h|}$
$\displaystyle=\frac{1}{2^{n}}\sum_{k=0}^{n}2^{-k}|\\{h\in\mathbb{F}_{2}^{n}\colon|h|=k\\}|$
$\displaystyle=\left(\frac{3}{4}\right)^{n}.$

In the third line, we used that $\Delta_{h}Q$ is a degree one classical
polynomial (using Lemma 3.8), which means that $e(\Delta_{h}Q)$ has only one
non-zero Fourier coefficient and that the magnitude of all the Fourier
coefficients of $e(\Delta_{h}(P))$ is at most $2^{-|h|/2}$, see the
computation of $|\hat{f}(\alpha)|^{2}$ above where
$f(x)=e(|h|/8)e(-\Delta_{h}P(x))$.

For $p=3$, the cubic phase function giving the amplitudes of the $n$-qudit
magic states is given by (10). One follows the same strategy by first
computing the derivative of the polynomial $x\mapsto|x|/9$ using the property
(2) and computing the magnitude of the Fourier coefficients of its associated
phase function and concluding with a use of Lemma 4.1. The case $p>3$ is
simpler as it does not require any property of the map $|\cdot|$, since the
polynomial in the phase of (11) is a classical polynomial. ∎

##  5 Stabilizer rank of the $n$-qudit magic state

Here we prove Theorem 1.1, our main result.

The following claim from [20] is needed to get a handle on the affine
subspaces that appear with the stabilizer states in a stabilizer
decomposition.

######  Claim 5.1 ([20]).

Let $p$ be a prime and $H_{1},\dots,H_{r}\subset\mathbb{F}_{p}^{n}$ be a
collection of affine subspaces and assume $r\leq n/2$. Then there exists an
affine subspace $U$ of dimension at least $n-2r$ and a subset $S\subset[r]$
such that for all $x\in U$

$1_{H_{i}}(x)=\begin{cases*}1&if $i\in S$\\\ 0&otherwise.\end{cases*}$

###### Proof.

Let $E\colon\mathbb{F}_{p}^{n}\to\\{0,1\\}^{r}$ be the map given by
$x\mapsto(1_{H_{1}}(x),\dots,1_{H_{r}}(x))$. By the pigeonhole principle,
there is $\alpha\in\\{0,1\\}^{r}$ such that $|E^{-1}(\alpha)|\geq
p^{n}2^{-r}\geq p^{n-r}$. Denote by $S\subset[r]$ the set of indices $i$ such
that $\alpha_{i}=1$. It is clear that $E^{-1}(\alpha)=\cap_{i\in
S}H_{i}\setminus\cup_{i\notin S}H_{i}$ (if $S=\emptyset$, define $\cap_{i\in
S}H_{i}=\mathbb{F}_{p}^{n}$). Now define $V=\cap_{i\in S}H_{i}$, this is an
affine subspace of dimension at least $n-r$. Pick an arbitrary $x_{0}\in
E^{-1}(\alpha)$, so $x_{0}\notin H_{i}$ for $i\notin S$. This implies that
$\forall i\notin S$ there is an affine equation $h_{i}$ such that
$h_{i}(x_{0})=1$ but $h_{i}(x)=0$ for all $x\in H_{i}$. The affine subspace we
are looking for is

$U:=\\{x\in V\colon\forall i\notin S\quad h_{i}(x)=1\\}.$

Note that $U$ is not empty since $x_{0}\in U$. Since we only add at most $r$
extra equations, the dimension of $U$ is at least $n-2r$. ∎

#### Proof of Theorem 1.1

Let $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be the nonclassical polynomial of
degree three given by the corresponding $n$-qudit magic state, depending on
the prime $p$. For $p=2$, $p=3$ and $p>3$ it is given by the (polynomials in
the phase of the) amplitudes of Equation (9), (10) and (11) respectively. Let
$|\psi\rangle$ be the corresponding $n$-qudit magic state, i.e.

$\displaystyle|\psi\rangle=p^{-n/2}\sum_{x\in\mathbb{F}_{p}^{n}}e(P(x))|x\rangle.$

Denote by $r$ the stabilizer rank of $|\psi\rangle$, so there is a
decomposition

$\displaystyle|\psi\rangle=\sum_{i=1}^{r}c_{i}|\phi_{i}\rangle,$

for some constants $c_{i}$ and stabilizer states $|\phi_{i}\rangle$. Each such
$\phi_{i}$ is defined on an affine subspace $H_{i}\subset\mathbb{F}_{p}^{n}$.
Let $C>0$ be a large enough constant111Given the prime $p$ and the constant
$c$ from Proposition 4.2, the constant $C$ should satisfy $C>2p/c$.. If
$r>n/C$, we are done. So assume $r\leq n/C$. Then, we have that

$\displaystyle e(P(x))$ $\displaystyle=p^{n/2}\langle
x|\psi\rangle=p^{n/2}\sum_{i=1}^{r}c_{i}\langle x|\phi_{i}\rangle$
$\displaystyle=\sum_{i=1}^{r}c^{\prime}_{i}e(Q_{i}(x))1_{H_{i}}(x),$

where $Q_{i}$ is a quadratic polynomial on $H_{i}$ and
$c_{i}^{\prime}=p^{(n-\dim(H_{i}))/2}c_{i}$. Then by Claim 5.1 (using
$r\leq~{}n/C$), there is an affine subspace $U$ of dimension $cn$ for some
$c\geq 0.99$ and a non-empty subset $S\subset[r]$ such that $\forall x\in U$

$1_{H_{i}}(x)=\begin{cases*}1&if $i\in S$\\\ 0&otherwise.\end{cases*}$

Let $A\colon\mathbb{F}_{p}^{cn}\to\mathbb{F}_{p}^{n}$ be an affine linear map
such that $U=\\{A(y)\colon y\in\mathbb{F}_{p}^{cn}\\}$. Let
$P^{\prime}\colon\mathbb{F}_{p}^{cn}\to\mathbb{T}$ be the polynomial given by
$P^{\prime}(y)=P(A(y))$. Then the restriction of the above decomposition of
$e(P(x))$ to $U$ implies that

$\displaystyle e(P^{\prime}(y))=\sum_{i\in
S}c^{\prime}_{i}e(Q^{\prime}_{i}(y)),$ (12)

where $Q^{\prime}_{i}(y):=Q_{i}(A(y))$ and we have that $Q^{\prime}_{i}$ is a
nonclassical polynomial of degree at most two. By Proposition 4.2 and (the
contrapositive of) 3.10 the polynomial $P$ has high rank:
$\mathrm{rank}(P)\geq\Omega(n)$. By Lemma 3.11 it follows that $P^{\prime}$ is
still cubic and we have $\mathrm{rank}(P^{\prime})\geq\Omega(n)$ (this uses
that $C$ is a large enough constant). But (12) is a decomposition in terms of
nonclassical polynomial phase functions of degree at most two. By Lemma 3.13
we have $|S|\geq\Omega(n)$ so that $r\geq\Omega(n)$.∎

##  6 Discussion

From the above proof, we can immediately conclude that it is not possible to
get super-linear lower bounds on the stabilizer rank of $n$-qudit magic states
using these techniques. This is due to the use of Claim 5.1. However, there is
no obvious obstruction to get super-linear lower bounds on the number of
stabilizer states needed in a decomposition of $n$-qudit magic states where
all the stabilizer states are defined on the full space $\mathbb{F}_{p}^{n}$.
The graph states (classical quadratic polynomials) are for example in this
set. The possibility of such a super-linear lower bound hinges on the
relationship between the rank of a polynomial and its Fourier rank: the
$d$-rank of a polynomial $P$ on $n$ variables is at most $n$, whereas the
degree-$d$ Fourier rank of a polynomial is at most $p^{n}$. Lemma 3.13 only
shows that $\mathrm{frank}_{d}(e(P))\geq\mathrm{rank}_{d}(P)$. Is this
relation optimal, or can we expect much better?

######  Problem 6.1.

Let $d\geq 2$ and $P\colon\mathbb{F}_{p}^{n}\to\mathbb{T}$ be a polynomial. Is
it true that

$\displaystyle\mathrm{frank}_{d}(e(P))\geq\omega(\mathrm{rank}_{d}(P))?$

A positive answer to this question would not only show that the $n$-qubit
magic state needs super-linear many stabilizer states defined on the full
space $\mathbb{F}_{p}^{n}$, but would also have implications in another field.
For this, let us consider the case $p=2$.

Let $\mathrm{AND}(x)=|x_{1}x_{2}\cdots x_{n}|/2$ be the (classical) polynomial
giving the AND function. The “quadratic uncertainty principle” [8] is a
conjecture that states that any decomposition

$\displaystyle e(\mathrm{AND}(x))=\sum_{i=1}^{r}c_{i}e(Q_{i}(x)),$ (13)

where $Q_{i}$ are classical quadratic polynomials, must have $r\geq
2^{\Omega(n)}$. Note that Definitions 3.9 and 3.12 of rank and frank are still
valid if we only allow _classical_ polynomials, which we will denote by
$\mathrm{rank}^{\prime}$ and $\mathrm{frank}^{\prime}$. The best known lower
bound is $\mathrm{frank}^{\prime}_{3}(e(\mathrm{AND}))\geq n/2$ [25]. The
proof of this uses the Chevalley-Warning theorem in an elegant way. It shows,
implicitly, that the 3-$\mathrm{rank}^{\prime}$ of the AND function is at
least $n/2$, i.e. near maximal rank. This way of looking at it fits very well
with Lemma 3.13. What is actually shown in [25] is the same lower bound for
the NOR function, i.e. $\mathrm{NOR}(x)=|1+x_{1}|\cdots|1+x_{n}|/2$. Lower
bounds on the NOR function imply the same lower bounds on the AND function (it
is the same function in a different basis). The proof also works if we allow
polynomials of degree at most a constant.

######  Theorem 6.2 ([25], generalized).

Let $\mathrm{NOR}\colon\mathbb{F}_{2}^{n}\to\mathbb{T}$ be the function
defined above and let $d\geq 3$ be an integer (constant). Then
$\mathrm{frank}^{\prime}_{d}(e(\mathrm{NOR}))\geq n/(d-1)$.

###### Proof.

We will show that $\mathrm{rank}^{\prime}_{d}(\mathrm{NOR})\geq n/(d-1)$.
Having shown this, the result follows immediately from Lemma 3.13 (which also
holds for $\mathrm{rank}^{\prime}$ and $\mathrm{frank}^{\prime}$).

Let $r=\mathrm{rank}^{\prime}_{d}(\mathrm{NOR})$. So there are (classical)
polynomials $Q_{1},\dots,Q_{r}$ of degree at most $d-1$ such that there is a
function $\Gamma\colon\mathbb{T}^{r}\to\mathbb{T}$ such that

$\displaystyle\mathrm{NOR}(x)=\Gamma(Q_{1}(x),\dots,Q_{r}(x)).$

We may assume without loss of generality that $Q_{i}(0)=0$ for all
$i=1,\dots,r$ (since $\Gamma$ can always add/subtract a constant to/from
$Q_{i}$). Assume that $r<n/(d-1)$. By the Chevalley-Warning theorem, the
polynomials $Q_{1},\dots,Q_{r}$ have another common root $x\neq(0,\dots,0)$.
This contradicts the fact that $\mathrm{NOR}(x)=1/2$ if and only if
$x=(0,\dots,0)$. ∎

Since the NOR function has $\mathrm{rank}^{\prime}_{3}(\mathrm{NOR})\geq n/2$,
a positive answer to Problem 6.1 would show that the number of quadratic
polynomials needed in (13) is super-linear. As noted before, Sanyal [21]
showed that
$\mathrm{frank}^{\prime}_{2}(e(P))\geq\mathrm{rank}^{\prime}_{2}(P)^{2}$. An
analogue of this result for $d>2$ would quadratically improve the best lower
bound on $\mathrm{frank}^{\prime}_{3}(\mathrm{NOR})$.

## References

  * Bannink et al. [2019] Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee.  Bounding quantum-classical separations for classes of nonlocal games.  In _36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)_ , pages 12:1–12:11, March 2019.  doi: 10.4230/LIPIcs.STACS.2019.12.
  * Bravyi and Gosset [2016] Sergey Bravyi and David Gosset.  Improved classical simulation of quantum circuits dominated by clifford gates.  _Phys. Rev. Lett._ , 116:250501, Jun 2016.  doi: 10.1103/PhysRevLett.116.250501.
  * Bravyi and Kitaev [2005] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal clifford gates and noisy ancillas.  _Physical Review A_ , 71(2):022316, 2005.  doi: 10.1103/PhysRevA.71.022316.
  * Bravyi et al. [2016] Sergey Bravyi, Graeme Smith, and John A. Smolin.  Trading classical and quantum computational resources.  _Phys. Rev. X_ , 6:021043, Jun 2016.  doi: 10.1103/PhysRevX.6.021043.
  * Bravyi et al. [2019] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard.  Simulation of quantum circuits by low-rank stabilizer decompositions.  _Quantum_ , 3:181, September 2019.  doi: 10.22331/q-2019-09-02-181.
  * Chen et al. [2018] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi.  Classical simulation of intermediate-size quantum circuits.  _arXiv preprint arXiv:1805.01450_ , 2018.
  * Dehaene and De Moor [2003] Jeroen Dehaene and Bart De Moor.  Clifford group, stabilizer states, and linear and quadratic operations over gf(2).  _Phys. Rev. A_ , 68:042318, Oct 2003.  doi: 10.1103/PhysRevA.68.042318.
  * Filmus et al. [2014] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O’Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer.  Real analysis in computer science: A collection of open problems.  _Preprint available at https://simons. berkeley. edu/sites/default/files/openprobsmerged. pdf_ , 2014.
  * Gottesman [1998] D Gottesman.  The heisenberg representation of quantum computers.  6 1998.  URL https://www.osti.gov/biblio/319738.
  * Gowers [1998] William Timothy Gowers.  A new proof of szemerédi’s theorem for arithmetic progressions of length four.  _Geometric & Functional Analysis GAFA_, 8(3):529–551, 1998.
  * Gross [2006] D. Gross.  Hudson’s theorem for finite-dimensional quantum systems.  _Journal of Mathematical Physics_ , 47(12):122107, 2006.  doi: 10.1063/1.2393152.
  * Häner and Steiger [2017] Thomas Häner and Damian S. Steiger.  0.5 petabyte simulation of a 45-qubit quantum circuit.  In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. ACM, 2017.  doi: 10.1145/3126908.3126947.
  * Hatami et al. [2019] Hamed Hatami, Pooya Hatami, and Shachar Lovett.  Higher-order fourier analysis and applications.  _Foundations and Trends® in Theoretical Computer Science_ , 13(4):247–448, 2019.  doi: 10.1561/0400000064.
  * Hostens et al. [2005] Erik Hostens, Jeroen Dehaene, and Bart De Moor.  Stabilizer states and clifford operations for systems of arbitrary dimensions and modular arithmetic.  _Physical Review A_ , 71(4), apr 2005.  doi: 10.1103/physreva.71.042315.
  * Howard and Vala [2012] Mark Howard and Jiri Vala.  Qudit versions of the qubit $\pi$/8 gate.  _Physical Review A_ , 86(2):022316, 2012.  doi: 10.1103/PhysRevA.86.022316.
  * Liu and Winter [2020] Zi-Wen Liu and Andreas Winter.  Many-body quantum magic.  _arXiv preprint arXiv:2010.13817_ , 2020.
  * Lovett et al. [2008] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky.  Inverse conjecture for the gowers norm is false.  In _Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing_ , STOC ’08, page 547–556, 2008.  doi: 10.1145/1374376.1374454.
  * Nielsen and Chuang [2010] Michael A. Nielsen and Isaac L. Chuang.  _Quantum Computation and Quantum Information: 10th Anniversary Edition_.  Cambridge University Press, 2010.  doi: 10.1017/CBO9780511976667.
  * Pednault et al. [2017] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, and Robert Wisnieff.  Breaking the 49-qubit barrier in the simulation of quantum circuits.  _arXiv preprint arXiv:1710.05867_ , 15, 2017.
  * Peleg et al. [2022] Shir Peleg, Ben Lee Volk, and Amir Shpilka.  Lower Bounds on Stabilizer Rank.  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ , volume 215 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 110:1–110:4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.  doi: 10.4230/LIPIcs.ITCS.2022.110.
  * Sanyal [2019] Swagato Sanyal.  Fourier sparsity and dimension.  _Theory of Computing_ , 15(11):1–13, 2019.  doi: 10.4086/toc.2019.v015a011.
  * Smelyanskiy et al. [2016] Mikhail Smelyanskiy, Nicolas PD Sawaya, and Alán Aspuru-Guzik.  qhipster: The quantum high performance software testing environment.  _arXiv preprint arXiv:1601.07195_ , 2016.
  * Szemerédi [1975] Endre Szemerédi.  On sets of integers containing no $k$ elements in arithmetic progression.  _Acta Arith_ , 27(199-245):2, 1975.  URL http://eudml.org/doc/205339.
  * Tao and Ziegler [2012] Terence Tao and Tamar Ziegler.  The inverse conjecture for the gowers norm over finite fields in low characteristic.  _Annals of Combinatorics_ , 16(1):121–188, 2012\.  doi: 10.1007/s00026-011-0124-3.
  * Williams [2018] Richard Ryan Williams.  Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials.  In _33rd Computational Complexity Conference (CCC 2018)_ , volume 102 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 6:1–6:24. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018.  doi: 10.4230/LIPIcs.CCC.2018.6.