# New techniques for bounding stabilizer rank

Benjamin Lovitz<EMAIL_ADDRESS>Vincent Steffan<EMAIL_ADDRESS>
###### Abstract

In this work, we present number-theoretic and algebraic-geometric techniques
for bounding the stabilizer rank of quantum states. First, we refine a number-
theoretic theorem of Moulton to exhibit an explicit sequence of product states
with exponential stabilizer rank but constant approximate stabilizer rank, and
to provide alternate (and simplified) proofs of the best-known asymptotic
lower bounds on stabilizer rank and approximate stabilizer rank, up to a log
factor. Second, we find the first non-trivial examples of quantum states with
multiplicative stabilizer rank under the tensor product. Third, we use
algebraic-geometric techniques to prove new bounds on the generic stabilizer
rank.

##  1 Introduction

It is of great practical importance to determine the classical simulation cost
of quantum computations. Indeed, lower bounds on the simulation cost indicate
quantum speedups, while upper bounds can help us to understand the limitations
of quantum computation. The stabilizer rank is a useful barometer for
determining the classical simulation cost of quantum circuits [BSS16]. A
stabilizer state is a quantum state in the orbit of a computational basis
state under the action of the Clifford group (which is defined in Section 2).
For a (pure) quantum state $[\psi]$, we define its stabilizer rank, denoted
$\chi([\psi])$, to be the smallest integer $r$ for which $[\psi]$ can be
written as a superposition of $r$ stabilizer states. The stabilizer rank is
motivated by the fact that the classical simulation cost of applying Clifford
gates and computational basis measurements to $[\psi]$ under current state-of-
the-art simulation protocols scales polynomially in the number of Clifford
gates and linearly in $\chi([\psi])$ (see Appendix A, and [BSS16, BG16,
BBC+19, QPG21]). For a real number $\delta>0$, the $\delta$-approximate
stabilizer rank, $\chi_{\delta}([\psi])$, is defined as the minimum stabilizer
rank over all quantum states that are $\delta$-close to $[\psi]$, and
similarly quantifies the classical simulation cost of approximating the
application of Clifford gates and computational basis measurements on
$[\psi]$. Our notation $[\psi]$ is projective, and can be thought of as
$\frac{1}{\lVert\mspace{1.0mu}\psi\mspace{1.0mu}\rVert^{2}}\psi\psi^{*}$ for a
non-zero vector $\psi$, where $(\cdot)^{*}$ denotes the conugate-transpose and
$\lVert\mspace{1.0mu}\cdot\mspace{1.0mu}\rVert$ denotes the Euclidean norm.

The $T$-count of a quantum state $[\psi]$ is the number of $T$-gates needed to
prepare $[\psi]$ using a circuit consisting only of Clifford+$T$-gates and
post-selective computational basis measurements (we define the $T$-gate in
Appendix A). It is known that if $[\psi]$ has $T$-count $n$, then
${\chi([\psi])\leq\chi([T^{\otimes n}])}$, where
$[T]=[\mathrm{e}_{0}+e^{i\pi/4}\mathrm{e}_{1}]$ is the so-called $T$-state,
and $\mathrm{e}_{0},\mathrm{e}_{1}$ are the computational basis vectors in
$\mathbb{C}^{2}$ [BSS16]. It is therefore of particular interest to determine
$\chi([T^{\otimes n}])$ and $\chi_{\delta}([T^{\otimes n}])$.

Despite the practical importance of the stabilizer rank, few techniques are
known for bounding this quantity. In this work, we introduce techniques from
number theory and algebraic geometry for bounding the stabilizer rank. In
particular, we:

  1. 1.

Refine a theorem of Moulton on subset-sum representations of exponentially
increasing sequences, and use this refinement to prove lower bounds on exact
and approximate stabilizer rank. In particular, we:

     * •

Exhibit an explicit sequence of $n$-qubit product states of exponentially
increasing stabilizer rank and constant $\delta$-approximate stabilizer rank
for any fixed $\delta>0$.

     * •

Prove that for any non-stabilizer qubit state $[\psi]$, it holds that
$\linebreak{\chi([\psi^{\otimes n}])=\Omega(n/\log_{2}n)}$, and in particular,
${\chi([T^{\otimes n}])\geq\frac{n+1}{4\log_{2}(n+1)}.}$ Our asymptotic
scaling matches the best-known lower bound ${\chi([T^{\otimes n}])\geq n/100}$
up to a log factor [PSV21].

     * •

Prove that for any non-stabilizer qubit state $[\psi]$, there exists a
constant $\delta>0$ for which ${\chi_{\delta}([\psi^{\otimes
n}])\geq\sqrt{n}/(2\log_{2}n)}$ for all $n\geq 2$. In particular, our
asymptotic scaling for the $T$-state matches the best-known lower bound
${\chi_{\delta}([T^{\otimes n}])=\Omega(\sqrt{n}/\log_{2}n)}$ [PSV21].

  2. 2.

Explicitly construct the first non-trivial examples of quantum states with
multiplicative stabilizer rank under the tensor product.

  3. 3.

Use algebraic-geometric techniques to prove bounds on, and useful reductions
for, the generic stabilizer rank, which upper bounds $\chi([T^{\otimes n}])$.

In the remainder of this introduction, we expand on points 1, 2, and 3, and
identify directions for future work. In Section 2 we review some mathematical
preliminaries for this work. In Sections 3, 4, and 5 we prove the results
introduced in points 1, 2, and 3, respectively. In Appendix A we review
motivation for the stabilizer rank as a measure of the computational cost of
classical simulations of quantum circuits.

###  1.1 Lower bounds on stabilizer rank and approximate stabilizer rank

In Section 3, we refine a number-theoretic theorem of Moulton to prove lower
bounds on stabilizer rank and approximate stabilizer rank [Mou01]. Let
$[n]=\\{1,\dots,n\\}$ when $n$ is a positive integer. For integers $q\geq 2$
and $r\geq 1$, and tuples of non-zero complex numbers

$\displaystyle\alpha$
$\displaystyle=(\alpha_{1},\dots,\alpha_{q})\in\mathbb{C}^{q}$ (1)
$\displaystyle\beta$
$\displaystyle=(\beta_{1},\dots,\beta_{r})\in\mathbb{C}^{r},$ (2)

we say that $\beta$ is a subset-sum representation of $\alpha$ if for all
$i\in[q]$ there exists a subset $R_{i}\subseteq[r]$ for which $\sum_{j\in
R_{i}}\beta_{j}=\alpha_{i}$. We refer to the integer $r$ as the length of the
subset-sum representation $\beta\in\mathbb{C}^{r}$. For an integer $2\leq
p\leq q$, we say that $\alpha\in\mathbb{C}^{q}$ has an exponentially
increasing subsequence of length $p$ if there exists $i_{1},\dots,i_{p}\in[q]$
for which

$\displaystyle\lvert\alpha_{i_{j+1}}\rvert\geq
2\lvert\alpha_{i_{j}}\rvert\quad\text{for all}\quad j\in[p].$ (3)

Moulton’s theorem states that any subset-sum representation of a $q$-tuple
containing the subsequence $(1,2,4,\dots,2^{p-1})$ has length at least
$p/\log_{2}p$ [Mou01]. We refine this result to prove that the same bound
holds for any $q$-tuple that contains an exponentially increasing subsequence
of length $p$ (Theorem 3.1).

Since stabilizer states have coordinates in $\\{0,\pm 1,\pm i\\}$ in the
computational basis (see Section 2), any decomposition of a state $[\psi]$
into a superposition of $r$ stabilizer states can be converted into a
length-$4r$-subset-sum representation of the coordinates of $[\psi]$. It
follows that if the coordinates of $[\psi]$ contain an exponentially
increasing subsequence of length $p$, then $\chi([\psi])\geq p/(4\log_{2}p)$
(Theorem 3.2). In particular, since $[T]$ is Clifford-equivalent to
$[H]:=[\mathrm{e}_{0}+\frac{1}{\sqrt{2}-1}\mathrm{e}_{1}]$, and the
coordinates of $[H^{\otimes n}]$ contain an exponentially increasing
subsequence of length $n+1$, we obtain $\chi([T^{\otimes
n}])\geq\frac{n+1}{4\log_{2}(n+1)}$. By a similar argument, we prove that
$\chi([\psi^{\otimes n}])=\Omega(n/\log_{2}n)$ for any non-stabilizer qubit
state $[\psi]$ (Theorem 3.2).

We further use Theorem 3.1, along with standard concentration inequalities for
the binomial distribution, to prove that for any non-stabilizer qubit state
$[\psi]$ there exists a constant $\delta>0$ for which it holds that
$\chi_{\delta}([\psi^{\otimes n}])\geq\sqrt{n}/(2\log_{2}n)$ for all $n\geq 2$
(Theorem 3.5).

Very recently, Peleg et al. obtained similar results: They proved that
$\chi([T^{\otimes n}])\geq n/100$, and that there exists $\delta>0$ for which
$\chi_{\delta}([T^{\otimes n}])=\Omega(\sqrt{n}/\log_{2}n)$ [PSV21].
Asymptotically, our bounds match theirs up to a log factor, and we suggest
that our proof technique is much simpler. While both of our bounds follow
quite quickly from our refinement of Moulton’s theorem mentioned above, the
two bounds of Peleg et al. use two different approaches from the analysis of
boolean functions and complexity theory: For their lower bound on
$\chi([T^{\otimes n}])$, they analyze directional derivatives of quadratic
polynomials, and for their lower bound on $\chi_{\delta}([T^{\otimes n}])$,
they use Razborov-Smolensky low-degree polynomial approximations and
correlation bounds against the majority function [Raz87, Smo87, Smo93]. It is
interesting that the vastly different approaches of ours and Peleg et al.
yield such similar results.

As a further application of our refinement of Moulton’s theorem, we explicitly
construct a sequence of $n$-qubit product states $[\psi^{\otimes n}]$ for
which it holds that $\chi([\psi^{\otimes n}])\geq\frac{2^{n}}{4n}$ and
${\chi_{\delta}([\psi^{\otimes n}])=\mathcal{O}(1)}$ for any $\delta>0$,
simply by writing down a product state with exponentially increasing
coordinate amplitudes. Note that the stabilizer rank of this sequence is very
close to $2^{n}$, the maximum possible of any $n$-qubit state. This result
lies contrast to the situation for other notions of rank, in which it is a
difficult open problem to explicitly construct sequences of states of near-
maximal rank. For example, the maximum border rank, a relevant notion of rank
in classical complexity theory, of a quantum state in three local spaces of
(affine) dimensions $d$, is $\lceil\frac{d^{3}}{3d-2}\rceil$ for all $d\neq
3$, whereas the largest border rank of any known explicit sequence of states
in this space is only linear in $d$ (see [LM19] for the largest known border
rank and [Lan11] for a general introduction into the topic).

