# Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Sabee Grewal The University of Texas at Austin. {sabee,
<EMAIL_ADDRESS>{vishnu.iyer<EMAIL_ADDRESS>Vishnu
Iyer11footnotemark: 1 William Kretschmer11footnotemark: 1 Daniel
Liang11footnotemark: 1

###### Abstract

We show that quantum states with “low stabilizer complexity” can be
efficiently distinguished from Haar-random. Specifically, given an $n$-qubit
pure state $\ket{\psi}$, we give an efficient algorithm that distinguishes
whether $\ket{\psi}$ is (i) Haar-random or (ii) a state with stabilizer
fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$
with some stabilizer state), promised that one of these is the case. With
black-box access to $\ket{\psi}$, our algorithm uses
$O\\!\left(k^{12}\log(1/\delta)\right)$ copies of $\ket{\psi}$ and
$O\\!\left(nk^{12}\log(1/\delta)\right)$ time to succeed with probability at
least $1-\delta$, and, with access to a state preparation unitary for
$\ket{\psi}$ (and its inverse), $O\\!\left(k^{3}\log(1/\delta)\right)$ queries
and $O\\!\left(nk^{3}\log(1/\delta)\right)$ time suffice.

As a corollary, we prove that $\omega(\log(n))$ $T$-gates are necessary for
any Clifford+$T$ circuit to prepare computationally pseudorandom quantum
states, a first-of-its-kind lower bound.

##  1 Introduction

The stabilizer formalism [gottesman1997stabilizer] plays a central role in
quantum information. Stabilizer states are states that lie in the intersection
of the positive eigenspaces of $2^{n}$ commuting Pauli operators. Stabilizer
states can be generated by Clifford circuits, which are the group of unitary
transformations that normalize the Pauli group. Stabilizer states and the
Clifford group have widespread applications in quantum error correction
[shor1995codes, calderbank1996codes], measurement-based quantum computation
[raussendorf2000mbqc], randomized benchmarking [knill2008benchmarking], and
quantum learning algorithms [huangkuengpresskill]. These applications are
largely thanks to the rich algebraic structure afforded by the stabilizer
formalism.

Stabilizer states are also one of the few classes of states that admit
efficient learning algorithms. Montanaro [montanaro2017learning] gave an
algorithm that takes $O(n)$ copies of an $n$-qubit stabilizer state and
correctly identifies the state with high probability in time $O(n^{3})$.
Gross, Nezami, and Walter [gross2021schur] gave an algorithm for property
testing stabilizer states, which is the task of distinguishing whether a state
is a stabilizer state or is far from any stabilizer state. Remarkably, this
algorithm requires only $6$ copes of the state.

Despite finding numerous applications, Clifford circuits are not universal for
quantum computation. Furthermore, in 1998, Gottesman and Knill showed that
Clifford circuits acting on stabilizer states can be efficiently classically
simulated [gottesman1998heisenberg, aaronson2004stabilizer]. However, with the
additional ability to apply a $T$-gate (the gate
$\ket{0}\\!\\!\bra{0}+e^{i\pi/4}\ket{1}\\!\\!\bra{1}$), the resulting gate set
becomes universal. Therefore, efficient simulation of so-called Clifford+$T$
circuits would imply $\BPP=\BQP$, and a large line of work has been devoted to
developing better simulation algorithms [PashayanPhysRevLett.115.070501,
BrayviPhysRevLett.116.250501, RallPhysRevA.99.062337,
Bravyi2019simulationofquantum].

Currently, the best-performing simulation algorithms are based on modeling the
output state of a quantum circuit as a decomposition of stabilizer states
[Bravyi2019simulationofquantum]. These decompositions give rise to simulation
algorithms whose runtimes scale polynomially in the complexity of the
decomposition. One such complexity measure is the stabilizer extent. Consider
the state $\ket{\psi}=\sum_{i}c_{i}\ket{\phi_{i}}$ for $c_{i}\in\mathbb{C}$
and stabilizer states $\ket{\phi_{i}}$. The stabilizer extent is the minimum
$\left(\sum_{i}{\lvert c_{i}\rvert}\right)^{2}$ over all such decompositions
of $\ket{\psi}$, and scales exponentially in the number of $T$-gates in the
circuit producing the state. A closely-related complexity measure is the
stabilizer fidelity, which is the maximum overlap between $\ket{\psi}$ and any
stabilizer state. Indeed, the inverse of stabilizer fidelity lower bounds
stabilizer extent [Bravyi2019simulationofquantum]. Collectively, we informally
refer to states with either low stabilizer extent or non-negligible stabilizer
fidelity as states of low “stabilizer complexity”.

As a generalization of stabilizer states, it is natural to ask whether states
of low stabilizer complexity are also efficiently learnable, and indeed a
similar question has been raised before [arunachalam2022phase]. Nevertheless,
this problem remains largely open except in some highly restricted settings
[lai2022learning]. This could be in part because many of the useful properties
of stabilizer states provably fail to generalize to states with low stabilizer
complexity. For example, [hinsche2022learning] observed that one can
efficiently learn the output distribution of any Clifford circuit, given
samples from this distribution.111Indeed, every such distribution is simply an
affine subspace of $\mathbb{F}_{2}^{n}$. However, this task already becomes
intractable for circuits with a single $T$-gate (producing a state of constant
stabilizer extent), where [hinsche2022learning] proved that learning the
output distribution is as hard as the learning parities with noise problem.

Furthermore, it is known that stabilizer states form a $t$-design for $t=3$,
meaning that random stabilizer states duplicate the first 3 moments of the
Haar measure [kuenghttps://doi.org/10.48550/arxiv.1510.02767,
webb2016clifford]. By contrast, [haferkamp2020homeopathy] showed that circuits
with $\poly(t)$ non-Clifford gates are sufficient to generate approximate
$t$-designs. Thus, for any constant $t$, states of constant stabilizer extent
can form approximate $t$-designs. This suggests that states of low stabilizer
complexity can give much stronger information-theoretic approximations to the
Haar measure than ordinary stabilizer states, because stabilizer states fail
to form a $t$-design for any $t>3$ [ZKGG16].

In this work, we investigate whether these properties that differentiate
stabilizer states from low-stabilizer-complexity states can be pushed further,
to prove hardness of learning low-stabilizer-complexity states. One natural
approach towards proving that low-stabilizer-complexity states are hard to
learn would be to show that they are pseudorandom. Ji, Liu, and Song
[Ji10.1007/978-3-319-96878-0_5] define an ensemble of $n$-qubit states to be
(computationally) pseudorandom if every $\poly(n)$-time quantum adversary has
at most a negligible advantage in distinguishing copies of a state drawn
randomly from the ensemble from copies of a Haar-random $n$-qubit state. Note
that pseudorandom states are not efficiently learnable, as any algorithm for
learning some set of quantum states gives an algorithm to distinguish those
states from the Haar measure.

Our main result is an efficient algorithm for distinguishing states of non-
negligible stabilizer fidelity from Haar-random states, showing that such
states cannot be pseudorandom. This type of distinguishing is sometimes known
as weak learning in learning theory.

######  Theorem 1.1 (Informal version of Theorem 4.1).

Let $\ket{\psi}$ be an unknown $n$-qubit pure state, and let
$k\leq\frac{4}{5}2^{n/12}$. There is an efficient algorithm that distinguishes
whether $\ket{\psi}$ is Haar-random or a state with stabilizer fidelity at
least $\frac{1}{k}$, promised that one of these is the case. In particular,
the algorithm uses $O(k^{12}\log(1/\delta))$ copies of $\ket{\psi}$ and
$O(nk^{12}\log(1/\delta))$ time to succeed with probability at least
$1-\delta$.

Theorem 1.1 also generalizes to distinguishing states with low stabilizer
extent from Haar-random. To the best of our knowledge, prior to our work, it
was even unknown whether states of stabilizer extent at most a constant could
be efficiently distinguished from Haar-random. We also emphasize that the
contrast between our positive learning result and the hardness result of
[hinsche2022learning] stems in part from the differing access models: we
assume access to copies of the quantum state, whereas [hinsche2022learning]
considers algorithms that only have outcomes of standard basis measurements of
the state.

As a simple corollary, we prove a first-of-its-kind lower bound on the number
of $T$-gates required to prepare computationally pseudorandom quantum states.

######  Corollary 1.2 (Corollary 4.3).

Any family of Clifford+$T$ circuits that produces an ensemble of $n$-qubit
computationally pseudorandom quantum states must use at least $\omega(\log n)$
$T$-gates.

In some sense, Corollary 1.2 contrasts sharply with the result of
[haferkamp2020homeopathy], where circuits containing just a few non-Clifford
gates are sufficient to produce strong information-theoretic approximations to
the Haar measure (i.e. $t$-designs). Nevertheless, we emphasize that our
result and [haferkamp2020homeopathy] are formally incomparable, because
computationally pseudorandom states need not form approximate $t$-designs for
constant $t$, nor vice-versa.

###  1.1 Main Ideas

Let $x=(p,q)\in\mathbb{F}_{2}^{2n}$, where $p$ and $q$ are the first and last
$n$ bits of $x$, respectively. Define $W_{x}\coloneqq i^{p\cdot q}X^{p}Z^{q}$
(a Pauli operator without phase), and let $\ket{\Phi^{+}}\coloneqq
2^{-n/2}\sum_{x\in\mathbb{F}_{2}^{n}}\ket{x,x}$ be a maximimally entangled
state. Then, the set $\\{\ket{W_{x}}\coloneqq(W_{x}\otimes
I)\ket{\Phi^{+}}\mid x\in\mathbb{F}_{2}^{2n}\\}$ is the Bell basis, an
orthonormal basis of $\mathbb{C}^{2^{n}}\otimes\mathbb{C}^{2^{n}}$.