###  1.2 States with multiplicative stabilizer rank under the tensor product

It is a standard fact that the stabilizer rank is sub-multiplicative under the
tensor product, i.e. $\chi([\psi\otimes\psi])\leq\chi([\psi])^{2}$ for any
quantum state $[\psi]$ [Qas21, Section 2.1.3]. In [Qas21, Section 4.4] it was
remarked that there are no known examples of quantum states $[\psi]$ of
stabilizer rank greater than one for which equality holds. In Section 4, we
explicitly construct two-qubit states $[\psi]$ for which $\chi([\psi])=2$ and
$\chi([\psi\otimes\psi])=4.$ This is the smallest possible example of such a
state, since for any single-qubit state $[\phi]$ it holds that
$\chi([\phi\otimes\phi])\leq 3$.

###  1.3 Generic stabilizer rank

For any positive integer $n$, all but finitely many qubit states $[\psi]$
maximize $\chi([\psi^{\otimes n}])$ (Fact 5.1). This motivates us to define
the $n$-th generic stabilizer rank, denoted $\chi_{n}$, to be the maximum
stabilizer rank of any state of the form $[\psi^{\otimes n}]$. In Section 5,
we prove new bounds on $\chi_{n}$, along with some useful reductions for
studying this quantity. In Proposition 5.2 we modestly improve the best-known
upper bound on $\chi_{n}$, recently obtained by Qassim et al., from
$\mathcal{O}((n+1)2^{n/2})$ to $\mathcal{O}(2^{n/2})$ [QPG21, Theorem 2]. In
Propositions 5.3 and 5.4 we prove two useful reductions for studying
$\chi_{n}$, namely, that there must exist a single set of $\chi_{n}$
stabilizer states that span the symmetric subspace, and that it suffices to
work over the real numbers. In Proposition 5.5 we introduce a technique for
upper bounding $\chi_{n}$ when upper bounds on $\chi([\psi^{\otimes n}])$ are
known for sufficiently many (linear in $n$) qubit states $[\psi]$. In
Proposition 5.6 we compute an upper bound on the (finite) number of qubit
states $[\psi]$ for which $\chi([\psi^{\otimes n}])<\chi_{n}$.

###  1.4 Directions for future work

We believe that our work opens the door for new approaches on questions
related to the stabilizer rank. Here, we present two of the most promising
ones.

####  1.4.1 Lower bounds on stabilizer rank via the $T$-count

As we mentioned in the second paragraph of the introduction, for any quantum
state $[\psi]$ of $T$-count $n$, it holds that $\chi([T^{\otimes
n}])\geq\chi([\psi])$ [BSS16]. We prove in Theorem 3.2 that if the coordinates
of $[\psi]$ contain an exponentially increasing subsequence of length $p$,
then $\chi([\psi])\geq p/(4\log_{2}p)$. Combining these two statements, if we
can find a sequence of states $[\psi]$ with small $T$-counts and long
exponentially increasing subsequences of coordinates, then we can obtain large
lower bounds on $\chi([T^{\otimes n}])$. For example, if we can find a
sequence of states $[\psi_{n}]$ with $T$-count $\mathcal{O}(2^{cn})$ for some
$0<c<1$, whose coordinates contain an exponentially increasing subsequence of
length $\Omega(2^{n})$, then we would obtain a super-linear lower bound
$\chi(T^{\otimes n})=\Omega\left(\frac{n^{1/c}}{\log_{2}n}\right)$.

####  1.4.2 Bounds on generic stabilizer rank

In Section 5 we prove several reductions for studying the generic stabilizer
rank $\chi_{n}$, but only manage to modestly improve the best-known bounds on
this quantity. We ask whether stronger bounds can be obtained from our
reductions.

## Acknowledgments

We thank Gerry Myerson for pointing us to the work of Moulton [Mou01]. BL
thanks Kieran Mastel and William Slofstra for helpful discussions. VS thanks
Daniel Stilck França and Matthias Christandl for helpful discussions. VS
acknowledges financial support from VILLUM FONDEN via the QMATH Centre of
Excellence (Grant No. 10059).

##  2 Background

We use projective notation for quantum states, which we briefly review here,
and refer the reader to [LJ20] for a more in-depth treatment. For a non-zero
complex vector space $\mathcal{V}$, let $\mathbb{P}(\mathcal{V})$ (or more
briefly, $\mathbb{P}\mathcal{V}$) be the set of $1$-dimensional linear
subspaces of $\mathcal{V}$, and let
$\mathbb{P}^{N}=\mathbb{P}(\mathbb{C}^{N+1})$ for any non-negative integer
$N$. We abuse the $[\cdot]$ notation and also write $[v]\in\mathbb{P}\\\ V$
for the span of a non-zero vector $v\in\mathcal{V}$. Crucially, we identify
$\mathbb{P}\mathcal{V}$ with the set of pure quantum states in $\mathcal{V}$,
under the canonical bijection which identifies a 1-dimensional linear subspace
with the unique unit vector in that subspace modulo global phase. For a subset
$X\subseteq\mathbb{P}\mathcal{V}$, let $\hat{X}\subseteq\mathcal{V}$ be the
affine cone over $X$, i.e. $\hat{X}=\\{x\in\mathcal{V}:[x]\in
X\\}\cup\\{0\\}$. Let $\mathcal{S}(\mathcal{V})$ be the set of unit vectors in
$\mathcal{V}$.

For a positive integer $n$, let $\mathcal{V}_{n}=(\mathbb{C}^{2})^{\otimes
n}$. We refer to elements of $\mathcal{V}_{n}$ as tensors, and elements of
$\mathcal{S}(\mathcal{V}_{n})$ as unit tensors. Let
$S^{n}(\mathbb{C}^{2})\subseteq\mathcal{V}_{n}$ be the symmetric subspace of
tensors that are invariant under permutation of the subsystems.

For a complex vector space $\mathcal{V}$, let $\mathrm{U}(\mathcal{V})$ be the
unitary group on $\mathcal{V}$. For a positive integer $n$, let
$\mathrm{Pauli}_{n}\subseteq\mathrm{U}(\mathcal{V}_{n})$ be the Pauli group,
the group generated by all $n$-fold tensor products of elements of the set
$\\{X,Z,i\mathds{1}_{2}\\}\subseteq\mathrm{U}(\mathbb{C}^{2})$, where

$X=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix},$

and $\mathds{1}_{k}$ is the identity matrix in $\mathrm{U}(\mathbb{C}^{k})$
for any positive integer $k$. The Clifford group, denoted
$\mathrm{Cliff}_{n}\subseteq\mathrm{U}(\mathcal{V}_{n})$, is the normalizer of
the Pauli group in $\mathrm{U}(\mathcal{V}_{n})$. The projective Clifford
group, denoted $\mathcal{C}_{n}$, is defined as
$\mathrm{Cliff}_{n}/\mathrm{U}(\mathbb{C})$, the Clifford group modulo phases.
The projective Clifford group is generated by the (equivalence classes of)
tensor products of elements of the set $\\{H,S,CNOT\\}$, where

$H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix},S=\begin{pmatrix}1&0\\\
0&i\end{pmatrix},\quad\text{and}\quad CNOT=\begin{pmatrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{pmatrix}.$

A quantum state $[\psi]\in\mathbb{P}^{2^{n}-1}$ is called a _stabilizer state_
if $[\psi]=U\left[\mathrm{e}_{0}^{\otimes n}\right]$ for some
$U\in\mathcal{C}_{n}$. Let
$\mathrm{Stab}_{n}=\mathcal{C}_{n}[\mathrm{e}_{0}^{\otimes n}]$ be the set of
stabilizer states. It is well known that a state
$[\psi]\in\mathbb{P}^{2^{n}-1}$ is a stabilizer state if and only if

$[\psi]=\left[\sum_{x\in A}i^{l(x)}\cdot(-1)^{q(x)}\cdot\mathrm{e}_{x}\right]$
(4)

for some affine linear subspace $A\subseteq\mathbb{F}_{2}^{n}$, linear form
$l\colon\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$, and quadratic form
$q\colon\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$ [DDM03, VdN10]. Here and
throughout, we define
$\mathrm{e}_{x}:=\mathrm{e}_{x_{1}}\otimes\dots\otimes\mathrm{e}_{x_{n}}$ when
$x\in\mathbb{F}_{2}^{n}$.

We say that a projective variety $Y\subseteq\mathbb{P}^{2^{n}-1}$ is non-
degenerate if $\operatorname{span}(Y)=\mathbb{P}^{2^{n}-1}$. For a projective,
non-degenerate variety $Y\subseteq\mathbb{P}^{2^{n}-1}$, we define the $r-$th
secant variety to $Y$, $\Sigma_{r}(Y),$ to be the Zariski closure of the set
of points in $\mathbb{P}^{2^{n}-1}$ that lie in the span of $r$ points in $Y$.
We will almost exclusively take $Y=\mathrm{Stab}_{n},$ which is a non-
degenerate, zero-dimensional projective variety (i.e. a finite set of points
that span $\mathbb{P}^{2^{n}-1}$). In this case, the set of points in
$\mathbb{P}^{2^{n}-1}$ that lie in the span of $r$ points in
$\mathrm{Stab}_{n}$ is already closed. The _stabilizer rank_ of a state
$[\psi]\in\mathbb{P}^{2^{n}-1}$, denoted $\chi([\psi])$, is the smallest
integer $r$ for which $[\psi]\in\Sigma_{r}(\mathrm{Stab}_{n})$. In other
words, it is the smallest integer $r$ for which

$\psi=\sum_{i=1}^{r}c_{i}\sigma_{i}$

for some complex numbers $c_{i}\in\mathbb{C}$ and stabilizer states
$[\sigma_{i}]\in\mathrm{Stab}_{n}$.

We also have an approximate version of stabilizer rank. For a positive real
number $\delta>0$ and state $[\psi]\in\mathbb{P}^{2^{n}-1}$, we define the
$\delta$-approximate stabilizer rank of $[\psi]$, denoted
$\chi_{\delta}([\psi])$, as

$\chi_{\delta}([\psi])=\min\bigg{\\{}\chi([\phi]):\biggl{\lVert}\mspace{1.0mu}\frac{\phi}{\lVert\mspace{1.0mu}\phi\mspace{1.0mu}\rVert}-\frac{\psi}{\lVert\mspace{1.0mu}\psi\mspace{1.0mu}\rVert}\mspace{1.0mu}\biggr{\rVert}<\delta\bigg{\\}}.$

We say a quantum state $[\psi]\in\mathbb{P}^{2^{n}-1}$ is real if $\psi$ is
proportional to a state with only real coordinates in the computational basis.
A quantum state $[\psi]$ is a real stabilizer state if and only if it can be
written in the form (4) with $l=0$. The set of real stabilizer states in
$\mathbb{P}^{2^{n}-1}$, which we denote by $\mathrm{Stab}_{n}^{\mathbb{R}}$,
is precisely the orbit of $[e_{0}^{\otimes n}]$ under the group generated by
the (equivalence classes of) $H$ and $CNOT$ [DDM03]. For a quantum state
$[\psi]\in\mathbb{P}^{2^{n}-1}$, we define the real stabilizer rank of
$[\psi]$, denoted $\chi^{\mathbb{R}}([\psi])$, to be the smallest integer $r$
for which $[\psi]$ can be written as a (complex) superposition of $r$ real
stabilizer states.

We close this section by computing the number of stabilizer states and real
stabilizer states, which we will use in Section 5 to upper bound the number of
states of sub-generic rank. It is a standard fact that there are
$\binom{n}{k}_{2}$ distinct $k$-dimensional linear subspaces of
$\mathbb{F}_{2}^{n}$, where

$\displaystyle\binom{n}{k}_{2}=\prod_{i=0}^{k-1}\frac{2^{n-i}-1}{2^{k-i}-1}$
(5)

is the Gaussian binomial coefficient (see e.g. [GR70]). Since there are
$2^{n-k}$ distinct affine translations of a $k$-dimensional linear subspace of
$\mathbb{F}_{2}^{n}$, it follows that there are $\binom{n}{k}_{2}2^{n-k}$
distinct affine linear subspaces of dimension $k$. For each index $k\in[n]$
and each $k$-dimensional affine subspace $A\subseteq\mathbb{F}_{2}^{n}$, there
are $2^{k(k+1)/2}$ distinct quadratic forms on $A$ and $2^{k}$ distinct linear
functions on $A$. It follows that

$\displaystyle\lvert\mathrm{Stab}_{n}\rvert$
$\displaystyle=2^{n}\sum_{k=1}^{n}\binom{n}{k}_{2}2^{k(k+1)/2}$ (6)
$\displaystyle=2^{n}\prod_{k=1}^{n}(2^{k}+1),$ (7)

where the second line follows from the Gaussian binomial theorem (see e.g.
[GR70]). Similarly,

$\displaystyle\bigl{\lvert}\mathrm{Stab}_{n}^{\mathbb{R}}\bigr{\rvert}=2^{n}\sum_{k=1}^{n}\binom{n}{k}_{2}.$
(8)

The quantity $\lvert\mathrm{Stab}_{n}\rvert$ was previously computed in
[Gro06, Corollary 21] using a different proof technique.

##  3 Lower bounds on stabilizer rank and approximate stabilizer rank

In this section, we refine a number-theoretic theorem of Moulton, and use this
to prove lower bounds on the stabilizer rank and approximate stabilizer rank.
Recall the definitions of exponentially increasing subsequences and subset-sum
representations given in Section 1.1. Moulton proved that any subset-sum
representation of a $q$-tuple containing the subsequence
$(1,2,4,\dots,2^{p-1})$ has length at least $p/\log_{2}p$ [Mou01]. In Section
3.1, we refine this result to prove that the same bound holds for any
$q$-tuple containing an exponentially increasing subsequence of length $p$
(Theorem 3.1). In Section 3.2 we use our refinement to prove that any quantum
state whose coordinates contain an exponentially increasing subsequence of
length $p$ has stabilizer rank at least $p/(4\log_{2}p)$ (Theorem 3.2). We
then use this result to explicitly construct a sequence of product states of
exponential stabilizer rank, to prove that $\chi([T^{\otimes
n}])\geq\frac{n+1}{4\log_{2}(n+1)}$, and to prove that $\chi([\psi^{\otimes
n}])=\Omega(n/\log_{2}n)$ for any non-stabilizer qubit state $[\psi]$. In
Section 3.3 we use our refinement of Moulton’s theorem to prove that, for any
non-stabilizer qubit state $[\psi]$, there exists $\delta>0$ for which
$\chi_{\delta}([\psi^{\otimes n}])\geq\sqrt{n}/(2\log_{2}n)$ for all
$n\in\mathbb{N}$.

###  3.1 A refinement of Moulton’s theorem

######  Theorem 3.1 (Refinement of Theorem 1 in [Mou01]).

Let $2\leq p\leq q$ be integers, and let $\alpha\in\mathbb{C}^{q}$ be a
$q$-tuple of non-zero complex numbers. If $\alpha$ contains an exponentially
increasing subsequence of length $p$, then any subset-sum representation of
$\alpha$ has length at least $p/\log_{2}(p)$.

###### Proof.

It suffices to consider the case $p=q$ and
$2\lvert\alpha_{i}\rvert\leq\lvert\alpha_{i+1}\rvert$ for all $i\in[q-1]$. Let
$\beta\in\mathbb{C}^{r}$ be a subset-sum representation of $\alpha$. Then for
each $i\in[q]$, there exists $c_{i}\in\\{0,1\\}^{r}$ such that
$\alpha_{i}=\beta^{\mathrm{T}}c_{i}$ Suppose that, for some
$u_{1},\dots,u_{q},v_{1},\dots,v_{q}\in\\{0,1\\}$, we have

$\displaystyle\sum_{i=1}^{q}u_{i}c_{i}=\sum_{i=1}^{q}v_{i}c_{i}.$ (9)

Applying $\beta^{\mathrm{T}}$ to both sides gives

$\displaystyle\sum_{i=1}^{q}u_{i}\alpha_{i}=\sum_{i=1}^{q}v_{i}\alpha_{i}.$
(10)

It follows that $u_{i}=v_{i}$ for all $i\in[q]$. Indeed, it suffices to prove
that $\lvert\alpha_{i+1}\rvert>\lvert\alpha_{1}+\dots+\alpha_{i}\rvert$ for
all $i\in[q-1]$, which in turn can be easily verified by an inductive
argument. By assumption, $\lvert\alpha_{2}\rvert>\lvert\alpha_{1}\rvert$, and
by induction,

$\displaystyle\lvert\alpha_{1}+\dots+\alpha_{i}\rvert\leq\lvert\alpha_{1}+\dots+\alpha_{i-1}\rvert+\lvert\alpha_{i}\rvert<2\lvert\alpha_{i}\rvert\leq\lvert\alpha_{i+1}\rvert.$
(11)

The remainder of the proof is identical to that of [Mou01]. There are at most
${2^{q}-1}$ choices of $u_{1},\dots,u_{q}\in\\{0,1\\}$, excluding the case
$u_{1}=\dots=u_{q}=1$. For each of these choices, the sum
$\sum_{i=1}^{q}u_{i}c_{i}$ can take one of $q^{r}-1$ possible choices in
$\\{0,1,\dots,q-1\\}^{\times r}$ (the choice
$(q-1,q-1,\dots,q-1)^{\mathrm{T}}$ is excluded since the $u_{i}$ are not all
equal to 1). Since each choice of $u_{1},\dots,u_{q}$ yields a different
vector, we must have $q^{r}-1\geq 2^{q}-1$, i.e. ${r\geq q/\log_{2}(q)}$. ∎

###  3.2 Lower bounds on stabilizer rank

In this subsection we use Theorem 3.1 to prove lower bounds on stabilizer
rank.

######  Theorem 3.2.

Let $p\geq 2$ be an integer, and let $[\psi]\in\mathbb{P}^{2^{n}-1}$ be a
quantum state. If the coordinates of $\psi$ contain an exponentially
increasing subsequence of length $p$, then $\chi([\psi])\geq p/(4\log_{2}p)$.

###### Proof.

Let $r=\chi([\psi])$, let $x_{1},\dots,x_{p}\in\mathbb{F}_{2}^{n}$ be such
that $\lvert\psi_{x_{i}}\rvert\leq 2\lvert\psi_{x_{i+1}}\rvert$ for all
${i\in[p-1]}$, and let
$\alpha=(\psi_{x_{1}},\dots,\psi_{x_{p}})\in\mathbb{C}^{p}$. Without loss of
generality, there exist complex numbers
$\\{c_{i}:i\in[r]\\}\subseteq\mathbb{C}$ and stabilizer states
$\\{[\sigma_{i}]:i\in[r]\\}\subseteq\mathrm{Stab}_{n}$ such that for all
$i\in[r]$, every coordinate of $\sigma_{i}$ is an element of $\\{0,\pm 1,\pm
i\\},$ and $\psi=\sum_{i=1}^{r}c_{i}\sigma_{i}$. Let

$\displaystyle S=(\sigma_{1},\dots,\sigma_{r})\in\\{0,\pm 1,\pm
i\\}^{\\{0,1\\}^{n}\times r}$ (12)

and

$\displaystyle{c=(c_{1},\dots,c_{r})\in\mathbb{C}^{r}},$ (13)

so that $Sc=\psi$. In particular, there exists a $p\times r$ submatrix $T$ of
$S$ for which $Tc=\alpha$. Let $T_{1},T_{2},T_{3},T_{4}\in\\{0,1\\}^{p\times
r}$ be such that

${T=T_{1}-T_{2}+i(T_{3}-T_{4})}.$

Then

$\displaystyle(T_{1},T_{2},T_{3},T_{4})(c,-c,ic,-ic)^{\mathrm{T}}=Tc=\alpha,$
(14)

so $(c,-c,ic,-ic)$ is a subset-sum representation of $\alpha$. It follows from
Theorem 3.1 that $4r\geq p/(\log_{2}p)$. This completes the proof. ∎

Theorem 3.2 allows us to construct an explicit sequence of product states with
exponential stabilizer rank and constant approximate stabilizer rank.

######  Corollary 3.3.

For any $n\in\mathbb{N}$, let

$\displaystyle\psi_{n}=\bigotimes_{i=1}^{n}(\mathrm{e}_{0}+2^{2^{i-1}}\mathrm{e}_{1})\in\mathcal{V}_{n}.$
(15)

Then $\chi([\psi_{n}])\geq\frac{2^{n}}{4n}$ and for any constant $\delta>0$,
$\chi_{\delta}([\psi_{n}])=\mathcal{O}(1)$.

###### Proof.

For each $n$, the coordinates of $\psi_{n}$ form an exponentially increasing
sequence of length $2^{n}$. It follows from Theorem 3.2 that
$\chi([\psi_{n}])\geq\frac{2^{n}}{4n}$. The bound
$\chi_{\delta}([\psi_{n}])=\mathcal{O}(1)$ is obtained as follows. For each
$i\in\\{0,1,\dots,2^{n}-1\\}$, let

$\displaystyle c_{i}=\sum_{j=0}^{i}4^{j}=\frac{{4^{i+1}-1}}{3},$ (16)

and observe that for any positive integer $k$, the tensor
$\phi_{n,k}\in\mathcal{V}_{n}$ obtained by setting all but the $k$ largest
coordinates of $\psi_{n}$ to zero satisfies

$\displaystyle\biggl{\lVert}\mspace{1.0mu}\frac{\psi_{n}}{\lVert\mspace{1.0mu}\psi_{n}\mspace{1.0mu}\rVert}-\frac{\phi_{n,k}}{\lVert\mspace{1.0mu}\phi_{n,k}\mspace{1.0mu}\rVert}\mspace{1.0mu}\biggr{\rVert}^{2}$
$\displaystyle=\biggl{\lVert}\mspace{1.0mu}\frac{1}{\sqrt{c_{2^{n}-1}}}\sum_{i=0}^{2^{n}-1}2^{i}\mathrm{e}_{i}-\frac{1}{\sqrt{c_{2^{n}-1}-c_{2^{n}-k-1}}}\sum_{i=2^{n}-k}^{2^{n}-1}2^{i}\mathrm{e}_{i}\mspace{1.0mu}\biggr{\rVert}^{2}$
(17)
$\displaystyle=\frac{c_{2^{n}-k-1}}{c_{2^{n}-1}}+\left(\frac{1}{\sqrt{c_{2^{n}-1}}}-\frac{1}{\sqrt{c_{2^{n}-1}-c_{2^{n}-k-1}}}\right)^{2}(c_{2^{n}-1}-c_{2^{n}-k-1})$
(18)
$\displaystyle=\frac{c_{2^{n}-k-1}}{c_{2^{n}-1}}+\left[\sqrt{1-\frac{c_{2^{n}-k-1}}{c_{2^{n}-1}}}-1\right]^{2}$
(19)
$\displaystyle=\frac{4^{1-k}-4^{1-2^{n}}}{1-4^{1-2^{n}}}+\left[\sqrt{\frac{1-4^{1-k}}{1-4^{1-2^{n}}}}-1\right]^{2},$
(20)

where we have re-indexed the computational basis of $\mathcal{V}_{n}$ as
$\mathrm{e}_{0},\dots,\mathrm{e}_{2^{n}-1}$ for clarity in this proof. The
quantity (20) can clearly be set to less than $\delta^{2}$ for any constant
$\delta>0$ by appropriate choice of $k=\mathcal{O}(1)$. Since
$\chi([\phi_{n,k}])\leq k$, this completes the proof. ∎

Theorem 3.2 also implies the following lower bound on $\chi([T^{\otimes n}])$,
and more generally, on $\chi([\psi^{\otimes n}])$ for any non-stabilizer qubit
state $[\psi]$.

######  Corollary 3.4.

For any state $[\psi]\in\mathbb{P}^{1}$ that is not a stabilizer state,
$\chi([\psi^{\otimes n}])=\Omega(n/\log_{2}n)$. In particular,

$\displaystyle\chi(\left[T^{\otimes n}\right])\geq\frac{n+1}{4\log_{2}(n+1)}.$
(21)

###### Proof.

Since $[\psi]$ is not a stabilizer state, there exists $\alpha\in\mathbb{C}$
with $\lvert\alpha\rvert>1$ for which
${[\tau]:=[\mathrm{e}_{0}+\alpha\mathrm{e}_{1}]}$ is in the
$\mathcal{C}_{1}$-orbit of $[\psi]$. Indeed, without loss of generality,
$[\psi]=[\mathrm{e}_{0}+\beta\mathrm{e}_{1}]$ for some complex number
$\beta\in\mathbb{C}^{\times}\setminus\\{0,\pm 1,\pm i\\}$, because $[\psi]$ is
not a stabilizer state. If $\lvert\beta\rvert>1$ we are done, and if
$\lvert\beta\rvert<1$ then let $[\tau]=X[\psi]$. If $\lvert\beta\rvert=1$ then
either $H[\psi]$ or $XH[\psi]$ must have the desired form. When $[\psi]=[T]$,
we can take
$[\tau]=XH[\psi]=[\mathrm{e}_{0}+\frac{i}{\sqrt{2}-1}\mathrm{e}_{1}]$.

Since $\lvert\alpha\rvert>1$, there exists $k\in\mathbb{N}$ for which
$\lvert\alpha\rvert^{k}\geq 2$. (When $[\psi]=[T]$, we can take ${k=1}$.) Now
observe that the complex numbers
$1,\alpha^{k},\alpha^{2k},\dots,\alpha^{\lfloor n/k\rfloor k}$ all appear as
coordinates of $\psi$. By Theorem 3.2, it follows that

$\displaystyle\chi([\psi^{\otimes n}])\geq\frac{\lfloor
n/k\rfloor+1}{4\log_{2}(\lfloor n/k\rfloor+1)}.$ (22)

This completes the proof. ∎

###  3.3 Lower bounds on approximate stabilizer rank

In this subsection, we use Theorem 3.1 to prove that, for any non-stabilizer
qubit state $[\psi]$, there exists a constant $\delta>0$ for which
$\chi_{\delta}([\psi^{\otimes n}])\geq\sqrt{n}/(2\log_{2}n).$

######  Theorem 3.5.

For any non-stabilizer qubit state $[\psi]\in\mathbb{P}^{1}$, there exists a
constant $\delta>0$ such that, for every integer $n\geq 2$,

$\chi_{\delta}([\psi^{\otimes n}])\geq\frac{{\sqrt{n}}}{2\log_{2}n}.$

###### Proof.

As in the proof of Corollary 3.4, since $[\psi]$ is not a stabilizer state,
there exists $\alpha\in\mathbb{C}$ with $\lvert\alpha\rvert>1$ for which
$[\mathrm{e}_{0}+\alpha\mathrm{e}_{1}]\in\mathcal{C}_{1}([\psi])$. Let
$\beta=\frac{1}{\sqrt{1+\lvert\alpha\rvert^{2}}}$,
$\gamma=\frac{\alpha}{\sqrt{1+\lvert\alpha\rvert^{2}}},$ and
${\tau=\beta\mathrm{e}_{0}+\gamma\mathrm{e}_{1}}$, so that
$\tau\in\mathcal{S}(\mathbb{C}^{2})$ and
$[\tau]=[\mathrm{e}_{0}+\alpha\mathrm{e}_{1}]$. Since the (approximate)
stabilizer rank is unchanged under $\mathcal{C}_{n}$, it suffices to lower
bound the approximate stabilizer rank of $[\tau^{\otimes n}]$.

Let $k\in\mathbb{N}$ be the smallest integer for which
$\lvert\alpha\rvert^{k}>2$, and let
$\lambda=\frac{2}{\lvert\alpha\rvert^{k}}$. If $[\psi]=[T]$, then we can take
$\alpha=\frac{1}{\sqrt{2}-1}$ and $k=1$. Let
$\phi\in\mathcal{S}(\mathcal{V}_{n})$ be a unit tensor, and let
$S\subseteq[n]$ be the set of integers $p\in[n]$ for which

$\displaystyle\lvert\gamma\rvert^{2}n-k\lceil\sqrt{n}\rceil\leq
p\leq\lvert\gamma\rvert^{2}n+k\lceil\sqrt{n}\rceil,$ (23)

and for all $x\in\mathbb{F}_{2}^{n}$ of Hamming weight $\lvert x\rvert=p$,

$\displaystyle\lvert\tau_{x}^{\otimes
n}-\phi_{x}\rvert\geq\left(\frac{1-\lambda}{1+\lambda}\right)\lvert\beta\rvert^{n-p}\lvert\gamma\rvert^{p}.$
(24)

By DeMoivre-Laplace, there exists a constant $c>0$ (which may depend on
$\lvert\alpha\rvert$, but does not depend on $n$) for which

$\displaystyle\left(\frac{1-\lambda}{1+\lambda}\right)^{2}\binom{n}{p}\lvert{\beta}^{n-p}{\gamma}^{p}\rvert^{2}\geq
c/\sqrt{n}$ (25)

for all $p\in S$ (see [Fel91, Section VII, Theorem 1] or [PSV21, Claim 4.6]).
It follows that

$\displaystyle\bigl{\lVert}\mspace{1.0mu}\tau^{\otimes
n}-\phi\mspace{1.0mu}\bigr{\rVert}^{2}\geq\sum_{p\in
S}\left(\frac{1-\lambda}{1+\lambda}\right)^{2}\binom{n}{p}\lvert\beta^{n-p}\gamma^{p}\rvert^{2}\geq\lvert
S\rvert\frac{c}{\sqrt{n}}.$ (26)

Let $\delta=\sqrt{ck}$, and suppose that
$\bigl{\lVert}\mspace{1.0mu}\tau^{\otimes
n}-\phi\mspace{1.0mu}\bigr{\rVert}<\delta$. Then $\lvert S\rvert\leq
k\sqrt{n}$. Let $P\subseteq[n]$ be the set of integers $p\in[n]$ that satisfy
(23) and are not contained in $S$. Observe that $\lvert P\rvert\geq
k\lceil\sqrt{n}\rceil$. By our definition of $P$, for each $p\in P$ there
exists $x_{p}\in\mathbb{F}_{2}^{n}$ with $\lvert x_{p}\rvert=p$ and

$\displaystyle\bigl{\lvert}\tau^{\otimes
n}_{x_{p}}-\phi_{x_{p}}\bigr{\rvert}\leq\left(\frac{1-\lambda}{1+\lambda}\right)\lvert\beta\rvert^{n-p}\lvert\gamma\rvert^{p}.$
(27)

For any $p,q\in P$ with $p<q$, it holds that

$\displaystyle\frac{\lvert\phi_{x_{q}}\rvert}{\bigl{\lvert}\phi_{{x_{p}}}\bigr{\rvert}}$
$\displaystyle=\frac{\bigl{\lvert}\phi_{x_{q}}-\tau^{\otimes
n}_{x_{q}}+\tau^{\otimes
n}_{x_{q}}\bigr{\rvert}}{\bigl{\lvert}\phi_{x_{p}}-\tau^{\otimes
n}_{x_{p}}+\tau^{\otimes n}_{x_{p}}\bigr{\rvert}}$ (28)
$\displaystyle\geq\frac{\bigl{\lvert}\tau^{\otimes
n}_{x_{q}}\bigr{\rvert}-\bigl{\lvert}\phi_{x_{q}}-\tau^{\otimes
n}_{x_{q}}\bigr{\rvert}}{\bigl{\lvert}\tau^{\otimes
n}_{x_{p}}\bigr{\rvert}+\bigl{\lvert}\phi_{x_{p}}-\tau^{\otimes
n}_{x_{p}}\bigr{\rvert}}$ (29)
$\displaystyle\geq\lambda\frac{\bigl{\lvert}\beta^{n-q}\gamma^{q}\bigr{\rvert}}{\bigl{\lvert}\beta^{n-p}\gamma^{p}\bigr{\rvert}}$
(30) $\displaystyle=\lambda\lvert\alpha\rvert^{q-p},$ (31)

where the first line is trivial, the second is the triangle inequality, the
third follows from (27), and the fourth is obvious. In particular, if $q-p\geq
k$, then $\frac{\lvert\phi_{x_{q}}\rvert}{\lvert\phi_{{x_{p}}}\rvert}\geq 2$.
Since $\lvert P\rvert\geq k\lceil\sqrt{n}\rceil$, there exists a subset
$Q\subseteq P$ of size $\lvert Q\rvert\geq\sqrt{n}$ for which $p-q\geq k$ for
all $p,q\in Q$ with $p<q$. By Theorem 3.2,

$\displaystyle\chi([\phi])\geq\frac{\sqrt{n}}{2\log_{2}(n)}.$ (32)

This completes the proof. ∎

We note that, using [Fel91, Section VII, Theorem 1] and a similar proof as
above, slight improvements to the above bound can be obtained if $\delta$ is
allowed to decay in $n$.

##  4 States with multiplicative stabilizer rank under the tensor product

It is a standard fact that the stabilizer rank is sub-multiplicative under the
tensor product, i.e. $\chi([\psi\otimes\psi])\leq\chi([\psi])^{2}$ for any
quantum state $[\psi]$ [Qas21, Section 2.1.3]. In [Qas21, Section 4.4] it was
remarked that there are no known examples of quantum states $[\psi]$ of
stabilizer rank greater than one for which equality holds. In this section, we
explicitly construct two-qubit states $[\psi]$ for which $\chi([\psi])=2$ and
$\chi([\psi\otimes\psi])=4$. Note that this is the smallest non-trivial
example of multiplicative stabilizer rank that one can hope for, since for any
single-qubit state
$[\psi]=[\mathrm{e}_{0}+\alpha\mathrm{e}_{1}]\in\mathbb{P}^{1}$, it holds that
$[\psi^{\otimes
2}]=[\mathrm{e}_{00}+\alpha(\mathrm{e}_{01}+\mathrm{e}_{10})+\alpha^{2}\mathrm{e}_{11}]$,
which has stabilizer rank at most 3.

######  Theorem 4.1.

Let

$\displaystyle\psi_{\alpha}=\mathrm{e}_{00}+\alpha(\mathrm{e}_{01}+\mathrm{e}_{10})\in(\mathbb{C}^{2})^{\otimes
2}$ (33)

when $\alpha\in\mathbb{C}^{\times}$ is a non-zero complex number. Then
$\chi([\psi_{\alpha}])=2$, and for all but finitely many $\alpha$ it holds
that $\chi([\psi_{\alpha}^{\otimes 2}])=4$. In particular,
$\chi([\psi_{\alpha}^{\otimes 2}])=4$ for any $\alpha$ that is transcendental
over $\mathbb{Q}$.

###### Proof.

The fact that $\chi([\psi_{\alpha}])=2$ is obvious, so it suffices to prove
that $\chi([\psi_{\alpha}^{\otimes 2}])=4$. Note that, since the imaginary
unit $i$ is algebraic over $\mathbb{Q}$, $\alpha$ is transcendental over
$\mathbb{Q}$ if and only if it is transcendental over $\mathbb{Q}(i)$. Since
there are only finitely many stabilizer states, it suffices to prove that for
any set of three stabilizer states
$\\{[\sigma_{1}],[\sigma_{2}],[\sigma_{3}]\\}\subseteq\mathrm{Stab}_{2}$,
there are at most finitely many $\alpha$ (and no $\alpha$ which are
transcendental over $\mathbb{Q}$) for which

$\displaystyle\psi_{\alpha}^{\otimes
2}\in\operatorname{span}\\{\sigma_{1},\sigma_{2},\sigma_{3}\\}.$ (34)

For each $j\in[3],$ we may assume that

$\displaystyle\sigma_{j}=\sum_{x\in
A_{j}}i^{l_{j}(x)}\cdot(-1)^{q_{j}(x)}\cdot\mathrm{e}_{x}$

for some affine linear subspace $A_{j}\subseteq\mathbb{F}_{2}^{2}$, linear
functional $l_{j}$, and quadratic form $q_{j}$, as in (4). Let
$S=(\sigma_{1},\sigma_{2},\sigma_{3})\in\mathbb{Q}(i)^{\\{0,1\\}^{n}\times
3}$. For every $\alpha$ that satisfies (34), there exist complex numbers
$\beta_{\alpha},\gamma_{\alpha},\lambda_{\alpha}\in\mathbb{C}$ for which
$\psi_{\alpha}^{\otimes
2}=\beta_{\alpha}\sigma_{1}+\gamma_{\alpha}\sigma_{2}+\lambda_{\alpha}\sigma_{3}$,
and a $3\times 3$ submatrix $T$ of $S$ for which

$\displaystyle\begin{bmatrix}T&-\mathds{1}_{3}\end{bmatrix}\begin{bmatrix}\beta_{\alpha}\\\
\gamma_{\alpha}\\\ \lambda_{\alpha}\\\ 1\\\ \alpha\\\
\alpha^{2}\end{bmatrix}=0.$ (35)

Since there are only finitely many $3\times 3$ submatrices of $S$, it suffices
to prove that for any choice of $3\times 3$ submatrix $T$, only finitely many
$\alpha$ (and no transcendental $\alpha$) can satisfy (35).

If $T$ is singular, then there exists a non-trivial $\mathbb{Q}(i)$-linear
combination of $\\{1,\alpha,\alpha^{2}\\}$ that equals zero, which at most
finitely many $\alpha$ will satisfy (and in particular, no transcendental
$\alpha$ will satisfy).

If $T$ is nonsingular, then by applying $T^{-1}$ to both sides we can find
polynomials ${f,g,h\in\mathbb{Q}(i)[x]}$ for which
$\beta_{\alpha}=f(\alpha),\gamma_{\alpha}=g(\alpha)$, and
$\lambda_{\alpha}=h(\alpha)$ for every choice of $\alpha$ that satisfies (35).

Let $R=\\{00,01,10\\}^{\times 2}\subseteq\mathbb{F}_{2}^{4}$ be the subset of
bitstrings corresponding to non-zero coordinates of $\psi_{\alpha}^{\otimes
2}$. If there exists $x\in A_{i}\setminus R$ for some $i\in[3]$, then there
exists a non-trivial $\mathbb{Q}(i)$-linear combination of $\\{f,g,h\\}$ which
equals zero, which at most finitely many $\alpha$ (and no transcendental
$\alpha$) will satisfy. So we may assume $A_{i}\subseteq R$ for all $i\in[3]$.

Let $R_{0}=\\{0000\\}$, $R_{1}=\\{0001,0010,0100,1000\\}$, and
$R_{2}=\\{0101,0110,1001,1010\\}$, so $R=R_{0}\cup R_{1}\cup R_{2}$. If there
exists $x\in A_{1}\cap R_{2}$ and $y\in R_{2}\setminus A_{1}$, then there
exist linear combinations

$\displaystyle\star f(\alpha)+$ $\displaystyle\cdot g(\alpha)+\cdot
h(\alpha)=\alpha^{2}$ $\displaystyle\cdot g(\alpha)+\cdot
h(\alpha)=\alpha^{2},$

where each $\cdot\in\mathbb{C}$ denotes an arbitrary complex number we do not
bother to name, and each $\star\in\mathbb{C}^{\times}$ denotes an arbitrary
non-zero complex number we don’t bother to name. Subtracting these equations
yields a non-trivial $\mathbb{Q}(i)$-linear combination of $\\{f,g,h\\}$ that
equals zero, which at most finitely many $\alpha$ (and no transcendental
$\alpha$) will satisfy. By symmetry, for all $i\in[3]$, either $R_{2}\subseteq
A_{i}$ or $R_{2}\cap A_{i}=\emptyset$. If $R_{2}\subseteq A_{i}$, then
$R_{2}=A_{i}$ because this is the only affine linear subspace contained in $R$
that contains $R_{2}$. Without loss of generality, we may assume
$A_{1}=R_{2}$. If $A_{2}=R_{2}$, then $A_{3}=R_{0}\cup S_{1}$, which is not an
affine linear subspace, a contradiction. Otherwise, $A_{2}\cup A_{3}=R_{0}\cup
R_{1}$, which is also a contradiction, as there are no affine linear subspaces
of size greater than 2 contained in $R_{0}\cup R_{1}$. This completes the
proof. ∎

##  5 Generic stabilizer rank

######  Fact 5.1.

For any positive integer $n$, all but finitely many qubit states
$[\psi]\in\mathbb{P}^{1}$ maximize $\chi([\psi^{\otimes n}])$. Similarly, all
but finitely many qubit states $[\psi]\in\mathbb{P}^{1}$ maximize
$\chi^{\mathbb{R}}([\psi^{\otimes n}])$.

This fact, the proof of which we defer until after introducing this section,
motivates us to define the $n$-th generic stabilizer rank as

$\displaystyle\chi_{n}=\max_{[\psi]\in\mathbb{P}^{1}}\chi([\psi^{\otimes
n}]),$ (36)

and the $n$-th generic real stabilizer rank as

$\displaystyle\chi_{n}^{\mathbb{R}}=\max_{[\psi]\in\mathbb{P}^{1}}\chi^{\mathbb{R}}([\psi^{\otimes
n}]).$ (37)

In Proposition 5.4 we prove that $\chi_{n}$ and $\chi_{n}^{\mathbb{R}}$ differ
by at most a constant factor of two. This motivates the study of
$\chi_{n}^{\mathbb{R}}$, since it has the same scaling as $\chi_{n}$, but may
be easier to work with. Note that $\chi_{n}$ upper bounds $\chi([T^{\otimes
n}])$.

In this section, we prove bounds on $\chi_{n}$ and $\chi_{n}^{\mathbb{R}}$,
and observe some useful reductions for studying these quantities. In
Proposition 5.2 we use Fact 5.1 to obtain a modest improvement of the best-
known upper bound on $\chi_{n}$. In Proposition 5.3 we prove a useful
reduction for studying $\chi_{n}$ (respectively, $\chi_{n}^{\mathbb{R}}$),
namely, that there must exist a single set of $\chi_{n}$ stabilizer states
(resp. $\chi_{n}^{\mathbb{R}}$ real stabilizer states) that span the symmetric
subspace. As an immediate consequence, there exists a single set of $\chi_{n}$
stabilizer states (resp. $\chi_{n}^{\mathbb{R}}$ real stabilizer states) such
that, for every qubit state $[\psi]$, the state $[\psi^{\otimes n}]$ lies in
the span of the set. In Proposition 5.5 we introduce a technique for upper
bounding $\chi_{n}$ when upper bounds on $\chi([\psi^{\otimes n}])$ are known
for sufficiently many (linear in $n$) qubit states $[\psi]$, and obtain
similar results for $\chi_{n}^{\mathbb{R}}$. In Proposition 5.6 we refine Fact
5.1 to obtain quantitative upper bounds on the (finite) number of states of
sub-generic stabilizer rank and sub-generic real stabilizer rank.

Before proceeding, we prove Fact 5.1. We refer the reader to [Har13] for the
basic algebraic-geometric definitions and arguments used in this proof, and
elsewhere in this section. In this proof and in others in this section, we
only prove the statement for $\chi_{n}$, as the proof for
$\chi_{n}^{\mathbb{R}}$ is essentially identical.

###### Proof of Fact 5.1.

We prove only the statement for $\chi_{n}$. Let

$\displaystyle\nu_{n}(\mathbb{P}^{1})=\\{[\phi^{\otimes
n}]:[\phi]\in\mathbb{P}^{1}\\}\subseteq\mathbb{P}^{2^{n}-1},$ (38)

which happens to be the image of the $n$-th _Veronese embedding_ of
$\mathbb{P}^{1}$, embedded in $\mathbb{P}^{2^{n}-1}$. The set
$\nu_{n}(\mathbb{P}^{1})$ forms a 1-dimensional irreducible projective
variety, so its intersection with any other projective variety is either
empty, zero-dimensional, or equal to $\nu_{n}(\mathbb{P}^{1})$. Hence, for any
positive integer $r$,
$\Sigma_{r}(\mathrm{Stab}_{n})\cap\nu_{n}(\mathbb{P}^{1})$ is either a finite
set of points, or
$\Sigma_{r}(\mathrm{Stab}_{n})\supseteq\nu_{n}(\mathbb{P}^{1}).$ This
completes the proof. ∎

Fact 5.1 immediately implies the following slight improvement of the upper
bound $\chi_{n}=\mathcal{O}((n+1)2^{n/2})$ obtained in [QPG21, Theorem 3]:

######  Proposition 5.2.

$\chi_{n}=\mathcal{O}(2^{n/2})$.

###### Proof.

This follows directly from our Fact 5.1 and [QPG21, Theorem 2], which states
that equitorial states (an infinite family of states) have stabilizer rank
$\mathcal{O}(2^{n/2})$. ∎

We next prove that the affine cone over a single set of $\chi_{n}$ stabilizer
states (respectively, $\chi_{n}^{\mathbb{R}}$ real stabilizer states) spans
$S^{n}(\mathbb{C}^{2}).$

######  Proposition 5.3.

For any positive integer $n$, there exists a single set of stabilizer states
$\\{[\sigma_{1}],\dots,[\sigma_{\chi_{n}}]\\}\subseteq\mathrm{Stab}_{n}$ for
which

$\displaystyle
S^{n}(\mathbb{C}^{2})\subseteq\operatorname{span}\\{\sigma_{1},\dots,\sigma_{\chi_{n}}\\}.$
(39)

Similarly, there exists a single set of real stabilizer states
$\\{[\sigma_{1}],\dots,[\sigma_{\chi_{n}^{\mathbb{R}}}]\\}\subseteq\mathrm{Stab}_{n}^{\mathbb{R}}$
for which

$\displaystyle
S^{n}(\mathbb{C}^{2})\subseteq\operatorname{span}\\{\sigma_{1},\dots,\sigma_{\chi_{n}^{\mathbb{R}}}\\}.$
(40)

Since $\dim(S^{n}(\mathbb{C}^{2}))=n+1$, it follows from Proposition 5.3 that
$\chi_{n}\geq n+1$. We note that a similar proof as below can be used to show
that a generic product state of the form
$[\psi_{1}\otimes\dots\otimes\psi_{n}]$, for qubit states
$\psi_{i}\in\mathbb{P}^{1}$, has stabilizer rank $2^{n}$, where in this
context we define generic in the same algebraic-geometric sense as in [LJ20].
In Corollary 3.3 we have constructed an explicit sequence of product states of
stabilizer rank at least $\frac{2^{n}}{4n}$, which is near maximal.

###### Proof of Proposition 5.3.

We prove only the statement for $\chi_{n}$. Let $r=\chi_{n}$, so
$\Sigma_{r}(\mathrm{Stab}_{n})\supseteq\nu_{n}(\mathbb{P}^{1}),$ where
$\nu_{n}(\mathbb{P}^{1})$ is defined in the proof of Fact 5.1. Since
$\nu_{n}(\mathbb{P}^{1})$ is irreducible, and $\Sigma_{r}(\mathrm{Stab}_{n})$
is reducible into a finite union of projective $(r-1)$-dimensional linear
subspaces, one of these subspaces must contain $\nu_{n}(\mathbb{P}^{1})$. To
complete the proof, recall that the affine cone over
$\operatorname{span}(\nu_{n}(\mathbb{P}^{1}))$ is $S^{n}(\mathbb{C}^{2})$. ∎

The next proposition shows that $\chi_{n}^{\mathbb{R}}$ and $\chi_{n}$ differ
by at most a constant factor of two, which motivates the study of
$\chi_{n}^{\mathbb{R}}$.

######  Proposition 5.4.

For any positive integer $n$, it holds that
$\chi_{n}\leq\chi^{\mathbb{R}}_{n}\leq 2\chi_{n}$.

###### Proof.

The first inequality is obvious, so it suffices to prove
$\chi^{\mathbb{R}}_{n}\leq 2\chi_{n}$. Since the tensors
$\sum_{\begin{subarray}{c}\lvert x\rvert=k\end{subarray}}\mathrm{e}_{x}$ for
$k\in[n]$ form a basis for $S^{n}(\mathbb{C}^{2})$, then by Proposition 5.3,
$\chi_{n}$ is the minimum number for which there exists a set of stabilizer
states
$\\{[\sigma_{1}],\dots,[\sigma_{\chi_{n}}]\\}\subseteq\mathrm{Stab}_{n}$ such
that

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathbb{F}_{2}^{n}\\\ \lvert
x\rvert=k\end{subarray}}\mathrm{e}_{x}\in\operatorname{span}\\{\sigma_{1},\dots,\sigma_{\chi_{n}}\\}$
(41)