Our algorithm uses Bell difference sampling [montanaro2017learning,
gross2021schur], which works as follows (see Section 2.3 for more detail):
Given four copies of an $n$-qubit pure state $\ket{\psi}$, perform a Bell-
basis measurement on $\ket{\psi}^{\otimes 2}$ to get measurement outcome
$x\in\mathbb{F}_{2}^{2n}$, repeat this on the remaining two copies to get
measurement outcome $y\in\mathbb{F}_{2}^{2n}$, and return $z=x+y$.

We refer to $p_{\psi}(x)\coloneqq
2^{-n}\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}$ as the characteristic
distribution of $\ket{\psi}$. To see that $p_{\psi}$ is a distribution, recall
that since the Pauli operators form an orthonormal basis over Hermitian
matrices, we can always decompose
$\ket{\psi}\\!\\!\bra{\psi}=\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2}^{n}}\braket{\psi}{W_{x}}{\psi}\cdot
W_{x}$. By assumption, $\lvert\braket{\psi}{\psi}\rvert^{2}=1$, so by
Parseval’s identity,

$\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2}^{n}}\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}=1.$

Gross, Nezami, and Walter [gross2021schur] showed that Bell difference
sampling an arbitrary pure state $\ket{\psi}$ corresponds to sampling a random
operator $W_{x}$ according to the following distribution:

$q_{\psi}(x)=\\!\\!\\!\sum_{y\in\mathbb{F}_{2}^{2n}}p_{\psi}(y)p_{\psi}(x+y).$

We call $q_{\psi}$ the Weyl distribution of $\ket{\psi}$. Note that the Weyl
distribution of $\ket{\psi}$ is the scaled convolution of the characteristic
distribution with itself (i.e., $q_{\psi}=4^{n}(p_{\psi}\ast p_{\psi})$, where
‘$\ast$’ is the convolution operator).

Define the $\\{\pm 1\\}$-outcome measurement $M_{x}\coloneqq\left\\{\frac{I\pm
W_{x}}{2}\right\\}$ (projections onto the $\pm 1$-eigenspaces of $W_{x}$). Our
algorithm begins by repeating the following process $m$ times: sample a random
Weyl operator $W_{x}$ (via Bell difference sampling) and perform the
measurement $M_{x}^{\otimes 2}$ on $\ket{\psi^{\otimes 2}}$. Then, average all
of the measurement outcomes. If the average is at least $1/\poly(k)$, we
decide that $\ket{\psi}$ has stabilizer fidelity at least $\frac{1}{k}$.
Otherwise, we decide that $\ket{\psi}$ is Haar-random.

What statistic are we computing in our algorithm? Denote the measurement
outcome on the $i$th iteration as $X_{i}\in\\{\pm 1\\}$. Observe that for all
$X_{i}$,

$\mathop{\bf
E\/}_{{\begin{subarray}{c}\end{subarray}}}[X_{i}]=\\!\\!\\!\sum_{x\in\mathbb{F}_{2}^{2n}}q_{\psi}(x)\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}=2^{n}\\!\\!\\!\sum_{x\in\mathbb{F}_{2}^{2n}}q_{\psi}(x)p_{\psi}(x)=2^{n}\mathop{\bf
E\/}_{{\begin{subarray}{c}x\sim q_{\psi}\end{subarray}}}[p_{\psi}(x)],$

where the expectation $\mathop{\bf E\/}[X_{i}]$ is taken over sampling $x\sim
q_{\psi}$ and the randomness from performing the measurement $M_{x}^{\otimes
2}$. Hence, for our algorithm to work, $\mathop{\bf
E\/}_{{\begin{subarray}{c}x\sim q_{\psi}\end{subarray}}}[p_{\psi}(x)]$ must be
“different enough” when $\ket{\psi}$ either is Haar-random or has low
stabilizer complexity. Proving that this is the case is the main technical
ingredient of our work:

######  Lemma 1.3 (Informal version of Lemma 3.1).

Let $\ket{\psi}$ be an $n$-qubit pure state. Suppose the stabilizer fidelity
of $\ket{\psi}$ is at least $\frac{1}{k}$. Then,

$2^{n}\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[p_{\psi}(x)\right]\geq\dfrac{1}{k^{6}}.$

In contrast, suppose $\ket{\psi}$ is a Haar-random quantum state. Then, with
overwhelming probability over the Haar measure,

$2^{n}\mathop{\bf E\/}_{x\sim q_{\psi}}\left[p_{\psi}(x)\right]\leq 2^{-n/2}.$

Our proof uses Fourier analysis of Boolean functions, and some parts of our
proof are reminiscent of the celebrated Blum-Luby-Rubinfield linearity test
[BLRtest]. Intuitively, $q_{\psi}$ is significantly closer to linear when
$\ket{\psi}$ has non-negligible stabilizer fidelity, as opposed to when
$\ket{\psi}$ is a Haar-random state.

With the above lemma, all that remains is “merely” a sample complexity
analysis, namely: what $m$ is sufficient to distinguish whether the average is
close to $0$ or $\Omega(1/k^{6})$? In the simplest case, we show that
$O(k^{12}\log(1/\delta))$ samples are sufficient by Hoeffding’s inequality.
However, this complexity can be improved if given access to a unitary that
prepares $\ket{\psi}$ (and its inverse). In this model, we are able to achieve
a quartic speedup in both sample and time complexity, which we explain in
Appendix A.

##  2 Preliminaries

First, we establish some notation used throughout this work. We denote
$[n]\coloneqq\\{1,\ldots,n\\}$. For $v\in\mathbb{C}^{n}$, $\lVert
v\rVert_{p}\coloneqq(\sum_{i\in[n]}\lvert v_{i}\rvert^{p})^{1/p}$ is the
$\ell_{p}$-norm. Logarithms are assumed to be in base $2$. For a probability
distribution $P$ on a set $S$, we denote drawing a sample $s\in S$ according
to $P$ by $s\sim P$. We denote drawing a sample $s\in S$ uniformly at random
by $s\sim S$.

###  2.1 Stabilizer States and Stabilizer Complexity Measures

We define the $1$-qubit Pauli group to be the collection of matrices
$\\{I,X,Y,Z\\}$, where

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

The $n$-qubit Pauli group $\mathcal{P}_{n}$ is the set $\\{\pm 1,\pm
i\\}\times\\{I,X,Y,Z\\}^{\otimes n}$. The Clifford group $\mathcal{C}_{n}$ is
the group of unitary transformations generated by $H$, $S$, and
$\mathrm{CNOT}$ gates, where $H$ is the Hadamard gate,
$S\coloneqq\ket{0}\\!\\!\bra{0}+i\ket{1}\\!\\!\bra{1}$ is the phase gate, and
$\mathrm{CNOT}$ is the controlled-not gate. We refer to unitary
transformations in the Clifford group as Clifford circuits. Clifford circuits
with the addition of the $T$-gate are universal, where the $T$-gate is defined
by $T\coloneqq\ket{0}\\!\\!\bra{0}+e^{i\pi/4}\ket{1}\\!\\!\bra{1}$.

A unitary transformation $U$ stabilizes a state $\ket{\psi}$ when
$U\ket{\psi}=\ket{\psi}$. It is folklore that if an $n$-qubit state can be
reached from the $\ket{0^{n}}$ state by applying a Clifford circuit, then the
state is stabilized by a group of $2^{n}$ commuting members of the subset
$\\{\pm 1\\}\times\\{I,X,Y,Z\\}^{\otimes
n}\subset\left(\mathcal{P}_{n}\setminus-I^{\otimes n}\right)$, called its
stabilizer group. Such states are called stabilizer states, and we denote the
set of stabilizer states by $\mathcal{S}_{n}$. For
$\ket{\psi}\in\mathcal{S}_{n}$, we denote its stabilizer group as
$\textrm{Stab}(\ket{\psi})$. For more background on stabilizer states, see,
e.g., [nielsen2002quantum].

We now define some complexity measures that characterize more general states
in terms of stabilizer state decompositions.

######  Definition 2.1 (stabilizer extent [Bravyi2019simulationofquantum]).

Suppose $\ket{\psi}$ is a pure $n$-qubit state. The _stabilizer extent_ of
$\ket{\psi}$, denoted $(\ket{\psi})$, is the minimum of $\lVert
c\rVert_{1}^{2}$ over all decompositions
$\ket{\psi}=\sum_{i}c_{i}\ket{\phi_{i}}$, where
$\ket{\phi_{i}}\in\mathcal{S}_{n}$ and $c$ is some vector in
$\mathbb{C}^{|\mathcal{S}_{n}|}$.

######  Definition 2.2 (stabilizer fidelity [Bravyi2019simulationofquantum]).

Suppose $\ket{\psi}$ is a pure $n$-qubit state. The _stabilizer fidelity_ of
$\ket{\psi}$, denoted $F_{\mathcal{S}}$, is

$F_{\mathcal{S}}(\ket{\psi})\coloneqq\max_{\ket{\phi}\in\mathcal{S}_{n}}\left|\braket{\phi}{\psi}\right|^{2}.$

Below we give a useful relation between the complexity measures defined above.

######  Claim 2.3.

Let $\ket{\psi}$ be an $n$-qubit pure state. Then,

$\xi(\ket{\psi})\geq\frac{1}{F_{\mathcal{S}}(\ket{\psi})}.$

###### Proof.

Let $\ket{\psi}=\sum_{\ket{\phi}\in\mathcal{S}_{n}}c_{\phi}\ket{\phi}$ be such
that $\left(\sum_{\phi}\lvert c_{\phi}\rvert\right)^{2}=\xi(\ket{\psi})$.
Suppose towards a contradiction that
$F_{\mathcal{S}}(\ket{\psi})<\frac{1}{\xi(\ket{\psi})}$ and therefore
$\lvert\braket{\phi}{\psi}\rvert<\frac{1}{\xi(\ket{\psi})}$ for all
$\ket{\phi}\in\mathcal{S}_{n}$. Then,

$\displaystyle
1=\lvert\braket{\psi}{\psi}\rvert=\left|\sum_{\ket{\phi_{S}}\in\mathcal{S}_{n}}c_{\phi}^{\ast}\braket{\phi}{\psi}\right|$
$\displaystyle\leq\sum_{\ket{\phi_{S}}\in\mathcal{S}_{n}}\left|c_{\phi}\right|\left|\braket{\phi}{\psi}\right|$
$\displaystyle\leq\max_{i}\lvert\braket{\phi_{i}}{\psi}\rvert\sum_{\ket{\phi_{S}}\in\mathcal{S}_{n}}\left|c_{\phi}\right|$
$\displaystyle\leq F_{\mathcal{S}}(\ket{\psi})\sqrt{\xi(\ket{\psi})}$
$\displaystyle<\sqrt{F_{\mathcal{S}}(\ket{\psi})}\leq 1$

The last line follows from the fact that $F_{\mathcal{S}}(\ket{\psi})\leq 1$
due to Cauchy-Schwarz and the definition of stabilizer fidelity. We then have
$1<1$ as a clear contradiction. ∎

The claim above also follows as a special case of
[Bravyi2019simulationofquantum, Theorem 4], though its proof is more
complicated.

To prove lower bounds on the number of $T$-gates necessary to prepare
pseudorandom quantum states, we need to upper bound the stabilizer extent of a
quantum state prepared by a Clifford+$T$ circuit comprised of $t$ $T$-gates.

######  Claim 2.4.

For $\ket{\psi}=\alpha\ket{v}+\beta\ket{w}$,

$\xi(\ket{\psi})\leq\left(\lvert\alpha\rvert\sqrt{\xi(\ket{v})}+\lvert\beta\rvert\sqrt{\xi(\ket{w})}\right)^{2}.$

###### Proof.

Let $\ket{v}=\sum_{i}c_{i}\ket{\phi_{i}}$ and
$\ket{w}=\sum_{j}d_{j}\ket{\varphi_{j}}$ be the minimal decompositions in
terms of stabilizer extent (i.e., $\left(\sum_{i}\lvert
c_{i}\rvert\right)^{2}=\xi(\ket{v})$). Since
$\ket{\psi}=\alpha\ket{v}+\beta\ket{w}=\alpha\sum_{i}c\ket{\phi_{i}}+\beta\sum_{j}d\ket{\varphi_{j}}$,
we have a stabilizer decomposition of $\ket{\psi}$. The stabilizer extent of
this decomposition is at most

$\left(\sum_{i}\lvert\alpha c_{i}+\beta
d_{i}\rvert\right)^{2}\leq\left(\lvert\alpha\rvert\sum_{i}\lvert
c_{i}\rvert+\lvert\beta\rvert\sum_{i}\lvert
d_{i}\rvert\right)^{2}\leq\left(\lvert\alpha\rvert\sqrt{\xi(v)}+\lvert\beta\rvert\sqrt{\xi(w)}\right)^{2}.\qed$

######  Lemma 2.5.

Let $C$ be any Clifford+$T$ circuit comprised of $t$ $T$-gates and
$\ket{\psi}=C\ket{0^{n}}$. Then,

$\xi(\ket{\psi})\leq\left(1+\frac{1}{\sqrt{2}}\right)^{t}.$

###### Proof.

We note that a Clifford+$T$ circuit can be broken into layers of Clifford
circuits, followed by a single $T$-gate, followed by more layers of Clifford
circuits, and so on. Since Clifford circuits preserve stabilizer extent, we
only need to show that the $T$-gate increases the stabilizer extent of any
state by at most a constant multiplicative factor. Since the SWAP gate is a
Clifford operation, we assume without loss of generality that each $T$-gate is
applied to the first qubit.

We proceed by induction on the layers of the circuit. In the first layer, when
no $T$-gates have been applied, the bound is trivially true because the
stabilizer extent of any stabilizer state is $1$. Now, assume that, after
applying some portion of the circuit $C^{\prime}$ to $\ket{0^{n}}$ with $t-1$
$T$-gates, we get the state $\ket{\varphi}$. Observe that the $T$-gate can be
expressed as $\cos(\pi/8)e^{i\pi/8}I+\sin(\pi/8)e^{i13\pi/8}Z$. Thus,
$(T\otimes I^{\otimes
n-1})\ket{\varphi}=\cos(\pi/8)e^{i\pi/8}\ket{\varphi}+\sin(\pi/8)e^{i13\pi/8}\left(Z\otimes
I^{\otimes n-1}\right)\ket{\varphi}$. Since $Z\otimes I^{\otimes n-1}$ is a
Clifford operation, $\left(Z\otimes I^{\otimes n-1}\right)\ket{\varphi}$ has
the same extent as $\ket{\varphi}$. Therefore, applying 2.4,

$\xi(\ket{\psi})\leq\left(\cos(\pi/8)+\sin(\pi/8)\right)^{2}\xi(\ket{\varphi})\leq\left(1+\frac{1}{\sqrt{2}}\right)^{t}.\qed$

###  2.2 Boolean Fourier Analysis

We review the basics of Fourier analysis over the Boolean hypercube.

######  Definition 2.6.

Let $S\subseteq[n]$ be an index of bits. Then the _parity function_ on $S$ is
defined to be

$\chi_{S}(x)\coloneqq\prod_{i\in S}(-1)^{x_{i}}.$

Alternatively, we can define $\chi_{S}(x)=(-1)^{x\cdot s}$ where $s_{i}=1$ if
and only if $i\in S$. This form will prove to be more natural for our
purposes.

The parity functions are orthonormal under the inner product $\langle
f,g\rangle=\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2}^{n}}f(x)g(x)$. Since there
are $2^{n}$ distinct parity functions, this gives a complete basis. Given a
function $f:\mathbb{F}_{2}^{n}\to\mathbb{R}$, we can then write

$f(x)=\sum_{S\subseteq[n]}\widehat{f}(S)\chi_{S}(x).$

The $\widehat{f}(S)$ are real numbers known as the Fourier coefficients
(collectively known as the Fourier spectrum), and are equivalently given by
the formula

$\widehat{f}(S)=\langle f(x),\chi_{S}(x)\rangle.$

As a basis change, we can then rethink inner products to be over the Fourier
coefficients as well.

######  Fact 2.7 (Plancherel’s theorem).

$\langle
f,g\rangle=\frac{1}{2^{n}}\sum_{S\subseteq[n]}\widehat{f}(S)\widehat{g}(S).$

Finally, the convolution is an operation that appears frequently in Fourier
analysis over the reals. We can similarly define it over Boolean inputs.

######  Definition 2.8.

For functions $f,g:\mathbb{F}_{2}^{n}\to\mathbb{R}$, we define the
_convolution_ $f\ast g$ as

$(f\ast g)(x)\coloneqq\frac{1}{2^{n}}\sum_{t\in\mathbb{F}_{2}^{n}}f(t)g(x+t).$

Much like Fourier transforms over the reals, convolution maps to
multiplication in the Fourier domain.

######  Fact 2.9 (Convolution theorem).

$\widehat{f\ast g}(S)=\widehat{f}(S)\widehat{g}(S)$

For proofs of all of these facts, as well as for a comprehensive reference on
analysis of Boolean functions, we recommend [o2014analysis].

###  2.3 Weyl Operators and Bell Difference Sampling

For $x=(p,q)\in\mathbb{F}_{2}^{2n}$, define the Weyl operator as

$W_{x}\coloneqq i^{p\cdot
q}(X^{p_{1}}Z^{q_{1}})\otimes\ldots\otimes(X^{p_{n}}Z^{q_{n}})=i^{p\cdot
q}X^{p}Z^{q}.$

Each Weyl operator is a Pauli operator, and every Pauli operator is a Weyl
operator (up to a phase). Note also that $W_{x}W_{y}=W_{x+y}$, up to a phase.
We use Weyl operators (rather than Pauli operators) when it is convenient to
identify members of the Pauli group with length-$2n$ bit strings.

A critical subroutine in our work is Bell difference sampling, which was
introduced in [montanaro2017learning, gross2021schur]. Let
$\ket{\Phi^{+}}\coloneqq 2^{-n/2}\sum_{x\in\mathbb{F}_{2}^{n}}\ket{x,x}$.
Then, the set of quantum states $\\{\ket{W_{x}}\coloneqq(W_{x}\otimes
I)\ket{\Phi^{+}}\mid x\in\mathbb{F}_{2}^{2n}\\}$ forms an orthonormal basis of
$\mathbb{C}^{2^{n}}\otimes\mathbb{C}^{2^{n}}$, which we call the Bell basis.
Bell sampling a state $\ket{\psi}$ refers to measuring $\ket{\psi}^{\otimes
2}$ in the Bell basis, and the measurement outcome is a length-$2n$ bit string
$x$ that corresponds to a Weyl operator $W_{x}$. Bell difference sampling a
state $\ket{\psi}$ refers to Bell sampling twice to get measurement outcomes
$x,y\in\mathbb{F}_{2}^{2n}$ and returning $z=x+y$, which corresponds to a Weyl
operator $W_{z}$ and uses four copies of $\ket{\psi}$. Montanaro showed Bell
difference sampling can be performed in $O(n)$ time [montanaro2017learning].

Bell difference sampling returns a random Weyl operator, but according to what
distribution? Gross, Nezami, and Walter [gross2021schur] showed that the
underlying distribution depends on the so-called characteristic distribution
of $\ket{\psi}$.

######  Definition 2.10 (characteristic distribution).

The _characteristic distribution_ of $\ket{\psi}$ is defined as

$p_{{\psi}}(x)\coloneqq 2^{-n}\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}.$

######  Lemma 2.11 ([gross2021schur, Theorem 3.2]).

Let $\ket{\psi}$ be an arbitrary $n$-qubit pure state. Bell difference
sampling corresponds to drawing a sample from the following distribution:

$q_{\psi}(x)\coloneqq 4^{n}(p_{\psi}\ast
p_{\psi})(x)=\sum_{y\in\mathbb{F}_{2}^{2n}}p_{\psi}(y)p_{{\psi}}(x+y).$

Additionally, if $\ket{\psi}\in\mathcal{S}_{n}$ is a stabilizer state, then

$q_{\psi}(x)=p_{{\psi}}(x)=2^{-n}\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}.$