for all $k\in\\{0,1,\dots,n\\}$. Without loss of generality, for each
$j\in[\chi_{n}]$ it holds that

$\displaystyle\sigma_{j}=\sum_{x\in
A_{j}}i^{l_{j}(x)}\cdot(-1)^{q_{j}(x)}\cdot\mathrm{e}_{x}$ (42)

for some affine linear subspace $A_{j}\subseteq\mathbb{F}_{2}^{n}$, linear
functional $l_{j}$, and quadratic form $q_{j}$ (see (4)). For each
$j\in[\chi_{n}]$, we define $\rho_{j}$ to be the tensor

$\displaystyle\rho_{j}=\sum_{x\in
A_{j}}(-1)^{q_{j}(x)+l_{j}(x)}\cdot\mathrm{e}_{x},$ (43)

and observe that for any real numbers $a,b\in\mathbb{R}$, it holds that

$\displaystyle\mathrm{Re}((a+ib)\sigma_{j})=(a-b)\mathrm{Re}({\sigma}_{j})+b\rho_{j},$
(44)

where $\mathrm{Re}(\cdot)$ is the real part with respect to the computational
basis. For each $k\in\\{0,1,\dots,n\\}$, there exist real numbers
$a_{1},\dots,a_{\chi_{n}},b_{1},\dots,b_{\chi_{n}}\in\mathbb{R}$ for which

$\displaystyle\sum_{\begin{subarray}{c}\lvert
x\rvert=k\end{subarray}}\mathrm{e}_{x}$
$\displaystyle=\sum_{j\in[\chi_{n}]}(a_{j}+ib_{j})\sigma_{i}$ (45)
$\displaystyle=\mathrm{Re}\left(\sum_{j\in[\chi_{n}]}(a_{j}+ib_{j})\sigma_{j}\right)$
(46)
$\displaystyle=\sum_{j\in[\chi_{n}]}\big{(}(a_{j}-b_{j})\mathrm{Re}({\sigma}_{j})+b\rho_{j}\big{)},$
(47)

where the first line follows from (41), the second follows from the fact that
the tensor is already real, and the third follows from (44). Hence,

$\displaystyle
S^{n}(\mathbb{C}^{2})\in\operatorname{span}_{\mathbb{C}}\\{\mathrm{Re}({\sigma}_{1}),\dots,\mathrm{Re}({\sigma}_{\chi_{n}}),\rho_{1},\dots,\rho_{\chi_{n}}\\}.$
(48)

Since $[\mathrm{Re}(\sigma_{j})]$ and $[\rho_{j}]$ are clearly real stabilizer
states for all $j\in[\chi_{n}]$, it follows that ${\chi_{n}^{\mathbb{R}}\leq
2\chi_{n}}$. ∎