We refer to $q_{\psi}$ as the Weyl distribution. Using this terminology, the
characteristic distribution and Weyl distribution are equal only when
$\ket{\psi}$ is a stabilizer state (i.e., when $4^{n}(p_{\psi}\ast
p_{\psi})=p_{\psi}$).

##  3 Certificate of Low Stabilizer Complexity

To efficiently distinguish a state with low stabilizer complexity (meaning, a
state with low stabilizer extent or non-negligible stabilizer fidelity) from a
Haar-random one, we require a property or statistic of the state that
distinguishes it from Haar-random. As such, we present the following technical
lemma, which forms the backbone of our algorithm.

######  Lemma 3.1.

Let $\ket{\psi}$ be an $n$-qubit pure state. If the stabilizer fidelity of
$\ket{\psi}$ is at least $\frac{1}{k}$, then

$\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]\geq\dfrac{1}{k^{6}}.$

In contrast, if $\ket{\psi}$ is Haar-random and $n\geq 33$, then, with
probability at least $1-\exp\left(-2^{n/2-15}\right)$ over the Haar measure,

$\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]\leq
2^{-n/2}.$

Our algorithm then amounts to estimating the quantity $\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$ via a
procedure involving Bell difference sampling.

To prove Lemma 3.1, as a first step, we relate $\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$ to the
Fourier coefficients of $p_{\psi}$. Note that this analysis closely resembles
the BLR linearity test [BLRtest] (see also [o2014analysis, Section 1.6]).

######  Fact 3.2.

Let $\ket{\psi}$ be an $n$-qubit pure state. Then,

$\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]=32^{n}\\!\\!\\!\sum_{x\in\mathbb{F}_{2}^{2n}}\widehat{p_{\psi}}(x)^{3}.$

###### Proof.

$\displaystyle\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$
$\displaystyle=2^{n}\mathop{\bf E\/}_{x\sim q_{\psi}}\left[p_{\psi}(x)\right]$
$\displaystyle=2^{n}\sum_{x\in\mathbb{F}_{2}^{2n}}p_{\psi}(x)q_{\psi}(x)$
$\displaystyle=8^{n}\sum_{x\in\mathbb{F}_{2}^{2n}}p_{\psi}(x)(p_{\psi}\ast
p_{\psi})(x)$ $\displaystyle=32^{n}\mathop{\bf
E\/}_{x\sim\mathbb{F}_{2}^{2n}}[p_{\psi}(x)(p_{\psi}\ast p_{\psi})(x)]$
$\displaystyle=32^{n}\sum_{x\in\mathbb{F}_{2}^{2n}}\widehat{p_{\psi}}(x)\widehat{p_{\psi}\ast
p_{\psi}}(x))$
$\displaystyle(\mathrm{\lx@cref{creftype~refnum}{fact:plancherel}})$
$\displaystyle=32^{n}\sum_{x\in\mathbb{F}_{2}^{2n}}\widehat{p_{\psi}}(x)^{3}.$
$\displaystyle(\mathrm{\lx@cref{creftype~refnum}{fact:convolution_theorem}})\qed$

For the remainder of this section, we use the following convention: when
$x=(v,w)\in\mathbb{F}_{2}^{2n}$, $v$ and $w$ denote the first and last $n$
bits of $x$, respectively, and, we will sometimes write $p_{\psi}(v,w)$ and
$q_{\psi}(v,w)$, rather than $p_{\psi}(x)$ and $q_{\psi}(x)$.

###  3.1 The Fourier Spectrum of the Characteristic Distribution

By 3.2, it is clear that understanding the Fourier spectrum of $p_{\psi}$ is
one avenue to proving Lemma 3.1.

######  Proposition 3.3.

The Fourier coefficients of $p_{\psi}(v,w)$ are
$\widehat{p_{\psi}}(v,w)=\frac{1}{2^{n}}p_{\psi}(w,v)$.

###### Proof.

Define $f:\mathbb{F}_{2}^{2n}\xrightarrow[]{}[-1,1]$ as
$f(v,w)\coloneqq\braket{\psi}{i^{v\cdot w}X^{v}Z^{w}}{\psi}$, where
$v,w\in\mathbb{F}_{2}^{n}$. We begin by computing the Fourier expansion of
$f$.

$\displaystyle f(v,w)$ $\displaystyle=\bra{\psi}i^{v\cdot
w}X^{v}Z^{w}\ket{\psi}$
$\displaystyle=\left(\sum_{x\in\mathbb{F}_{2}^{n}}c^{*}_{x}\bra{x}\right)i^{v\cdot
w}X^{v}Z^{w}\left(\sum_{x\in\mathbb{F}_{2}^{n}}c_{x}\ket{x}\right)$
$\displaystyle=i^{v\cdot
w}\left(\sum_{x\in\mathbb{F}_{2}^{n}}c^{*}_{x}\bra{x+v}\right)\left(\sum_{x\in\mathbb{F}_{2}^{n}}(-1)^{x\cdot
w}c_{x}\ket{x}\right)$ $\displaystyle=i^{v\cdot
w}\sum_{x\in\mathbb{F}_{2}^{n}}c_{x+v}^{*}c_{x}(-1)^{w\cdot x}.$ (1)

In the second line we are simply writing $\ket{\psi}$ in the computational
basis.

Observe now that $p_{\psi}(v,w)=\frac{1}{2^{n}}\lvert f(v,w)\rvert^{2}$, which
we can also treat as a function on Boolean variables. Hence,

$\displaystyle p_{\psi}(v,w)$ $\displaystyle=\frac{1}{2^{n}}\left(i^{v\cdot
w}\sum_{x\in\mathbb{F}_{2}^{n}}c_{x+v}^{*}c_{x}(-1)^{w\cdot
x}\right)\left((-i)^{v\cdot
w}\sum_{x\in\mathbb{F}_{2}^{n}}c_{x+v}c^{*}_{x}(-1)^{w\cdot x}\right)$
$\displaystyle=\frac{1}{2^{n}}\sum_{x,y\in\mathbb{F}_{2}^{n}}c^{*}_{v+y}c_{y}c_{v+x+y}c^{*}_{x+y}(-1)^{w\cdot
x},$

where the first equality follows by substituting in Section 3.1.

We can now compute the Fourier spectrum of $p_{\psi}$ by taking the inner
product between $p_{\psi}$ and an arbitrary Fourier character (this is the
simplest approach to computing Fourier coefficients).

$\displaystyle\widehat{p_{\psi}}(v,w)$
$\displaystyle=\frac{1}{4^{n}}\sum_{s,t\in\mathbb{F}_{2}^{n}}p_{\psi}(s,t)(-1)^{s\cdot
v+t\cdot w}$
$\displaystyle=\frac{1}{8^{n}}\sum_{s,t,x,y\in\mathbb{F}_{2}^{n}}c^{*}_{s+y}c_{y}c_{s+x+y}c^{*}_{x+y}(-1)^{t\cdot
x+v\cdot s+w\cdot t}$
$\displaystyle=\frac{1}{8^{n}}\sum_{s,x,y\in\mathbb{F}_{2}^{n}}c^{*}_{s+y}c_{y}c_{s+x+y}c^{*}_{x+y}(-1)^{v\cdot
s}\sum_{t\in\mathbb{F}_{2}^{n}}(-1)^{t\cdot(x+w)}$
$\displaystyle=\frac{1}{4^{n}}\sum_{s,y\in\mathbb{F}_{2}^{n}}c^{*}_{s+y}c_{y}c_{s+w+y}c^{*}_{w+y}(-1)^{v\cdot
s}$ $\displaystyle=\frac{1}{2^{n}}p_{\psi}(w,v).\qed$

###  3.2 Low-Stabilizer-Complexity States

We prove the first part of Lemma 3.1; namely, that

$\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]\geq\dfrac{1}{k^{6}}$

when $\ket{\psi}$ has low stabilizer complexity.

######  Claim 3.4.

For an $n$-qubit pure state
$\ket{\psi}=\sum_{x\in\mathbb{F}_{2}^{n}}c_{x}\ket{x}$,

$32^{n}\sum_{x\in\mathbb{F}_{2}^{2n}}\widehat{p_{\psi}}(x)^{3}\geq\lvert
c_{0}\rvert^{12}.$

###### Proof.

$\displaystyle
32^{n}\\!\\!\sum_{v,w\in\mathbb{F}_{2}^{2n}}\widehat{p_{\psi}}(v,w)^{3}$
$\displaystyle=4^{n}\sum_{v,w\in\mathbb{F}_{2}^{2n}}\\!\\!p_{\psi}(w,v)^{3}$
$\displaystyle(\mathrm{\lx@cref{creftype~refnum}{prop:fourier-
coefficients}}.)$ $\displaystyle\geq
4^{n}\sum_{v\in\mathbb{F}_{2}^{n}}p_{\psi}(0,v)^{3}$ $\displaystyle(\forall
x,y,p_{\psi}(x,y)\geq 0.)$
$\displaystyle=\frac{1}{2^{n}}\sum_{v\in\mathbb{F}_{2}^{n}}\lvert\braket{\psi}{Z^{v}}{\psi}\rvert^{6}$
$\displaystyle\geq\frac{1}{2^{6n}}\left(\sum_{v\in\mathbb{F}_{2}^{n}}\braket{\psi}{Z^{v}}{\psi}\right)^{6}$
$\displaystyle\left(\sum_{i=1}^{m}\lvert
a_{i}\rvert^{6}\geq\frac{1}{m^{5}}\left(\sum_{i=1}^{m}\lvert
a_{i}\rvert\right)^{6}.\right)$ $\displaystyle\geq\lvert c_{0}\rvert^{12}.$
$\displaystyle\left(\sum_{v\in\mathbb{F}_{2}^{n}}Z^{v}=2^{n}\ket{0^{n}}\\!\\!\bra{0^{n}}.\right)\qed$

###### Proof of first part of Lemma 3.1.

Let $\ket{\psi}$ be an $n$-qubit pure state, and suppose that the stabilizer
fidelity of $\ket{\psi}$ is at least $\frac{1}{k}$. Then there exists a
Clifford circuit $C\in\mathcal{C}_{n}$ such that
$C\ket{\psi}=\sum_{x\in\mathbb{F}_{2}^{n}}c_{x}\ket{x}$ where $\lvert
c_{0}\rvert^{2}\geq\frac{1}{k}$. Call $\ket{\phi}\coloneqq C\ket{\psi}$. By
3.4,

$32^{n}\sum_{v,w\in\mathbb{F}_{2}^{n}}\widehat{p_{\phi}}(v,w)^{3}\geq\lvert
c_{0}\rvert^{12}\geq\frac{1}{k^{6}}.$

A Clifford circuit $C$ is a permutation of the Pauli group under conjugation
(i.e., $C^{\dagger}\mathcal{P}_{n}C=\mathcal{P}_{n}$ for any
$C\in\mathcal{C}_{n}$). Hence, for all $C\in\mathcal{C}_{n}$ and
$g:\mathcal{P}_{n}\rightarrow\mathbb{R}$,

$\sum_{x\in\mathbb{F}_{2}^{2n}}g(W_{x})=\sum_{x\in\mathbb{F}_{2}^{2n}}g(C^{\dagger}W_{x}C).$

Therefore, we conclude that

$32^{n}\sum_{v,w\in\mathbb{F}_{2}^{n}}\widehat{p_{\psi}}(v,w)^{3}\geq\frac{1}{k^{6}}$

as well. Combining this bound with 3.2 completes the proof. ∎

###  3.3 Haar-Random States

We complete the proof of Lemma 3.1 by showing that $\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$ is small
when $\ket{\psi}$ is a Haar-random state. We begin by showing that, for a
Haar-random state, all of the Weyl measurements (except $W_{x}=I$) are
exponentially close to $0$ with overwhelming probability.

######  Lemma 3.5 (Lévy’s Lemma, see e.g. [Gerken13measureconcentration]).

Let $\mathbb{S}^{N}$ denote the set of all $N$-dimensional pure quantum
states, and let $f:\mathbb{S}^{N}\to\mathbb{R}$ be $L$-Lipschitz, meaning that
$\lvert f(\ket{\psi})-f(\ket{\varphi})\rvert\leq
L\cdot\lVert\ket{\psi}-\ket{\varphi}\rVert_{2}$. Then:

$\mathop{\bf Pr\/}_{\ket{\psi}\sim\mu_{\rm{Haar}}}\left[\lvert
f(\ket{\psi})-\mathop{\bf E\/}[f]\rvert\geq\varepsilon\right]\leq
2\exp\left(-\frac{N\varepsilon^{2}}{9\pi^{3}L^{2}}\right).$

######  Lemma 3.6.

For any $n$-qubit Weyl operator $W_{x}$, the function
$f_{x}:\mathbb{S}^{2^{n}}\to\mathbb{R}$ defined by
$f_{x}(\ket{\psi})=\bra{\psi}W_{x}\ket{\psi}$ is $2$-Lipschitz.

###### Proof.

Write $W_{x}=\Pi_{+}-\Pi_{-}$ where $\Pi_{+}$ and $\Pi_{-}$ are the projectors
onto the positive and negative eigenspaces of $W_{x}$, respectively. Then,

$\displaystyle\lvert f_{x}(\ket{\psi})-f_{x}(\ket{\varphi})\rvert$
$\displaystyle=\lvert\bra{\psi}W_{x}\ket{\psi}-\bra{\varphi}W_{x}\ket{\varphi}\rvert$
$\displaystyle=\lvert\bra{\psi}\Pi_{+}\ket{\psi}-\bra{\varphi}\Pi_{+}\ket{\varphi}-\bra{\psi}\Pi_{-}\ket{\psi}+\bra{\varphi}\Pi_{-}\ket{\varphi}\rvert$
$\displaystyle\leq\lvert\bra{\psi}\Pi_{+}\ket{\psi}-\bra{\varphi}\Pi_{+}\ket{\varphi}\rvert+\lvert\bra{\psi}\Pi_{-}\ket{\psi}+\bra{\varphi}\Pi_{-}\ket{\varphi}\rvert$
$\displaystyle=\lvert\
\lVert\Pi_{+}\ket{\psi}\rVert_{2}-\lVert\Pi_{+}\ket{\varphi}\rVert\rvert_{2}+\lvert\lVert\Pi_{-}\ket{\psi}\rVert_{2}-\lVert\Pi_{-}\ket{\varphi}\rVert_{2}\rvert$
$\displaystyle\leq\lVert\Pi_{+}(\ket{\psi}-\ket{\varphi})\rVert_{2}+\lVert\Pi_{-}(\ket{\psi}-\ket{\varphi})\rVert_{2}$
$\displaystyle\leq 2\lVert\ket{\psi}-\ket{\varphi}\rVert_{2},$

where the third and fifth lines apply the triangle inequality, and the fourth
and sixth lines use the fact that $\Pi_{+}$ and $\Pi_{-}$ are projectors. ∎

######  Corollary 3.7.

Let $W_{x}$ be any $n$-qubit Weyl operator in which $x\neq 0$ (i.e. $W_{x}\neq
I$). Then:

$\mathop{\bf
Pr\/}_{\ket{\psi}\sim\mu_{\rm{Haar}}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert\geq\varepsilon\right]\leq
2\exp\left(-\frac{2^{n}\varepsilon^{2}}{36\pi^{3}}\right).$

###### Proof.

Define $f_{x}(\ket{\psi})=\bra{\psi}W_{x}\ket{\psi}$ as in Lemma 3.6. By Lemma
3.6, we know that $f_{x}$ is $2$-Lipschitz. Additionally, observe that
$\mathop{\bf E\/}[f]=0$ over the Haar measure because exactly half of the
eigenvalues of $W_{x}$ are $1$ and the other half are $-1$. Then the corollary
follows from Lemma 3.5. ∎

######  Corollary 3.8.

$\mathop{\bf Pr\/}_{\ket{\psi}\sim\mu_{\rm{Haar}}}\left[\exists x\neq
0:\lvert\braket{\psi}{W_{x}}{\psi}\rvert\geq\varepsilon\right]\leq
2^{2n+1}\exp\left(-\frac{2^{n}\varepsilon^{2}}{36\pi^{3}}\right).$

###### Proof.

This follows from Corollary 3.7 and a union bound over all $2^{2n}$ possible
Weyl operators. ∎

Note that if $\varepsilon\geq\frac{1}{\mathrm{poly}(n)}$, then the probability
bound in Corollary 3.8 is doubly-exponentially small.

We have shown that, with high probability, all Weyl measurements (except
$W_{x}=I$) are close to $0$. We use this to complete the proof of Lemma 3.1.

###### Proof of second part of Lemma 3.1.

Suppose $\ket{\psi}$ is a Haar-random state. By Corollary 3.8, for all
$W_{x}\neq I$,
$\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}=2^{n}p(x)\leq\varepsilon^{2}$ with
probability
$1-2^{2n+1}\exp\left(-\frac{2^{n}\varepsilon^{2}}{36\pi^{3}}\right)$.
Therefore by 3.2 and Proposition 3.3,

$\displaystyle\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$
$\displaystyle=32^{n}\sum_{x,y\in\mathbb{F}_{2}^{n}}\widehat{p}(x,y)^{3}$
$\displaystyle=4^{n}\sum_{w,v\in\mathbb{F}_{2}^{n}}p(v,w)^{3}$
$\displaystyle=4^{n}\left(\frac{1}{8^{n}}+\sum_{\begin{subarray}{c}w,v\in\mathbb{F}_{2}^{n}\\\
w,v\neq 0\end{subarray}}p(v,w)^{3}\right)$
$\displaystyle\leq\frac{1+(4^{n}-1)\varepsilon^{6}}{2^{n}},$

with probability at least
$1-2^{2n+1}\exp\left(-\frac{2^{n}\varepsilon^{2}}{36\pi^{3}}\right)$. By
setting
$\epsilon^{2}=\frac{1}{2^{n/6}}\left(\frac{2^{n}-2^{n/2}}{4^{n}-1}\right)^{1/3}$,
we get

$\mathop{\bf E\/}_{x\sim
q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]\leq\frac{1}{2^{n/2}}$

with probability at least
$1-2^{2n+1}\exp\left(-\frac{2^{5n/6}}{36\pi^{3}}\left(\frac{2^{n}-2^{n/2}}{4^{n}-1}\right)^{1/3}\right)$,
which is at least $1-\exp\left(-2^{n/2-15}\right)$ for $n\geq 33$. ∎

##  4 Algorithm and Sample Complexity Analysis

We are now ready to state and analyze our algorithm that distinguishes between
Haar-random states and states with low stabilizer complexity. Our algorithm
uses the fact that we can efficiently sample from $q_{\psi}$ (via Bell
difference sampling) and efficiently estimate
$\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}$ for any given
$x\in\mathbb{F}_{2}^{2n}$, using quantum measurements. By combining these
subroutines, we construct an unbiased estimator for $\mathop{\bf E\/}_{x\sim
q}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$. Motivated by Lemma
3.1, if our estimator exceeds a certain threshold we determine that the input
state has low stabilizer complexity; otherwise, we determine that the state is
Haar-random. For the remainder of this section, $\eta\coloneqq\mathop{\bf
E\/}_{x\sim q}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right]$.

Input: Black-box access to copies of $\ket{\psi}$

Promise : $\ket{\psi}$ is Haar-random or has stabilizer fidelity at least
$\frac{1}{k}$

Output: $1$ if $\ket{\psi}$ has stabilizer fidelity at least $\frac{1}{k}$ and
$0$ if $\ket{\psi}$ is Haar-random

1 Let $m=60k^{12}\ln(1/\delta)$.

2repeat  _$m$_ times

3 Perform Bell difference sampling to obtain $W_{x}\sim q_{\psi}$.