Using similar techniques as in the proof of Proposition 5.3, it is
straightforward to show that $\chi([\psi])\leq\chi^{\mathbb{R}}([\psi])\leq
2\chi([\psi])$ for any real quantum state $[\psi]\in\mathbb{P}^{2^{n}-1}$.

The next proposition tells us that upper bounds on the stabilizer ranks
(respectively, real stabilizer ranks) of any set of $n+1$ states of the form
$[\psi^{\otimes n}]$ implies an upper bound on $\chi_{n}$ (resp.
$\chi_{n}^{\mathbb{R}}$).

######  Proposition 5.5.

Let $r$ be a positive integer. If there exists a set of $n+1$ distinct qubit
states $\\{[\psi_{1}],\dots,[\psi_{n+1}]\\}\subseteq\mathbb{P}^{1}$ with
$\chi([\psi_{i}^{\otimes n}])\leq r$ for all $i\in[n+1]$, then $\chi_{n}\leq
r(n+1)$. Similarly, if there exists a set of $n+1$ distinct qubit states
$\\{[\psi_{1}],\dots,[\psi_{n+1}]\\}\subseteq\mathbb{P}^{1}$ with
$\chi^{\mathbb{R}}([\psi_{i}^{\otimes n}])\leq r$ for all $i\in[n+1]$, then
$\chi_{n}^{\mathbb{R}}\leq r(n+1)$.

###### Proof.

We prove only the statement for $\chi_{n}$. Since $\chi([\psi_{i}^{\otimes
n}])\leq r$ for all $i\in[n+1]$, then by taking the span of the union of all
stabilizer states appearing in the decompositions of each $[\psi_{i}^{\otimes
n}]$, we have $\\{[\psi_{1}^{\otimes n}],\dots,[\psi_{n+1}^{\otimes
n}]\\}\subseteq\Sigma_{r(n+1)}(\mathrm{Stab}_{n})$. The proposition follows
from the fact that the affine cone over any set of $n+1$ distinct states of
this form spans $S^{n}(\mathbb{C}^{2})$, so
${\hat{\Sigma}_{r(n+1)}(\mathrm{Stab}_{n})\supseteq S^{2}(\mathbb{C}^{2})}$
(see [HK15, Proposition 3.1] or [LP21, Corollary 18]). ∎