4 Perform the measurement $W_{x}^{\otimes 2}$ on $\ket{\psi}^{\otimes 2}$. Let
$X_{i}\in\\{\pm 1\\}$ denote the measurement outcome.

5

Set $\widehat{\eta}=\frac{1}{m}\sum_{i}X_{i}$. Return $1$ if
$\widehat{\eta}\geq\frac{2}{3k^{6}}$, and $0$ otherwise.

Algorithm 1 Distinguishing Low-Stabilizer-Complexity States from Haar-Random

######  Theorem 4.1.

Let $\ket{\psi}$ be an unknown $n$-qubit pure state for some $n\geq 33$, and
let $k\leq\frac{4}{5}2^{n/12}$. Algorithm 1 distinguishes whether $\ket{\psi}$
is Haar-random or a state with stabilizer fidelity at least $\frac{1}{k}$,
promised that one of these is the case. The algorithm uses
$O\left(k^{12}\log(1/\delta)\right)$ copies of $\ket{\psi}$ and
$O(nk^{12}\log(1/\delta))$ time, and distinguishes the two cases with success
probability at least $1-\delta$.

###### Proof.

Following the notation in Algorithm 1, $X_{i}$ is the outcome of the
measurement on the $i$th iteration of the algorithm loop. Observe that for any
$X_{i}$,

$\mathop{\bf E\/}_{{\begin{subarray}{c}x\sim q_{\psi},\\\ \text{meas. by
$W_{x}^{\otimes 2}$}\end{subarray}}}[X_{i}]=\mathop{\bf E\/}_{x\sim
q_{\psi}}\bra{\psi^{\otimes 2}}W_{x}^{\otimes 2}\ket{\psi^{\otimes
2}}=\mathop{\bf E\/}_{x\sim
q_{\psi}}\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}=\eta.$

Therefore, $\widehat{\eta}=\frac{1}{m}\sum_{i}X_{i}$ is an unbiased estimator
of $\eta$ (i.e., $\mathop{\bf E\/}[\widehat{\eta}]=\eta$).

Suppose $\ket{\psi}$ has stabilizer fidelity at least $\frac{1}{k}$. Then, our
algorithm fails when $\widehat{\eta}<\frac{2}{3k^{6}}$. Hence,

$\mathop{\bf Pr\/}[\text{\lx@cref{creftype~refnum}{alg:distinguisher}
fails}]=\mathop{\bf
Pr\/}\left[\widehat{\eta}<\frac{2}{3k^{6}}\right]=\mathop{\bf
Pr\/}\left[\widehat{\eta}-\eta<\frac{2}{3k^{6}}-\eta\right]\leq\mathop{\bf
Pr\/}\left[\widehat{\eta}-\eta\leq-\frac{1}{3k^{6}}\right],$

where the last inequality follows from Lemma 3.1. By Hoeffding’s inequality,

$\mathop{\bf
Pr\/}\left[\widehat{\eta}-\eta\leq-\frac{1}{3k^{6}}\right]\leq\exp\left(-\frac{m}{18k^{12}}\right).$

Therefore, $m\geq 18k^{12}\ln(15)=49k^{12}$ samples suffice for the failure
probability to be at most $\frac{1}{15}$.

Now suppose $\ket{\psi}$ is Haar-random. Then, our algorithm fails when
$\widehat{\eta}\geq\frac{2}{3k^{6}}$. By Lemma 3.1, $\eta\leq 2^{-n/2}$ with
probability at least $1-\exp\left(-2^{n/2-15}\right)>=1-e^{-2\sqrt{2}}$ for
$n\geq 33$. Assuming that $\eta\leq 2^{-n/2}$,

$\mathop{\bf Pr\/}[\text{\lx@cref{creftype~refnum}{alg:distinguisher}
fails}]=\mathop{\bf
Pr\/}\left[\widehat{\eta}\geq\frac{2}{3k^{6}}\right]=\mathop{\bf
Pr\/}\left[\widehat{\eta}-\eta\geq\frac{2}{3k^{6}}-\eta\right]\leq\mathop{\bf
Pr\/}\left[\widehat{\eta}-\eta\geq\frac{1}{2k^{6}}-2^{-n/2}\right].$

Once again, by Hoeffding’s inequality,

$\displaystyle\mathop{\bf
Pr\/}\left[\widehat{\eta}-\eta\geq\frac{1}{2k^{6}}-2^{-n/2}\right]$
$\displaystyle\leq\exp\left(-\frac{m}{2}\left(\frac{2}{3k^{6}}-2^{-n/2}\right)^{2}\right)$
$\displaystyle\leq\exp\left(-\frac{m}{2}\left(\frac{2}{3k^{6}}-\frac{1}{3k^{6}}\right)^{2}\right)$
$\displaystyle\leq\exp\left(-\frac{m}{18k^{12}}\right).$

Therefore, $m\geq-18k^{12}\ln\left(\frac{1}{15}-e^{-2\sqrt{2}}\right)\geq
88k^{12}$ samples suffice for the failure probability to be at most
$\frac{1}{15}-e^{-2\sqrt{2}}$. By the union bound, the failure probability is
at most $\frac{1}{15}$, where the randomness is over both the Haar measure and
the quantum measurements.

We have shown that in either case we output the correct answer with
probability at least $\frac{14}{15}$. Using the Chernoff-Hoeffding theorem,
the success probability can be boosted from $\frac{14}{15}$ to at least
$1-\delta$ by doing $\frac{2}{3}\ln(1/\delta)$ repetitions of Algorithm 1 and
taking the majority answer. Since each iteration of the algorithm loop uses
$6$ copies of $\ket{\psi}$, Algorithm 1 consumes
$O\left(k^{12}\log(1/\delta)\right)$ copies in total. Finally, Bell difference
sampling and performing the measurement $W_{x}^{\otimes 2}$ takes $O(n)$ time,
so the total runtime is $O\left(nk^{12}\log(1/\delta)\right)$. ∎

All of these results also apply to states with stabilizer extent at most $k$,
since by 2.3, such states have stabilizer fidelity at least $\frac{1}{k}$.

######  Corollary 4.2.

Let $\ket{\psi}$ be an unknown $n$-qubit pure state for $n\geq 33$, and let
$k\leq\frac{4}{5}2^{n/12}$. Algorithm 1 distinguishes whether $\ket{\psi}$ is
Haar-random or a state with stabilizer extent at most $k$, promised that one
of these is the case. The algorithm uses $O\left(k^{12}\log(1/\delta)\right)$
copies of $\ket{\psi}$ and distinguishes the two cases with success
probability at least $1-\delta$.

The above result immediately implies that output states of Clifford+$T$
circuits with few $T$-gates cannot be computationally pseudorandom.

######  Corollary 4.3.

Any family of Clifford+$T$ circuits that produces an ensemble of $n$-qubit
computationally pseudorandom quantum states must use at least $\omega(\log n)$
$T$-gates.

###### Proof.

Consider any ensemble of states wherein each state in the ensemble is the
output of some Clifford+$T$ circuit with at most $K\log n$ $T$-gates. By Lemma
2.5, the stabilizer extent of any such state $\ket{\psi}$ is at most
$n^{\alpha K}$ for $\alpha\leq 0.7716$. By Corollary 4.2, on input copies of
$\ket{\psi}$, Algorithm 1 takes $O(n^{12\alpha K+1})\leq\poly(n)$ time and
outputs $1$ with probability at least $2/3$. On the other hand, if
$\ket{\psi}$ is a Haar-random state then the same algorithm outputs $1$ with
probability at most $\frac{1}{3}$. As such, the algorithm’s distinguishing
advantage between the ensemble and the Haar measure is non-negligible. This is
to say that the ensemble cannot be pseudorandom under the definition of
[Ji10.1007/978-3-319-96878-0_5]. ∎

##  5 Open Problems

An immediate direction for future work is to improve the sample complexity of
our algorithm, or to prove sample complexity lower bounds. One can also
endeavour to improve other features of our algorithm: Is it possible to remove
the need for entangled measurements?222 The optimal algorithms for learning
and testing stabilizer states use entangled measurements. So, a first step
would be to understand how many separable measurements are required to
separate stabilizer states from Haar-random. Or, is it possible to show that
entangled measurements are in any sense necessary? Are there quantum
measurements that allow us to sample from $p_{\psi}$ directly (rather than
$q_{\psi}$)?

Beyond that, can Bell difference sampling be used for learning and/or property
testing stabilizer-extent-$k$ states? For stabilizer states ($k=1$), a
$6$-query property testing algorithm is given by [gross2021schur] and a
$\Theta(n)$-query learning algorithm is given by [montanaro2017learning]. Both
algorithms rely on Bell difference sampling and are asymptotically optimal. We
ask if there are generalizations of these algorithms for states with higher
stabilizer complexity, similar to the question that was raised in
[arunachalam2022phase].

######  Question 5.1.

Is there a $\poly(k)$-query algorithm for property testing stabilizer-
extent-$k$ states? Likewise, is there a $\poly(n,k)$-time algorithm for
learning stabilizer-extent-$k$ states?

Our results on stabilizer extent are due to the fact that extent and fidelity
are inversely related. Is it possible to relate stabilizer rank (a closely-
related complexity measure, denoted by $\chi$) and stabilizer fidelity? For
instance, proving that, for all states $\ket{\psi}$,

$F_{\mathcal{S}}(\ket{\psi})^{-1}\leq\chi(\ket{\psi})^{c},\quad\text{for any
constant $c$,}$

would imply that our algorithm can distinguish low-stabilizer-rank states from
Haar-random. However, proving such a relation for even $c<\frac{\alpha n}{\log
n}$ for $\alpha\leq 0.2284$ would imply super-linear lower bounds on the
stabilizer rank of Clifford magic states, a long-standing open problem.

One can also ask if the lower bound on the number of $T$-gates necessary for
computationally pseudorandom states can be improved.

######  Question 5.2.

How many $T$-gates are necessary for a family of Clifford+$T$ circuits to
produce an ensemble of $n$-qubit computationally pseudorandom states?