We close this section by refining Fact 5.1 to give a quantitative upper bound
on the number of states of sub-generic rank.

######  Proposition 5.6.

There are at most

$\displaystyle n\binom{\lvert\mathrm{Stab}_{n}\rvert}{\chi_{n}-1}$ (49)

states $[\psi]\in\mathbb{P}^{1}$ for which $\chi([\psi^{\otimes
n}])<\chi_{n}$. Similarly, there are at most

$\displaystyle
n\binom{\bigl{\lvert}\mathrm{Stab}_{n}^{\mathbb{R}}\bigr{\rvert}}{\chi_{n}^{\mathbb{R}}-1}$
(50)

states $[\psi]\in\mathbb{P}^{1}$ for which $\chi^{\mathbb{R}}([\psi^{\otimes
n}])<\chi_{n}^{\mathbb{R}}$.

We have computed the quantities $\lvert\mathrm{Stab}_{n}\rvert$ and
$\bigl{\lvert}\mathrm{Stab}_{n}^{\mathbb{R}}\bigr{\rvert}$ at the end of
Section 2.

###### Proof.

We prove only the statement for $\chi_{n}$. Note that any set of $n+1$
distinct tensors in $\hat{\nu}_{1}(\mathbb{P}^{1})$ (i.e. tensors of the form
$\psi^{\otimes n}$) span $S^{n}(\mathbb{C}^{2})$ (see [HK15, Proposition 3.1]
or [LP21, Corollary 18]), so any set of $\chi_{n}-1$ linearly independent
stabilizer states can contain at most $n$ distinct elements of
$\hat{\nu}_{1}(\mathbb{P}^{1})$ in their span. Since there are at most

$\displaystyle\binom{\lvert\mathrm{Stab}_{n}\rvert}{\chi_{n}-1}$ (51)

distinct sets of $\chi_{n}-1$ linearly independent stabilizer states, the
bound follows. ∎

## References

  * [BBC+19] 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, 2019.
  * [BG16] Sergey Bravyi and David Gosset.  Improved classical simulation of quantum circuits dominated by Clifford gates.  Physical Review Letters, 116:250501, 2016.
  * [BK05] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal clifford gates and noisy ancillas.  Physical Review A, 71:022316, 2005.
  * [BMP+99] P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan.  On universal and fault-tolerant quantum computing: A novel basis and a new constructive proof of universality for Shor’s basis.  In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999.
  * [BSS16] Sergey Bravyi, Graeme Smith, and John A. Smolin.  Trading classical and quantum computational resources.  Physical Review X, 6:021043, 2016.
  * [DDM03] Jeroen Dehaene and Bart De Moor.  Clifford group, stabilizer states, and linear and quadratic operations over GF(2).  Physical Review A, 68:042318, 2003.
  * [Fel91] William Feller.  An Introduction to Probability Theory and Its Applications, volume 1.  John Wiley and Sons, third edition, 1991.
  * [Got97] Daniel Gottesman.  Stabilizer codes and quantum error correction.  PhD thesis, California Institute of Technology, 1997.
  * [Got98] Daniel Gottesman.  The Heisenberg representation of quantum computers.  In 22nd International Colloquium on Group Theoretical Methods in Physics, pages 32–43, 1998.
  * [GR70] Jay Goldman and Gian-Carlo Rota.  On the foundations of combinatorial theory IV: Finite vector spaces and Eulerian generating functions.  Technical report, Harvard University, 1970.
  * [Gro06] David Gross.  Hudson’s theorem for finite-dimensional quantum systems.  Journal of Mathematical Physics, 47(12):122107, 2006.
  * [Har13] Joe Harris.  Algebraic Geometry: A First Course.  Graduate Texts in Mathematics. Springer New York, 2013.
  * [HK15] Kil-Chan Ha and Seung-Hyeok Kye.  Multi-partite separable states with unique decompositions and construction of three qubit entanglement with positive partial transpose.  Journal of Physics A: Mathematical and Theoretical, 48(4):045303, 2015.
  * [Lan11] Joseph Landsberg.  Tensors: Geometry and applications.  volume 128 of Graduate Studies in Mathematics. AMS, 2011.
  * [LJ20] Benjamin Lovitz and Nathaniel Johnston.  Entangled subspaces and generic local state discrimination with pre-shared entanglement.  arXiv preprint, quant-ph/2010.02876, 2020.
  * [LM19] J. Landsberg and M. Michałek.  Towards finding hay in a haystack: explicit tensors of border rank greater than 2.02m in $\mathbb{C}^{m}\otimes\mathbb{C}^{m}\otimes\mathbb{C}^{m}$.  arXiv preprint, cs.CC/1912.11927, 2019.
  * [LP21] Benjamin Lovitz and Fedor Petrov.  A generalization of Kruskal’s theorem on tensor decomposition.  arXiv preprint, math.CO/2103.15633, 2021.
  * [Mou01] David Petrie Moulton.  Representing powers of numbers as subset sums of small sets.  Journal of Number Theory, 89(2):193–211, 2001.
  * [NC00] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2000.
  * [PSV21] Shir Peleg, Amir Shpilka, and Ben Lee Volk.  Lower bounds on stabilizer rank.  arXiv preprint, quant-ph/2106.03214, 2021.
  * [Qas21] Hammam Qassim.  Classical simulations of quantum systems using stabilizer decompositions.  PhD thesis, University of Waterloo, 2021.
  * [QPG21] Hammam Qassim, Hakop Pashayan, and David Gosset.  Improved upper bounds on the stabilizer rank of magic states.  arXiv preprint, quant-ph/2106.07740, 2021.
  * [Raz87] A. A. Razborov.  Lower bounds on the size of bounded depth circuits over a complete basis with logical addition.  Mathematical notes of the Academy of Sciences of the USSR, 41:333–338, 1987.
  * [Smo87] R. Smolensky.  Algebraic methods in the theory of lower bounds for boolean circuit complexity.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 77–82, 1987.
  * [Smo93] R. Smolensky.  On representations by low-degree polynomials.  In Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, pages 130–138, 1993.
  * [VdN10] Maarten Van den Nest.  Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond.  Quantum Information and Computation, 10(3):258–271, 2010.

##  Appendix A Motivation behind stabilizer rank

In this appendix we will motivate the definition of stabilizer rank in more
depth, and explain how it relates to the simulation cost of quantum circuits.
In particular, we will review how the stabilizer rank of a quantum state
quantifies the classical simulation cost of applying Clifford gates and
computational basis measurements to that state, and review how the stabilizer
rank of $n$ copies of the so-called $T$-state quantifies the simulation cost
of Clifford+$T$ circuits consisting of $n$ $T$-gates.

For this discussion, it will be more convenient to use affine notation instead
of the projective notation used in the main text. When we use the terms
unitary, Clifford unitary or Pauli unitary we will therefore always mean the
affine version defined in Section 2. Abusing terminology, we will refer to
unit tensors $v\in\mathcal{S}(\mathcal{V}_{k}),$ for a positive integer $k$,
as quantum states in this appendix. We use the standard graphical notation for
quantum circuits: We depict with

$\Qcircuit<EMAIL_ADDRESS>\lstick{\psi\;\Bigg{\\{}}\raisebox{4.0pt}{\vdots}\raisebox{4.0pt}{\vdots}\\\
\qw\ghost{U}\qw\meter}$ (52)

a circuit applying a $k$-qubit unitary $U$ to an input state
$\psi\in\mathcal{S}(\mathcal{V}_{k})$ and measuring the $k$ qubits in
computational basis.

Recall that simulating a quantum circuit in (52) with a $k$-qubit input state
$\psi$ weakly means to draw $k$ classical bits according to the output
distribution of the circuit. Simulating the circuit strongly on the other hand
means to be able to compute the probability of a bit string $x_{1}\dots x_{k}$
being the output of the circuit. By Born’s rule, this probability is given by
$p_{x_{1}\dots x_{k}}^{*}p_{x_{1}\dots x_{k}}$ where

$p_{x_{1}\dots
x_{k}}=\left(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*}\right)U\psi.$
(53)

Recall the (affine) Clifford gates $H,S$ and $CNOT$ defined in Section 2. We
will later also need the controlled $Z$ gate defined via

$CZ=(\mathds{1}_{2}\otimes H)CNOT(\mathds{1}_{2}\otimes
H)=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&-1\\\ \end{pmatrix}.$
(54)

The Clifford unitaries $U\in\mathrm{Cliff}_{k}$ are exactly those unitaries
composed from $H,S$ and $CNOT$ gates only. As done in Section 2, on can
equivalently define the group $\mathrm{Cliff}_{k}$ as the normalizer of the
$k$-qubit Pauli group $\mathrm{Pauli}_{k}$ (also defined in Section 2):
Conjugating a Pauli unitary with a Clifford unitary yields another Pauli
unitary [Got97].

As a consequence of this fact, we can work very efficiently on certain quantum
states using the stabilizer formalism, which was introduced in [Got97]. We
will now briefly recall some basics about the stabilizer formalism and refer
the reader to [NC00] for an in-depth discussion and detailed proofs. To start,
note that $\mathrm{e}_{0}^{\otimes k}$ is, up to global phase, the unique
quantum state invariant under applying (or stabilized by) $Z_{i}$ for all
$i\in[k]$, where $Z_{i}$ is the tensor product of a Pauli $Z$ on the $i$’th
qubit with identities on all other qubits. In fact, one can show that if
$P_{1},\dots,P_{k}$ are independent Pauli unitaries (that is, none of them is
a product of the others) and the group generated by them does not contain
$-\mathds{1}_{2}^{\otimes k}$ then there exists up to global phase a unique
state $\sigma$ stabilized by $P_{1},\dots,P_{k}$ (see [NC00, Chapter 10.5.1]
for details). It turns out that if a state $\sigma$ can be uniquely specified
as above, the same holds for the state resulting from applying a Clifford
unitary $U$ to $\sigma$: In fact, one can show that the Pauli unitaries
$UP_{1}U^{\dagger},\dots,UP_{k}U^{\dagger}$ are independent again, do not
generate $-\mathds{1}_{2}^{\otimes k}$ and it is easy to see that they
stabilize $U\sigma$ (see [NC00, Chapter 10.5.2] for details). Conversely, for
every state of the form $U\mathrm{e}_{0}^{\otimes k}$, there are $k$
independent Paulis stabilizing it, see [Gro06] for a proof. Summarizing, we
see that the states of the form $\sigma=U\mathrm{e}_{0}^{\otimes k}$ for a
Clifford unitary $U$ are exactly the ones uniquely specified up to global
phase by $k$ independent Pauli operators stabilizing it. This explains why we
defined a stabilizer state as a state of the form $[U\mathrm{e}_{0}^{\otimes
k}]$ where $U$ is a Clifford unitary in Section 2. Abusing terminology, we
will call the unit tensor $U\mathrm{e}_{0}^{\otimes
k}\in\mathcal{S}(\mathcal{V}_{k})$, for a Clifford unitary $U$, a stabilizer
state in this Appendix.