We remark that any improvements to our $\log n$ lower bound would require
techniques beyond the ones used in our paper. Indeed, in Appendix B we show
that one can hope for at most a quadratic improvement in the relationship
between $\eta$ and stabilizer fidelity. Such an improvement would only yield
constant-factor improvements on the number of $T$-gates necessary to prepare
computationally pseudorandom states.

On the other hand, we are not aware of any attempts to optimize the $T$-gate
count for plausible constructions of $n$-qubit pseudorandom states. The best
upper bound we know of is the essentially trivial bound of $O(n)$, based on
constructions of with $O(n)$ general gates. This is because pseudorandom
states can be constructed from pseudorandom functions (PRFs) with constant
overhead [brakerski10.1007/978-3-030-36030-6_10], and PRFs are believed to be
constructible in linear time [ishai_10.1145/1374376.1374438,
fan_10.1145/3519935.3520010].333Technically, we are not sure whether the PRFs
constructed in [ishai_10.1145/1374376.1374438, fan_10.1145/3519935.3520010]
are secure against quantum adversaries, which is necessary for instantiating
[brakerski10.1007/978-3-030-36030-6_10]’s construction, but we consider it
reasonable to conjecture that linear-time quantum-secure PRFs exist.

## Acknowledgments

We thank Scott Aaronson for helpful comments. SG, VI, DL are supported by
Scott Aaronson’s Vannevar Bush Fellowship from the US Department of Defense,
the Berkeley NSF-QLCI CIQC Center, a Simons Investigator Award, and the Simons
“It from Qubit” collaboration. WK is supported by an NDSEG Fellowship.

## References

  * [ABDY22] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder.  Optimal algorithms for learning quantum phase states, 2022.  doi:10.48550/arxiv.2208.07851.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5), nov 2004.  doi:10.1103/physreva.70.052328.
  * [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, September 2019.  doi:10.22331/q-2019-09-02-181.
  * [BG16] Sergey Bravyi and David Gosset.  Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.  Phys. Rev. Lett., 116:250501, 2016.  doi:10.1103/PhysRevLett.116.250501.
  * [BHMT02] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp.  Quantum Amplitude Amplification and Estimation, 2002.  doi:10.1090/conm/305/05215.
  * [BLR93] Manuel Blum, Michael Luby, and Ronitt Rubinfeld.  Self-Testing/Correcting with Applications to Numerical Problems.  J. Comput. Syst. Sci., 47(3):549–595, 1993.  doi:10.1016/0022-0000(93)90044-W.
  * [BS19] Zvika Brakerski and Omri Shmueli.  (Pseudo) Random Quantum States with Binary Phase.  In Theory of Cryptography, 2019.  doi:10.1007/978-3-030-36030-6_10.
  * [CS96] A. R. Calderbank and Peter W. Shor.  Good quantum error-correcting codes exist.  Phys. Rev. A, 54:1098–1105, 1996.  doi:10.1103/PhysRevA.54.1098.
  * [FLY22] Zhiyuan Fan, Jiatu Li, and Tianqi Yang.  The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 962–975, 2022.  doi:10.1145/3519935.3520010.
  * [Ger13] Manuel Gerken.  Measure concentration: Levy’s Lemma, 2013.
  * [GNW21] David Gross, Sepehr Nezami, and Michael Walter.  Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations.  Communications in Mathematical Physics, 385(3):1325–1393, 2021\.  doi:10.1007/s00220-021-04118-7.
  * [Got97] Daniel Gottesman.  Stabilizer Codes and Quantum Error Correction, 1997.  doi:10.48550/arxiv.quant-ph/9705052.
  * [Got98] Daniel Gottesman.  The Heisenberg Representation of Quantum Computers.  1998\.  doi:10.48550/arXiv.quant-ph/9807006.
  * [HIN+22] Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, and Ryan Sweke.  A single $t$-gate makes distribution learning hard, 2022.  doi:10.48550/arxiv.2207.03140.
  * [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, 2020.  doi:10.1038/s41567-020-0932-7.
  * [HMMH+20] Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth.  Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates, 2020.  doi:10.48550/arxiv.2002.09524.
  * [IKOS08] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai.  Cryptography with Constant Computational Overhead.  In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 433–442, 2008.  doi:10.1145/1374376.1374438.
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song.  Pseudorandom Quantum States.  In Advances in Cryptology – CRYPTO 2018. Springer International Publishing, 2018.  doi:10.1007/978-3-319-96878-0_5.
  * [KG15] Richard Kueng and David Gross.  Qubit stabilizer states are complex projective 3-designs, 2015.  doi:10.48550/arXiv.1510.02767.
  * [KLR+08] E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland.  Randomized benchmarking of quantum gates.  Physical Review A, 77(1), 2008.  doi:10.1103/physreva.77.012307.
  * [LC22] Ching-Yi Lai and Hao-Chung Cheng.  Learning Quantum Circuits of Some $T$ Gates.  IEEE Transactions on Information Theory, 68(6):3951–3964, 2022\.  doi:10.1109/TIT.2022.3151760.
  * [Mon17] Ashley Montanaro.  Learning stabilizer states by Bell sampling.  arXiv preprint arXiv:1707.04012, 2017.  doi:10.48550/arXiv.1707.04012.
  * [NC02] Michael A. Nielsen and Isaac Chuang.  Quantum Computation and Quantum Information, 2002.  doi:10.1017/CBO9780511976667.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.  doi:10.1017/CBO9781139814782.
  * [PWB15] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett.  Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities.  Phys. Rev. Lett., 115:070501, 2015.  doi:10.1103/PhysRevLett.115.070501.
  * [RB00] Robert Raussendorf and Hans J. Briegel.  Quantum computing via measurements only, 2000.  doi:10.48550/arxiv.quant-ph/0010033.
  * [RLCK19] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer.  Simulation of qubit quantum circuits via Pauli propagation.  Phys. Rev. A, 99:062337, 2019.  doi:10.1103/PhysRevA.99.062337.
  * [Sho95] Peter W. Shor.  Scheme for reducing decoherence in quantum computer memory.  Phys. Rev. A, 52:R2493–R2496, 1995.  doi:10.1103/PhysRevA.52.R2493.
  * [Web16] Zak Webb.  The Clifford Group Forms a Unitary 3-Design.  Quantum Info. Comput., 16(15–16):1379–1400, 2016.
  * [ZKGG16] Huangjun Zhu, Richard Kueng, Markus Grassl, and David Gross.  The Clifford group fails gracefully to be a unitary 4-design, 2016.  arXiv:1609.08172.

##  Appendix A Algorithm Improvements via State Preparation Unitary

When given access to a state preparation unitary for $\ket{\psi}$ (and its
inverse), denoted by $U$ and $U^{\dagger}$, we can improve the sample and time
complexities of our algorithm to $O\left(k^{3}\log(1/\delta)\right)$ and
$O\left(nk^{3}\log(1/\delta)\right)$, respectively, at the cost of
$O\left(k^{3}\log(1/\delta)\right)$ queries to $U$ and $U^{\dagger}$.

Access to $U$ and $U^{\dagger}$ allows us to run quantum amplitude estimation
(QAE) as a subroutine in our algorithm. Recall the well-known result of
Brassard, Høyer, Mosca, and Tapp:

######  Theorem A.1 (Quantum Amplitude Estimation (Theorem 12 in
[Brassard_2002])).

Let $\Pi$ be a projector and $\ket{\psi}$ be an $n$-qubit pure state such that
$\braket{\psi}{\Pi}{\psi}=\eta$. Given access to the unitary transformations
$R_{\Pi}=2\Pi-I$ and $R_{\psi}=2\ket{\psi}\\!\\!\bra{\psi}-I$, there exists a
quantum algorithm that outputs $\widehat{\eta}$ such that

$\lvert\widehat{\eta}-\eta\rvert\leq\frac{2\pi\sqrt{\eta(1-\eta)}}{m}+\frac{\pi^{2}}{m^{2}}$

with probability at least $\frac{8}{\pi^{2}}$. The algorithm makes $m$ calls
to $R_{\Pi}$ and $R_{\psi}$.

######  Corollary A.2.

Let $\Pi$, $\ket{\psi}$, $R_{\Pi}$, and $R_{\psi}$ be the same as in Theorem
A.1. There exists a quantum algorithm that outputs $\widehat{\eta}$ such that

$\lvert\widehat{\eta}-\eta\rvert\leq\varepsilon$

with probability at least $\frac{8}{\pi^{2}}$. The algorithm makes no more
than

$\pi\frac{\sqrt{\eta(1-\eta)+\varepsilon}}{\varepsilon}$

calls to $R_{\Pi}$ and $R_{\psi}$.

###### Proof.

By Theorem A.1, this will require $m$ queries, where $m$ is a solution to the
following quadratic equation:

$\frac{2\pi\sqrt{\eta(1-\eta)}}{m}+\frac{\pi^{2}}{m^{2}}\leq\varepsilon\Rightarrow
m\geq\pi\frac{\sqrt{\eta(1-\eta)+\varepsilon}}{\varepsilon}\geq\pi\frac{\sqrt{\eta(1-\eta)}+\sqrt{\eta(1-\eta)+\varepsilon}}{2\varepsilon}.$

∎

With that, we are ready to explain the modifications to Algorithm 1 that
achieves a quartic speedup in the dependency on $k$.

######  Theorem A.3.

Let $\ket{\psi}$ be an unknown $n$-qubit pure state prepared by a unitary $U$
for $n\geq 33$, and let $k\leq\frac{4}{5}2^{n/12}$. There exists a quantum
algorithm that distinguishes whether $\ket{\psi}$ is Haar-random or a state
with stabilizer fidelity at least $\frac{1}{k}$, promised that one of these is
The case. The algorithm uses $O\left(k^{3}\log(1/\delta)\right)$ applications
of either $U$ or $U^{\dagger}$ and time $O\left(nk^{3}\log(1/\delta)\right)$,
and distinguishes the two cases with success probability at least $1-\delta$.

###### Proof.

We first define the Bell difference sampling projector on $x$ as

$\Pi_{x}\coloneqq\sum_{y\in\mathbb{F}_{2}^{2n}}\ket{W_{y}}\\!\\!\bra{W_{y}}\otimes\ket{W_{x+y}}\\!\\!\bra{W_{x+y}}.$

Note that this is simply a compact way of writing the Bell difference sampling
procedure: the probability of sampling $x$ is
$q_{\psi}(x)=\lVert\Pi_{x}\ket{\psi^{\otimes 4}}\rVert$.444Indeed, this is the
way Gross, Nezami, and Walter [gross2021schur] introduce Bell difference
sampling. We can also perform the projective measurement $P_{\psi,x}\coloneqq
W_{x}\ket{\psi}\\!\\!\bra{\psi}W_{x}=W_{x}U\ket{0}\\!\\!\bra{0}U^{\dagger}W_{x}$,
where this measurement is performed by applying $W_{x}$, $U^{\dagger}$, and
then measuring in the computational basis. We can entangle $\Pi_{x}$ and
$P_{\psi,x}$ to form the following projector:

$M=\sum_{x\in\mathbb{F}_{2}^{2n}}\Pi_{x}\otimes P_{\psi,x}.$

Building $M$ involves controlled applications of $W_{x}$ according to the Bell
difference sampling outcome. Observe that

$\braket{\psi^{\otimes 5}}{M}{\psi^{\otimes
5}}=\sum_{x\in\mathbb{F}_{2}^{2n}}\braket{\psi^{\otimes
4}}{\Pi_{x}}{\psi^{\otimes 4}}\cdot\braket{\psi}{P_{\psi,x}}{\psi}=\mathop{\bf
E\/}_{x\sim q_{\psi}}\left[\lvert\braket{\psi}{W_{x}}{\psi}\rvert^{2}\right].$

Hence, we can run QAE with the input projector $M$ and the input state
$\ket{\psi^{\otimes 5}}$, and the output will be an estimate of $\eta$ whose
accuracy depends on $m$, the number of total calls to $R_{\Pi}$ and
$R_{\psi}$.

Proving the sample complexity bound will mimic Theorem 4.1. Suppose
$\ket{\psi}$ is a state with stabilizer fidelity at least $\frac{1}{k}$.
Define $\eta_{min}\coloneqq\frac{1}{k^{6}}$, and note that for any state with
stabilizer fidelity at least $\frac{1}{k}$, $\eta\geq\eta_{min}$ due to Lemma
3.1. For our algorithm to succeed, recall from the proof of Theorem 4.1 that
we need

$\lvert\widehat{\eta}-\eta\rvert\leq\lvert\frac{2}{3k^{6}}-\eta\rvert.$

Therefore, we can run QAE with a fixed value of $m$ (to be specified later)
for an estimate of $\eta$ whose accuracy is within
$\pm\left(\eta-\frac{2}{3k^{6}}\right)$. By Corollary A.2,

$\displaystyle
m\geq\pi\frac{\sqrt{\eta(1-\eta)+\eta-\frac{2}{3k^{6}}}}{\eta-\frac{2}{3k^{6}}}$
(2)

queries suffice. The chosen value of $m$ must work for all
$\eta\in[\frac{1}{k^{6}},1]$. Note that Eq. 2 is monotonically decreasing for
$\eta\in[\frac{2}{3k^{6}},1)$, and is therefore maximized by $\eta_{min}$ for
$\eta\in[\frac{1}{k^{6}},1]$. To succeed with probability at least
$\frac{8}{\pi^{2}}$,

$m\geq 4\pi
k^{3}\geq\pi\sqrt{12k^{6}-9}=\pi\frac{\sqrt{\eta_{min}(1-\eta_{min})+\eta_{min}-\frac{2}{3k^{6}}}}{\eta_{min}-\frac{2}{3k^{6}}}$

calls to $R_{\Pi}$ and $R_{\psi}$ suffices.

Now suppose $\ket{\psi}$ is a Haar-random state. Again, by Lemma 3.1, we know
that $\eta\leq 2^{-n/2}$ with probability $1-e^{-2\sqrt{2}}$ for $n\geq 33$.
Assuming $\eta\leq 2^{-n/2}$ and using Corollary A.2, as long as we have

$m\geq\sqrt{6}\pi
k^{3}\geq\pi\frac{\sqrt{2^{-n/2}(1-2^{-n/2})+\frac{2}{3k^{6}}-2^{-n/2}}}{\frac{2}{3k^{6}}-2^{-n/2}}\geq\pi\frac{\sqrt{\eta(1-\eta)+\frac{2}{3k^{6}}-\eta}}{\frac{2}{3k^{6}}-\eta}$

queries to $R_{\Pi}$ and $R_{\psi}$, we obtain the correct answer with
probability at least $\frac{8}{\pi^{2}}$. In the inequalities above we use
similar reasoning to the stabilizer fidelity $\frac{1}{k}$ case, combined with
the fact that $2^{-n/2}\leq\frac{1}{3k^{6}}$.

Finally, since $R_{\Pi}$ and $R_{\psi}$ use a constant number of calls to $U$
and $U^{\dagger}$, the total number of calls is $O(k^{3})$. Chernoff-Hoeffding
can be used to bring the success probability from $3/4$ to $1-\delta$ using
$6\ln(1/\delta)$ repetitions. The runtime includes an extra factor of $O(n)$,
due to the linear cost of both preparing $W_{x}$ and the Bell difference
sampling projector, giving a $O\left(nk^{3}\log(1/\delta)\right)$ time
complexity. ∎

##  Appendix B On the Tightness of Our Analysis

We argue that the first part of Lemma 3.1 is polynomially-close to optimal. We
begin by computing the stabilizer extent and stabilizer fidelity of Clifford
magic states. The two technical ingredients involved in the computation are
due to Bravyi et al. [Bravyi2019simulationofquantum].

######  Fact B.1 ([Bravyi2019simulationofquantum, Proposition 2]).

Let $\ket{\psi}$ be a Clifford magic state. Then,
$\xi(\ket{\psi})=F_{\mathcal{S}}(\ket{\psi})^{-1}$.

######  Fact B.2 ([Bravyi2019simulationofquantum, Proposition 1]).

Let $\\{\ket{\psi_{1}},\ket{\psi_{2}},\ldots,\ket{\psi_{L}}\\}$ be any set of
states such that each state $\ket{\psi_{j}}$ describes a system of at most $3$
qubits. Then,

$\xi(\ket{\psi_{1}}\otimes\ket{\psi_{2}}\otimes\ldots\otimes\ket{\psi_{L}})=\prod_{i}\xi(\ket{\psi_{i}}).$

It is well known that the $m$-fold tensor product of $\ket{T}\coloneqq
2^{-1/2}(\ket{0}+e^{i\pi/4}\ket{0})$ is a Clifford magic state. Using the
facts above, we can compute the stabilizer extent and stabilizer fidelity of
$\ket{T^{\otimes m}}$.

######  Fact B.3.

$\xi(\ket{T^{\otimes m}})=\left(\cos\pi/8\right)^{-2m}\quad\text{and}\quad
F_{\mathcal{S}_{m}}(\ket{T^{\otimes m}})=\left(\cos\pi/8\right)^{2m}.$

###### Proof.

By B.2, the stabilizer extent of $\ket{T^{\otimes{m}}}$ is simply the
stabilizer extent of $\ket{T}$ raised to the power $m$. By B.1, the stabilizer
extent is the inverse of the stabilizer fidelity. Hence, the result follows
simply by showing that the stabilizer fidelity of $\ket{T}$ is
$\cos(\pi/8)^{2}$, which can be verified by explicit calculation over the $6$
different $1$-qubit stabilizer states. ∎

Next, we compute $\eta$ for the state $\ket{T^{\otimes m}}$.

######  Claim B.4.

Let $\ket{\psi}=\ket{T^{\otimes m}}$ and define $\eta\coloneqq\mathop{\bf
E\/}_{x\sim q_{\psi}}[2^{n}p_{\psi}(x)]$. Then, $\eta=(5/8)^{m}$.

###### Proof.

We begin by writing out $\ket{T}\\!\\!\bra{T}$ as a sum of Pauli matrices. By
definition,

$\ket{T}\\!\\!\bra{T}=\dfrac{1}{2}\left(I+\dfrac{1}{\sqrt{2}}X+\dfrac{1}{\sqrt{2}}Y\right).$

We wish to compute $\sum_{x\in\mathbb{F}_{2}^{2m}}\widehat{p}_{\psi}(x)^{3}$.
We know that every such Pauli with nonzero $\widehat{p}_{\psi}(x)$ is a tensor
product combination of $I$, $X$, and $Y$, so we enumerate over the number of
indices where an $X$ or $Y$ appear.

$\sum_{x\in\mathbb{F}_{2}^{2m}}\widehat{p}_{\psi}(x)^{3}=\dfrac{1}{2^{6m}}\sum_{k=0}^{m}\binom{m}{k}\dfrac{1}{2^{3k}}\cdot
2^{k}=\dfrac{1}{64^{m}}\sum_{k=0}^{m}\binom{m}{k}\dfrac{1}{4^{k}}=\left(\frac{5}{256}\right)^{m}.$

Thus, by 3.2,

$\eta=32^{m}\sum_{x\in\mathbb{F}_{2}^{2m}}\widehat{p}_{\psi}(x)^{3}=\left(\frac{5}{8}\right)^{m}.\qed$

Combining B.4 with Lemma 3.1, we have

$F_{\mathcal{S}}(\ket{\psi})\leq\eta^{1/c}=\left(\frac{5}{8}\right)^{m/c}$

for $c=6$ (Lemma 3.1). But, from B.3, we know that
$F_{\mathcal{S}}(\ket{T^{\otimes m}})=(\cos\pi/8)^{2m}$. Combining the two
statements gives

$(\cos\pi/8)^{2m}\leq(5/8)^{m/c}.$

$c\approx 2.97$ is the minimum $c$ that does not violate this inequality.
Hence, one cannot hope for much more than a quadratic improvement in our
bound.