The celebrated Gottesman-Knill theorem states that a circuit as in (52) where
$U$ is a Clifford unitary can be simulated efficiently if the input state is a
stabilizer state ${\sigma\in\mathcal{S}(\mathcal{V}_{k})}$.

######  Theorem A.1 (Gottesman, Knill [Got98]).

Let $\sigma$ be a $k$-qubit stabilizer state specified by $k$ independent
Paulis that stabilize it. A quantum circuit $U$ composed only from Clifford
gates acting on $\sigma$ followed by measurements in the computational basis
can be efficiently simulated both strongly and weakly. More precisely, the
complexity of simulating the quantum computation scales quadratically in the
number of qubits and linearly in the number of Clifford gates and measurements
that are applied.

A proof of Theorem A.1 can be found in [NC00, Section 10.5.4]. We mention that
one essentially has to update the Pauli stabilizers gate-by-gate, which yields
$k$ independent Paulis stabilizing $U\sigma$. One can read in detail in [NC00,
Section 10.5.3] how one can then efficiently obtain the outcome probabilities
from this.

Note that if a quantum state $\sigma\in\mathcal{S}(\mathcal{V}_{k})$ is
stabilized by a Pauli unitary $P$, all states of the form $e^{i\theta}\sigma$
for $\theta\in\mathbb{R}$ are also stabilized by $P$. While a global phase
does not influence the outcome probabilities of computational basis
measurements, it changes the amplitudes of the state. This means that Theorem
A.1 as stated above does not let us calculate amplitudes but only outcome
probabilities. In [BBC+19], the authors describe a way of keeping track of the
global phase: They define a classical data format for stabilizer states which
they call the $CH$-form. We now briefly describe their approach and refer to
[BBC+19] for more details. Another in-depth discussion can be found in [Qas21,
Section 2.1.4] from where we also borrow our notation. Essentially, one can
show that every stabilizer state $\sigma$ is of the form

$\sigma=wUH(h)(\mathrm{e}_{s_{1}}\otimes\dots\otimes\mathrm{e}_{s_{k}})$ (55)

where $w\in\mathbb{C}$, $s,h\in\mathbb{F}_{2}^{k}$ and $U$ is a Clifford
unitary composed from gates $CNOT,CZ$ and $S$ only. The unitary $H(h)$ is a
tensor product of $H$ gates acting on the qubits $i$ such that $h_{i}=1$ and
$\mathds{1}_{2}$ elsewhere. As in the proof of Theorem A.1, one can now
simulate a circuit built from Clifford gates only by updating $w,U,h$ and $s$
gate-by-gate. The authors show in [BBC+19] that this update can be done with
computational cost at most quadratic in $k$. Moreover, they show that given a
stabilizer state $\sigma\in\mathcal{S}(\mathcal{V}_{k})$ in $CH$-form, one can
calculate the amplitude
$(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*})\sigma$ with
computational cost quadratic in the number of qubits. Summarizing, we can
calculate the amplitude of $U\sigma$ with computational cost quadratic in the
number of qubits and linear in the number of Clifford gates of which $U$ is
composed.

With that, we can now understand the importance of the stabilizer rank as a
measure of the computational cost of a certain method to simulate quantum
circuits. For simplicity, we discuss only the connection to strong simulation
of quantum circuits with general input states. For a discussion of a weak
simulation protocol see [BBC+19, Section 4]. Say, we want to strongly simulate
a quantum circuit as in (52) where $\psi$ is a $k$-qubit quantum state and $U$
is a Clifford unitary. Say furthermore that we can decompose

$\psi=\sum_{i=1}^{r}c_{i}\sigma_{i}$ (56)

where the $\sigma_{i}$ are stabilizer states each specified in $CH$-form and
the $c_{i}$ are complex numbers. Given a bit string $x_{1}\dots x_{k}$, we can
efficiently calculate
$(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*})U\sigma_{i}$
by first updating the $CH$-form and then calculating the amplitude. By
linearity, we can therefore calculate

$p_{x_{1}\dots
x_{k}}=\left(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*}\right)U\psi=\sum_{i=1}^{r}c_{i}\left(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*}\right)U\sigma_{i},$
(57)

and therefore calculate the probability $p_{x_{1}\dots x_{k}}^{*}p_{x_{1}\dots
x_{k}}$ of outcome $x_{1}\dots x_{k}$, with computational cost linear in the
length of the stabilizer decomposition. Since for every summand, the
computational cost is linear in the number of gates of which $U$ is composed
and quadratic in the number of qubits, the whole cost is quadratic in the
number of qubits, linear in the number of Clifford gates applied and linear in
the number of terms $r$ appearing in the stabilizer decomposition.

As already done in Section 2, we call the minimal $r$ such that there exists a
decomposition as in equation (56) the stabilizer rank of $\psi$ and denote it
$\chi(\psi)$ (note that we again abuse terminology by using the term
stabilizer rank in the affine context). It follows that lower bounds on
$\chi(\psi)$ imply lower bounds on the complexity of simulating a circuit of
the form (52) using the approach we have just described. On the other hand,
finding upper bounds on $\chi(\psi)$ by providing a decomposition as in (56)
can give us better simulation algorithms for circuits of the form (52).

As an application, we will now see how low-rank stabilizer decompositions of
$n$ copies of the so-called $T$-state can also be used to simulate circuits
built from a universal gate set. This strategy has been used for instance in
[BG16]. Recall that a gate set $\mathcal{G}$ is called universal if every
unitary $U$ on $k$ qubits can be approximated arbitrarily well by unitaries
$U_{\mathcal{G}}$ composed solely of gates in $\mathcal{G}$. It is well-known
that the set of Clifford gates is not universal but, together with the so-
called $T$-gate

$T=\begin{pmatrix}1&0\\\ 0&e^{i\frac{\pi}{4}}\end{pmatrix},$ (58)

they form a universal gate set [BMP+99].

Under the assumption that our quantum device can only prepare a computational
basis state $\mathrm{e}_{0}^{\otimes k}$, apply Clifford$+T$ operations and
measure the qubits in computational basis, the $T$-gates appear, by the
preceeding discussion, to be responsible for the potential superiority of the
quantum device. It is therefore an interesting question how efficiently we can
simulate a quantum computation on $k$ qubits which, in addition to Clifford
gates, uses $n$ single-qubit $T$-gates.

A standard way of approaching this question is via the study of magic state
injection [BK05]. For this, we note that for the magic state
$T=\frac{1}{\sqrt{2}}\left(\mathrm{e}_{0}+e^{i\frac{\pi}{4}}\mathrm{e}_{1}\right)$,
applying a $T$-gate to any qubit state $\psi$ is the same as applying the
circuit

$\Qcircuit<EMAIL_ADDRESS>\lstick{T}\qw\targ\qw\meter\cw\controlo\cw\cwx\gategroup{1}{5}{2}{14}{1.3em}{--}}$
(59)

where the double wire denotes a classical control: The $S$ gate on the first
system is applied if and only if the outcome of the computational basis
measurement on the second system is 1. Therefore, any $k$-qubit quantum
circuit

$\Qcircuit<EMAIL_ADDRESS>\lstick{\mathrm{e}_{0}^{\otimes
k\;}\Bigg{\\{}}\raisebox{4.0pt}{\vdots}\raisebox{4.0pt}{\vdots}\\\
\qw\ghost{V}\qw\meter}$ (60)

where $V$ is composed of Clifford gates and $n$ $T$-gates, can be implemented
with a circuit composed from Clifford gates and classical controls acting on
the state $\mathrm{e}_{0}^{\otimes k}\otimes T^{\otimes n}$ by replacing each
$T$-gate with the gadget in (59). By postselecting outcomes $0$ for each
measurement on a $T$-state in this circuit, we see that

$V\mathrm{e}_{0}^{\otimes k}={2^{n/2}}\left(\mathds{1}^{\otimes
k}\otimes(\mathrm{e}_{0}^{*})^{\otimes n}\right)U\left(e_{0}^{\otimes
k}\otimes T^{\otimes n}\right)$ (61)

where $U$ is composed from Clifford gates only (more precisely, the Clifford
gates from $V$ plus an additional $CNOT$ gate for each injected $T$-state).

With that, it follows that the probability of outcome $x_{1}\dots x_{k}$ in
the circuit in (60) is given by $p_{x_{1}\dots x_{k}}^{*}p_{x_{1}\dots x_{k}}$
where

$\displaystyle p_{x_{1}\dots x_{k}}$
$\displaystyle=\left(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*}\right)V\mathrm{e}_{0}^{\otimes
k}$ (62)
$\displaystyle={2^{n/2}}\left(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*}\otimes(\mathrm{e}_{0}^{*})^{\otimes
n}\right)U\left((\mathrm{e}_{0})^{\otimes k}\otimes T^{\otimes n}\right).$
(63)

Note that if there are stabilizer states $\sigma_{1},\dots,\sigma_{r}$ and
complex numbers $c_{1},\dots,c_{r}\in\mathbb{C}$ such that
$\psi=\sum_{i=1}^{r}c_{i}\sigma_{i}$, then the quantity in (63) decomposes by
linearity as

$p_{x_{1}\dots
x_{k}}=2^{n/2}\sum_{i=1}^{r}c_{i}\left(\mathrm{e}_{x_{1}}^{*}\otimes\dots\otimes\mathrm{e}_{x_{k}}^{*}\otimes(\mathrm{e}_{0}^{*})^{\otimes
n}\right)U\left((\mathrm{e}_{0})^{\otimes k}\otimes\sigma_{i}\right).$ (64)

All summands in (64) can be calculated efficiently using the $CH$-form as
discussed before: They are amplitudes of the outcome of a quantum circuit
composed of Clifford gates acting on a stabilizer state.

Summarizing, every stabilizer decomposition of $T^{\otimes n}$ yields a way to
strongly simulate Clifford+$T$ circuits consisting of $n$ $T$-gates. The
complexity of this simulation scales linearly in the number of terms appearing
in the stabilizer decomposition and polynomially in all other parameters. With
this, it follows that finding decompositions of $T^{\otimes n}$ into few
stabilizer states can reduce the complexity of simulating such circuits. Lower
bounds on $\chi(T^{\otimes n})$, on the other hand, translate directly into
lower bounds on the cost of simulating quantum circuits using these methods,
namely, stabilizer decompositions and $CH$-forms.