remresetThe remreset package revtex4-1Repair the float

# Learning $t$-doped stabilizer states exactly

Lorenzo Leone<EMAIL_ADDRESS>Physics Department, University of
Massachusetts Boston, 02125, USA  Salvatore F.E. Oliviero
<EMAIL_ADDRESS>Physics Department, University of Massachusetts Boston,
02125, USA  Alioscia Hamma<EMAIL_ADDRESS>Dipartimento di Fisica
‘Ettore Pancini’, Università degli Studi di Napoli Federico II, Via Cintia
80126, Napoli, Italy  INFN, Sezione di Napoli, Italy

###### Abstract

In this paper, we present a learning algorithm aimed at learning states
obtained from computational basis states by Clifford circuits doped with a
finite number $t$ of $T$-gates. The algorithm learns an exact tomographic
description of $t$-doped stabilizer states in terms of Pauli observables. This
is possible because such states are countable and form a discrete set. To
tackle the problem, we introduce a novel algebraic framework for $t$-doped
stabilizer states, which extends beyond $T$-gates and includes doping with any
kind of local non-Clifford gate. The algorithm requires resources of
complexity $\operatorname{poly}(n,2^{t})$ and exhibits an exponentially small
probability of failure.

##  1 Introduction

The task of learning an unknown quantum state usually refers to the ability to
build a classical representation of the state that is “close” enough, based on
a specified measure of distance, to the unknown state. However, it is well
known that learning an arbitrary many-body quantum state requires an
exponential number of experiments due to the exponential growth of the Hilbert
space with the number of particles.

Let us be more precise and let us consider the Hilbert space of $n$ qubits and
denote $d\equiv 2^{n}$ its dimension. We can define the group of Pauli
operators as the collection of all possible products of Pauli matrices applied
to each qubit. Pauli tomography [1, 2, 3, 4, 5, 6] serves as a prevalent and
widely employed technique for learning a given state $\psi$. Specifically,
Pauli tomography entails acquiring knowledge about the expectation values
$\operatorname{tr}(P\psi)$ for every Pauli string $P$. To achieve a classical
reconstruction of the state vector $\psi$, a total of $d^{2}$ Pauli operators
must be measured and it becomes evident that tomography is generally a
resource-intensive task. The primary challenge in achieving efficiency in
quantum state tomography arises from our limited knowledge of the state of
interest. Nevertheless, there exist different classes of states, for which
tomography can be performed with remarkable efficiency, e.g. Matrix Product
States [2], quantum phase states [7], non-interacting fermionic states [8] and
stabilizer states [9]. The latter are obtained by the computational basis
state $\ket{0}^{\otimes n}$ by the action of the Clifford group – the subgroup
of the unitary group that sends Pauli operators in Pauli operators [9]. Each
stabilizer state $\ket{\sigma}$ corresponds to a stabilizer group
$G_{\sigma}$, a subgroup of the Pauli group, comprising $d$ mutually commuting
Pauli operators $P$ satisfying the condition $P\ket{\sigma}=\pm\ket{\sigma}$,
i.e. elements of the stabilizer group $G_{\sigma}$ stabilize the stabilizer
state $\ket{\sigma}$. Thus, to find the tomographic description of $\sigma$,
one needs to learn the stabilizer group $G_{\sigma}$ and the relative phases.
Every stabilizer group $G_{\sigma}$ admits (more than) a set of generators
$g_{\sigma}$, i.e. $G_{\sigma}=\langle g_{\sigma}\rangle$ with cardinality
$|g_{\sigma}|=n$. Thus, it is sufficient to find a set of $n$ generators and
phases to completely characterize $\sigma$. Montanaro [10] showed an algorithm
that learns the tomographic decomposition of any stabilizer state with $O(n)$
queries to $\ket{\sigma}$, thus gaining an exponential speed-up for stabilizer
states overall tomographic methods [11].

However, stabilizer states are not universal for quantum computation and
cannot provide quantum speed-up of any kind [12]. To make the set of
stabilizer states universal for quantum computation, one must use unitaries
that lie outside the Clifford group [13]. One common choice is to use the
single qubit $T$-gate defined as $T=\operatorname{diag}(1,e^{i\pi/4})$. States
obtained from $\ket{0}^{\otimes n}$ by the action of Clifford unitaries plus
$t$ $T$-gates are usually referred to as $t$-doped stabilizer states [14].

Whether Montanaro’s procedure could be extended to states beyond the
stabilizer formalism, in particular to $t$-doped stabilizer states, has been a
research question since then. There has been a noteworthy attempt in [15], in
which the authors cleverly discovered an extension of the stabilizer formalism
for those states obtained by a stabilizer state acting with a row of $t$
$T$-gates followed by a Clifford circuit: T-depth $1$ circuits. Such states
can be learned by $O(3^{t}n)$ query accesses and time $O(n^{3}+3^{t}n)$.
However, their protocol is limited only to those states achievable through a
specific architecture of Clifford$+T$ circuits.

In this paper, we finally show that it is possible to extend learning
algorithms to general states obtained by Clifford$+T$ unitaries. We propose an
innovative algebraic framework for $t$-doped stabilizer states by employing
concepts from stabilizer entropy. Building upon this newly established
structure, we devise two algorithms that aim at learning an unknown $t$-doped
stabilizer state exactly. The first one involves sampling from a distribution
$\Xi$ obtained by squaring the expectation values of Pauli operators, also
known as characteristic distribution, that can be achieved by a Bell sampling
on both the state and its conjugate in the computational basis [10]. The
second approach relaxes the requirement of accessing samples from the
characteristic distribution. Instead, it relies on the sampling from a
probability distribution $\tilde{\Xi}$ obtained by Bell measurements on two
copies of the state at a time, without the need to access its conjugate. A key
factor of both algorithms above is that, being limited in learning a discrete
set of states obtained by the action of Clifford+T circuits, they learn an
exact tomographic description in terms of Pauli observables.

To enhance clarity, we summarize the results on the sample and computational
complexity of both methods below. Since both algorithms have access to samples
from a probability distribution on Pauli operators, $\Xi$ and $\tilde{\Xi}$
respectively, in what follows we split the sample complexity coming from
sampling from such distributions from the sample complexity employed for
additional Pauli measurements, which we refer to as measurement shots.

######  Algorithm 1.

Assuming having access to sample from the characteristic distribution
$\Xi_{\psi_{t}}$, the algorithm that learns a exact classical description of
$t$-doped stabilizer state requires $O(2^{t}n+t2^{5t})$ $\Xi$-samples,
$O(2^{7t}+2^{4t}n(n+t))$ measurement shots, $O(4^{2t}n^{2})$ additional
computational steps, and fails with probability $O(n2^{-n})$.

######  Algorithm 2.

Having access to sample from
$\tilde{\Xi}_{\psi_{t}}=d^{-1}|\\!\braket{\psi_{t}}{P}{\psi_{t}^{*}}\\!|^{2}$,
the algorithm that learns a exact classical description of $t$-doped
stabilizer state requires $O(2^{6t}n)$ $\tilde{\Xi}$-samples,
$O(2^{9t}n(n+6t))$ measurement shots, $O(n^{2})$ additional computational
steps, and fails with probability $O(n2^{-n})$.

Furthermore, it is worth noting that for $t=0$, both algorithms reduce to
Montanaro’s algorithm.

##  2 Algebraic structure of $t$-doped stabilizer states

Denote $\mathbb{P}_{n}$ the Pauli group on $n$ qubits and $\mathcal{C}_{n}$
the Clifford group. We define $t$-doped Clifford unitaries, denoted as
$C_{t}$, unitary operators comprised of Clifford unitaries
$C\in\mathcal{C}_{n}$ plus $t$ $l$-qubits non-Clifford gates with $l=O(1)$.
Let $\ket{\psi_{t}}$ be a $t$-doped stabilizer state – i.e. a state obtained
as $\ket{\psi_{t}}=C_{t}\ket{0}^{\otimes n}$ – and let $\psi_{t}$ be its
density matrix. Define
$S_{\psi_{t}}:=\\{P\in\mathbb{P}_{n}\,|\,\operatorname{tr}(P\psi_{t})\neq
0\\}$ the set of Pauli operators with nonzero expectation over
$\ket{\psi_{t}}$. For a stabilizer state ($t=0$) $|S_{\psi_{0}}|=d$. Further,
one can define the probability distribution $\Xi_{\psi_{t}}$ with support on
$S_{\psi_{t}}$ and components
$\Xi_{\psi_{t}}(P)=\operatorname{tr}^{2}(P\psi_{t})/d$. We denote the
stabilizer entropy [16] of the state $\psi_{t}$ as
$M_{\alpha}(\psi_{t})=S_{\alpha}(\Xi_{\psi_{t}})-n$, that corresponds to the
Rényi entropy $S_{\alpha}(\Xi_{\psi_{t}})$ of order $\alpha$ of the
probability distribution $\Xi_{\psi}$ up to an offset $n$. As we shall see,
the stabilizer entropy can be operationally interpreted as the entropy of the
tomography in the Pauli basis.

Consider $M_{0}(\psi_{t})\equiv\log(|S_{\psi_{t}}|/d)$. One has
$M_{0}(\psi_{t})\leq 2lt$ [16] and thus $|S_{\psi_{t}}|\leq d2^{2lt}$.
Furthermore, a $t$-doped stabilizer state $\psi_{t}$ admits a stabilizer group
$G_{\psi_{t}}$ [17], i.e. a subgroup of $\mathbb{P}_{n}$ such that $\forall
P\in G_{\psi_{t}}$ $P\ket{\psi_{t}}=\pm\ket{\psi_{t}}$. However, unlike
stabilizer states, the stabilizer group of a generic $t$-doped stabilizer
state has a cardinality $|G_{\psi_{t}}|$ strictly less than $d$ and is bounded
from below

$\frac{d}{2^{2lt}}\leq|G_{\psi_{t}}|\leq d\,,$ (1)

i.e. the set of Pauli operators stabilizing a given $t$-doped state gets (at
most) halved every non-Clifford gate used to build $\ket{\psi_{t}}$ from
$\ket{0}^{\otimes n}$. Since $G_{\psi_{t}}$ is a subgroup of the Pauli group,
it is finitely generated and there exist $g_{1},\ldots,g_{m}$ generators, with
$m\equiv\log_{2}|G_{\psi_{t}}|$, such that every element $Q\in G_{\psi_{t}}$
can be obtained by a product of $g_{1},\ldots,g_{m}$ with relative phases
$\phi_{g_{1}},\ldots,\phi_{g_{m}}$ defined by
$g_{i}\ket{\psi_{t}}=\phi_{g_{i}}\ket{\psi_{t}}$. Since there are at most
$|S_{\psi_{t}}|\leq d2^{2lt}$ Pauli operators with nonzero expectation over
$\psi_{t}$ and at least $d/2^{2lt}$ of those stabilize $\ket{\psi_{t}}$, there
exist Pauli operators $h_{1},\ldots,h_{k}\in S_{\psi_{t}}$ ( $k\leq
4^{2lt}-1$) such that the set $S_{\psi_{t}}$ can be written as the union of
left disjoint cosets (see Appendix C.1)

$S_{\psi_{t}}=G_{\psi_{t}}\cup h_{1}G_{\psi_{t}}\cup\ldots\cup
h_{k}G_{\psi_{t}}\,.$ (2)

Throughout the manuscript, we refer to the coset representatives
$h_{1},\ldots,h_{k}$ as bad-generators of the $t$-doped stabilizer state
$\psi_{t}$. Note that the number $m$ of generators $g_{i}$ and the number $k$
of bad-generators $h_{i}$ must obey $2^{m}(k+1)=|S_{\psi_{t}}|$. Thanks to the
structure of $S_{\psi_{t}}$ in Eq. (2), a $t$-doped stabilizer state can be
expressed in the Pauli basis as

$\psi_{t}=\frac{1}{d}\sum_{i=0}^{k}\operatorname{tr}(h_{i}\psi_{t})h_{i}\prod_{j=1}^{m}\left({\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}+\phi_{g_{j}}g_{j}\right)\,,$ (3)

where $h_{0}\equiv{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}$. Notice that the operator
$\prod_{j=1}^{m}({\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}+\phi_{g_{j}}g_{j})=2^{m}\Pi_{\psi_{t}}$
is proportional to the projector $\Pi_{\psi_{t}}$ onto the stabilizer group
$G_{\psi_{t}}$, which automatically implies that bad generators commute with
every $P\in G_{\psi_{t}}$ to ensure hermiticity and positivity of $\psi_{t}$.
Through the decomposition in Eq. (3), we can easily derive the corollary of
the results in [18, 19] that will be useful later on. Define
$\mathcal{D}\in\mathcal{C}_{n}$ a Clifford operator that obeys
$\mathcal{D}^{{\dagger}}\Pi_{\psi_{t}}\mathcal{D}=\ket{0}\\!\\!\bra{0}^{\otimes
m}\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{[n-m]}$, where ${\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}_{[n-m]}$ denotes the identity on the last $n-m$ qubits. Then
since $h_{i}$ are coset representative and do commute with $\Pi_{\psi_{t}}$,
the following decomposition holds

$\ket{\psi_{t}}=\mathcal{D}(\ket{0}^{\otimes m}\otimes\ket{\phi})\,,$ (4)

where $\ket{\phi}$ is a state defined on the last $(n-m)$ qubits. The density
matrix associated to $\ket{\phi}$ can be written as
$\ket{\phi}\\!\\!\bra{\phi}=2^{n-m}\sum_{i=0}^{k}\operatorname{tr}(h_{i}\psi_{t})\tilde{h}_{i}$,
where $\tilde{h}_{i}\equiv\mathcal{D}^{{\dagger}}h_{i}\mathcal{D}$. To be
consistent with the terminology used in Refs. [18, 19], we refer to the
Clifford operator $\mathcal{D}$ as the diagonalizer.

As another consequence of Eq. (3), a direct computation of the stabilizer
entropy $M_{\alpha}(\psi_{t})$ returns
$M_{\alpha}(\psi_{t})=E_{\alpha}(\chi_{\psi_{t}})-\nu(\psi_{t})$, where
$\nu(\psi_{t})\equiv n-m$ is the stabilizer nullity introduced in [20], while
$E_{\alpha}(\chi_{\psi_{t}})$ is the $\alpha$-Rényi entropy of the probability
distribution $\chi_{\psi_{t}}$ with support on the cosets $h_{i}G_{\psi_{t}}$
and components
$\chi_{\psi_{t}}(h_{i})=\operatorname{tr}^{2}(h_{i}\psi_{t})|G_{\psi_{t}}|/d$.
The probability distribution $\chi_{\psi_{t}}$ can be interpreted as the
entropy of bad generators $h_{1},\ldots,h_{k}$, e.g.
$E_{0}(\psi_{t})=\log(k+1)$.

While all the results presented so far are general, let us conclude the
section by directing our attention toward $t$-doped stabilizer states
resulting from the application of Clifford+T circuits. For T-gates, the
previously derived bounds can be obtained by substituting $2l$ with $1$. As
these states form a discrete set, it is expected that the expectation values
of Pauli operators exhibit discrete values. Hence, there should exist a finite
resolution, strictly dependent on $t$, enabling one to exactly distinguish
these values by employing a sufficient number of samples. This intuition is
made rigorous in the following discussion. Consider a $t$-doped stabilizer
state obtained by the action of $t$ $T$-gates. Then, for every
$P,Q\in\mathbb{P}_{n}$, the following lower bound holds

$|\operatorname{tr}(P\psi_{t})-\operatorname{tr}(Q\psi_{t})|\geq\frac{\sqrt{2}}{6}\left(\frac{1}{\sqrt{2}}-\frac{1}{2}\right)^{t}$
(5)

provided that $\operatorname{tr}(P\psi_{t})\neq\operatorname{tr}(Q\psi_{t})$.
See Appendix C.4 for the proof. Therefore, for $t=O(\log n)$, the expectation
values of Pauli operators either coincide or exhibit a polynomial separation.
This fact will enable us to say that by employing a sufficient number of
samples – though polynomial in $n$ for $t=O(\log n)$ – to measure Pauli
expectation values, one can learn $t$-doped stabilizer states exactly. Let us
remark again that, contrary to all statements presented in the section, Eq.
(5) does not hold for the broader scenario of doping with $O(1)$-qubit non-
Clifford gates; rather, it specifically applies to the case involving
$T$-gates exclusively.

##  3 Learning algorithm from $\Xi_{\psi_{t}}$-samples

In the previous section, we explicitly revealed the algebraic structure of a
generic $t$-doped stabilizer state. Let us provide the algorithm able to learn
a $t$-doped stabilizer state. While the majority of our results can be
generalized to states doped by $l$-local non-Clifford gates (with $l=O(1)$),
we will focus our discussion on the $T$-gate case in order to employ the
finite resolution result in Eq. (5). In particular, a state $\psi_{t}$ doped
with a number $t$ of $T$-gates is characterized by $(i)$ $m\geq n-t$
generators $g_{i}$ of $G_{\psi_{t}}$ with $m$ relative phases $\phi_{g_{i}}$;
$(ii)$ by $k\leq 4^{t}-1$ bad generators $h_{i}$ with $k$ expectation values
$\operatorname{tr}(h_{i}\psi_{t})$. Therefore, the learning of a classical
description of a $t$-doped stabilizer state requires the knowledge of
$2m+2k\leq 2n+2\times 4^{t}$ objects, and therefore for $t=O(\log n)$ we have
$2m+2k=O(\operatorname{poly}(n))$111Essentially, the complexity stems from the
fact that the support $|S_{\psi_{t}}|\leq 2^{t}d$. However, it’s worth noting
that a weaker form of such a bound, i.e., $|S_{\psi_{t}}|\leq 3^{t}d$, was
previously demonstrated in Ref. [15]..

Let us assume to be able to sample from the distribution $\Xi_{\psi_{t}}$.
Later on, in Section 4, we discuss in which situations an efficient sampling
from $\Xi_{\psi_{t}}$ is possible by querying the $t$-doped state $\psi_{t}$.
We first aim to learn a basis for the stabilizer group $G_{\psi_{t}}$, i.e.
$m$ generators $g_{i}$. Sampling from $\Xi_{\psi_{t}}$ we get a Pauli operator
$P\in G_{\psi_{t}}$ with probability

$\operatorname{Pr}(P\in
G_{\psi_{t}})=\frac{|G_{\psi_{t}}|}{d}\geq\frac{1}{2^{t}}\,.$ (6)

Therefore, after $O(2^{t})$ samples one gets a Pauli operator sampled
uniformly from $G_{\psi_{t}}$ with high probability. To check whether a
sampled Pauli operator $P$ stabilizes $\ket{\psi_{t}}$ is sufficient to
measure $M$ times $P$. If all the measurement outcomes are equal, then $P\in
G_{\psi_{t}}$ with failure probability at most
$(1-2^{-t})(h_{\max}/2+1/2)^{M}$ (see Appendix C), where
$h_{\max}\equiv\max_{h_{i}}|\operatorname{tr}(h_{i}\psi_{t})|$. We remark that
the above procedure also reveals the stabilizing phase $\phi_{P}$
corresponding to $P\in G_{\psi_{t}}$. Following the reasoning introduced by
Montanaro [10], the extraction of $m+n$ random Pauli operators $\in
G_{\psi_{t}}$ suffices to identify a set of generators $g_{1},\ldots,g_{m}$
with failure probability at most $2^{-n}$. Indeed, determining a basis for
$G_{\psi_{t}}$ is equivalent to determining a basis for the $m$-dimensional
subspace $T$ of $\mathbb{F}_{2}^{2n}$; the probability that $n+m$ random
samples from $T$ lie in a $(m-1)$-dimensional subspace of $T$ is $2^{-m-n}$
and – by the union bound – the probability that these samples lie in one of
the $2^{m}$ $(m-1)$-dimensional subspaces of $T$ is at most $2^{-n}$. We
conclude that $O(2^{t}(n+m))$ samples from the probability distribution
$\Xi_{\psi_{t}}$, plus $O(2^{t}(n+m)M)$ additional measurement shots, are
sufficient to learn all the generators $g_{1},\ldots,g_{m}$ and phases
$\phi_{g_{i}}$ with failure probability
$O(2^{t}(n+m)(h_{\max}/2+1/2)^{M}+2^{-n})$.

At this point, let us learn the $k$ bad generators $h_{1},\ldots,h_{k}$.
Suppose the algorithm already found $l$ out of $k$ bad generators, say
$h_{1},\ldots,h_{l}$. To find the $(l+1)$-th bad generator, we keep sampling
from $\Xi_{\psi_{t}}$. The probability $\pi_{l}$ that the sampled Pauli
operator $P$ does not belong to $G_{\psi_{t}}\cup
h_{1}G_{\psi_{t}}\cup\ldots\cup h_{l}G_{\psi_{t}}$ is

$\pi_{l}=1-\frac{|G_{\psi_{t}}|}{d}\left(1+\sum_{i=1}^{l}\operatorname{tr}^{2}(h_{i}\psi_{t})\right)\,.$
(7)

To find a useful lower bound to $\pi_{l}$, let us exploit the unit purity of
the state $\psi_{t}$. In Appendix C, we obtain

$\pi_{l}\geq|G_{\psi_{t}}|(k-l)h_{\min}^{2}/d$ (8)

with $h_{\min}:=\min_{h_{i}}|\operatorname{tr}(h_{i}\psi_{t})|$. However, a
learner needs an efficient way to check whether a sampled Pauli operator
belongs to $G_{\psi_{t}}\cup h_{1}G_{\psi_{t}}\cup\ldots\cup
h_{l}G_{\psi_{t}}$. Let us provide a simple algorithm to efficiently check
whether a Pauli operator $P$ belongs to $G_{\psi_{t}}\cup
h_{1}G_{\psi_{t}}\cup\ldots\cup h_{l}G_{\psi_{t}}$ or not. Let us assume $P\in
h_{0}G_{\psi_{t}}\cup h_{1}G_{\psi_{t}}\cup\cdot\cup h_{l}G_{\psi_{t}}$, where
$h_{0}={\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}$. Then for some $i\in 0\ldots l$, there
exists $h_{i}$ such that $h_{i}P\in G_{\psi_{t}}$. Thus the problem reduces to
check if there exists an $h_{i}\in\\{h_{0},\ldots,h_{l}\\}$ such that
$h_{i}P\in G_{\psi_{t}}$. The latter can be solved by adding $h_{i}P$ to a
generating set $G_{\psi_{t}}$ and performing Gaussian elimination over
$\mathbb{F}_{2}^{2n}$. The task requires $O(n^{3})$ steps and has to be
repeated $l$ times, meaning that the full task requires $O(n^{3}l)$
computational steps, and so to learn all the $k$ bad generators one needs
$O(n^{3}k^{2})$. In appendix B we provide a slightly more efficient algorithm
relying instead on the notion of diagonalizer[18, 19] where the number of
computational steps to verify the containment of one bad generator is
$O(n^{2}k)$, and so reducing the computational steps to learn all the bad
generators to $O(n^{2}k^{2})$. The total number of samples scales as
$\sum_{l=0}^{k-1}\pi_{l}^{-1}\leq
2^{t}h_{\min}^{-2}\sum_{l=0}^{k-1}(k-l)^{-1}\leq
2^{t}h_{\min}^{-2}(\gamma+\log(k+1))$ for $\gamma$ being the Euler’s constant.
Therefore using $O\left(2^{t}h_{\min}^{-2}\log(k+1)\right)$ samples from
$\Xi_{\psi_{t}}$, plus $O(n^{2}k^{2})$ computational steps, one learns the $k$
bad generators $h_{1},\ldots,h_{k}$. To evaluate $h_{\min}$ and $h_{\max}$,
let us recall that the state $\ket{\psi_{t}}$ is obtained from the
computational basis state $\ket{0}^{\otimes n}$ by a Clifford circuit polluted
with $t$ single qubit $T$-gates, that generate a discrete set of states, which
ultimately implies the existence of a finite resolution
$\delta_{t}\equiv\min|\operatorname{tr}[(P-Q)\psi_{t}]|$ for
$\operatorname{tr}(P\psi_{t})\neq\operatorname{tr}(Q\psi_{t})$. From Eq. (5),
one has $\delta_{t}=\Omega(2^{-bt})$ for $b\simeq 2.27$. Therefore
$O(2^{2bt})$ measurement shots are sufficient to determine the expectation
value $\operatorname{tr}(h_{i}\psi_{t})$ exactly. In addition, one has
$h_{\min}=\Omega(2^{-bt})$ and $h_{\max}<1-O(2^{-bt})$. In summary, to learn
$k$ bad generators and the corresponding expectations, the learner employs
$O(2^{(2b+1)t}\log(k+1))$ samples from $\Xi_{\psi_{t}}$, $O(k2^{2bt})$
measurement shots, and $O(n^{2}k^{2})$ additional computational steps.

Let us count the total number of resources to learn a $t$-doped stabilizer
state employing the algorithm proposed above. Set $m\leq n$, $k<4^{t}$, $b<3$
and $M=2^{3t+1}(n+t)$. The total number of samples from the probability
distribution $\Xi_{\psi_{t}}$ is $O(2^{t}n+t2^{5t})$ plus $O(4^{t}n^{2})$
additional computational steps. The total number of measurement shots is
$O(2^{7t}+2^{4t}n(n+t))$ and the algorithm fails with probability at most
$O(n2^{-n})$. Therefore for $t=O(\log n)$, the algorithm learns the
tomographic description of a $t$-doped stabilizer state of Eq. (3) with
polynomial resources and overwhelming probability.

##  4 Sampling from $\Xi_{\psi_{t}}$

In Section 3, we provided an algorithm that learns a $t$-doped stabilizer
state with $\operatorname{poly}(n,2^{t})$ resources. In particular, the
algorithm uses $O(2^{t}n+t2^{5t})$ samples from the probability distribution
$\Xi_{\psi_{t}}$ with elements
$\Xi_{\psi_{t}}(P)=\operatorname{tr}^{2}(P\psi_{t})/d$. Let us discuss the
connection between queries to the unknown state $\ket{\psi_{t}}$ and samples
from the distribution $\Xi_{\psi_{t}}$. Having query access to the $t$-doped
stabilizer state $\ket{\psi_{t}}$ and its conjugate (in the computational
basis) $\ket{\psi_{t}^{*}}$, one can easily achieve the task via Bell
sampling. Define the Bell basis on two copies of Hilbert space $\mathcal{H}$
as $\ket{P}\equiv{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\otimes P\ket{{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$
with $\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}}=2^{-n/2}\sum_{i=1}^{2^{n}}\ket{i}\otimes\ket{i}$ and
$P\in\mathbb{P}_{n}$. Then, measuring $\ket{\psi_{t}\otimes\psi_{t}^{*}}$ in
the basis $\ket{P}$ is equivalent to sample from the distribution
$\Xi_{\psi_{t}}$:

$\operatorname{Pr}(\ket{\psi_{t}\otimes\psi_{t}^{*}}\mapsto\ket{P})=\Xi_{\psi_{t}}(P)\,.$
(9)

Therefore a single query to $\ket{\psi_{t}}$ and its conjugate
$\ket{\psi_{t}^{*}}$ suffices to obtain one sample from the distribution
$\Xi_{\psi_{t}}$.

At this point, the careful reader may wonder how the learner can prepare the
conjugate state $\ket{\psi_{t}^{*}}$ in order to use the algorithm. We have a
manifold of answers to this. First of all, an important situation in which
learning is important is that of the study of ground states of quantum many-
body systems. Generically, as long as time-reversal is not broken, these are
real states, and thus $\ket{\psi_{t}^{*}}=\ket{\psi_{t}}$. An example is
provided by stabilizer Hamiltonians [21] perturbed by local impurities.
Moreover, in many scenarios, the preparation itself of the state
$\ket{\psi_{t}}$ can be thought of as made by a quantum circuit. In this case
then, the task of preparing $\ket{\psi_{t}^{*}}$ is straightforward. Indeed,
it is sufficient to replace the gate $S=\operatorname{diag}(1,i)$ with
$S^{*}=\operatorname{diag}(1,-i)$ and the $T$-gate with $TS^{*}$ to obtain
$U_{t}^{*}$ and thus constructing $\ket{\psi_{t}^{*}}$ from $\ket{0}^{\otimes
n}$.

In any case, while distilling the conjugate state is a hard task in general,
the states under examination in this paper for which the learning is
efficient, i.e. $t$-doped stabilizer states with $t=O(\log n)$, have a fine
structure and all the hardness proofs fail at capturing the hardness of
distilling $\ket{\psi_{t}^{*}}$ from samples of $\ket{\psi_{t}}$. Indeed, from
the knowledge of the algebraic structure in Eq. (3), sampling from the
characteristic distribution is straightforward: it is sufficient to flip a
$k$-faceted dice with probabilities $\chi_{\psi_{t}}(h_{i})$ – defined above
in Section 2 – and outcomes $h_{i}$, and uniformly sample a Pauli operator
$P\in G_{\psi_{t}}$ through $m$ generators. As a result, one samples a Pauli
operator $h_{i}P$ according to $\Xi_{\psi_{t}}$. This procedure is readily
efficient for $k=O(\operatorname{poly}(n))$, i.e. for $t=O(\log(n))$.
Therefore, there is no reason to believe that sampling from the distribution
$\Xi_{\psi_{t}}$, with queries limited to $\ket{\psi_{t}}$ alone and without
knowing the algebraic structure (3) (i.e. bypassing the a priori learning of
the $t$-doped stabilizer state), is hard and, as such, it remains an ongoing
subject of research.

##  5 Learning algorithm without access to $\Xi_{\psi_{t}}$

We discussed a simple and intuitive learning algorithm that works whenever one
has access to samples from the distribution $\Xi_{\psi_{t}}$. However, as we
saw in Section 4, known methods for sampling from $\Xi_{\psi_{t}}$ require
query access to the $t$-doped stabilizer state and its conjugate in the
computational basis, which is not always available in real scenarios. In this
section, we present an algorithm that is similar in spirit to the one in
Section 3, but we relax the hypothesis of having samples from
$\Xi_{\psi_{t}}$.

As measuring $\ket{\psi_{t}\otimes\psi_{t}^{*}}$ in the Bell basis $\ket{P}$
returns samples from $\Xi_{\psi_{t}}$, measuring
$\ket{\psi_{t}\otimes\psi_{t}}$ in the Bell basis returns samples from

$\widetilde{\Xi}_{\psi_{t}}(P)\equiv\frac{|\braket{\psi_{t}}{P}{\psi_{t}^{*}}|^{2}}{d}\,.$
(10)

Let us show that samples from $\widetilde{\Xi}_{\psi_{t}}$ are still
sufficient to learn the stabilizer group $G_{\psi_{t}}$ and, ultimately, the
$t$-doped stabilizer state $\psi_{t}$ exactly. To see this, it is useful to
show how the algebraic structure changes from $\psi_{t}$ to $\psi_{t}^{*}$.
Naively, from Eq. (3), we can write the density matrix associated to
$\psi_{t}^{*}$ as

$\psi_{t}^{*}=\frac{1}{d}\sum_{i=0}^{k}\operatorname{tr}(h_{i}\psi_{t}^{*})h_{i}\prod_{j=1}^{m}({\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}+\phi_{g_{j}}g_{j}^{*})\,.$ (11)

To understand the algebraic structure of $\psi_{t}^{*}$, it is useful to look
back at the simple case of stabilizer states, i.e. $t=0$. As shown by
Montanaro in Ref. [10], given a stabilizer state $\ket{\sigma}$, its conjugate
$\ket{\sigma^{*}}$ can be obtained with a Pauli rotation as
$\ket{\sigma^{*}}=P_{\sigma}\ket{\sigma}$ for some Pauli operator
$P_{\sigma}$. Similarly, since the projector $\Pi_{\psi_{t}}$ in Eq. (3), onto
the stabilizer group $G_{\psi_{t}}$, can be completed to represent a pure
stabilizer state (by completion of the stabilizer group $G_{\psi_{t}}$), it is
immediate to see that there exist a Pauli operator $P_{\psi_{t}}$ such that

$P_{\psi_{t}}\Pi_{\psi_{t}}P_{\psi_{t}}=\Pi_{\psi_{t}}^{*}\,,$ (12)

where $\Pi_{\psi_{t}}^{*}\equiv 2^{-m}\prod_{j=1}^{m}({\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}+\phi_{g_{j}}g_{j}^{*})$. In other words, analogously to the
case of stabilizer states, the projectors onto the stabilizer groups
$\Pi_{\psi_{t}},\Pi_{\psi_{t}}^{*}$, of $\psi_{t}$ and $\psi_{t}^{*}$
respectively, can be obtained from one another by the application of a Pauli
operator $P_{\psi_{t}}$. Hence, the state
$\ket{\psi_{t}^{*\prime}}:=P_{\psi_{t}}\ket{\psi_{t}^{*}}$ has the same
stabilizer group $G_{\psi_{t}}$ of $\psi_{t}$, by construction.

As explained in Section 2, from the projector $\Pi_{\psi_{t}}$ onto the
stabilizer group $G_{\psi_{t}}$, one can define a diagonalizer $\mathcal{D}$.
Since the stabilizer groups are the same, $\mathcal{D}$ diagonalize
$\ket{\psi_{t}}$ and $\ket{\psi_{t}^{*\prime}}$ at the same time as
$\mathcal{D}\ket{\psi_{t}}=\ket{0}^{\otimes m}\otimes\ket{\phi}$ and
$\mathcal{D}\ket{\psi_{t}^{*\prime}}=\ket{0}^{\otimes
m}\otimes\ket{\phi^{*}}$, cfr. Eq. (4). By simple manipulations, we can thus
rewrite the probability in Eq. (10) as only depending on the nonstabilizer
part $\ket{\phi}$ of the $t$-doped stabilizer state $\ket{\psi_{t}}$ as

$\widetilde{\Xi}_{\psi_{t}}(P)=\frac{|\braket{\phi}{\bar{P}}{\phi^{*}}|^{2}}{d}\,,$
(13)

with $\bar{P}\equiv\braket{0^{\otimes
m}}{\mathcal{D}^{{\dagger}}PP_{\psi_{t}}\mathcal{D}}{0^{\otimes m}}$. It is
easy to be convinced that the probability $\tilde{\Xi}_{\psi_{t}}(P)$ is
different from zero only if
$\mathcal{D}^{{\dagger}}PP_{\psi_{t}}\mathcal{D}\in({\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}_{m}\otimes\bar{P})G_{\psi_{t}}$ for any
$\bar{P}\in\mathbb{P}_{n-m}$ living on the last $(n-m)$ qubits. Hence, samples
from $\widetilde{\Xi}_{\psi_{t}}(P)$ returns Pauli operators
$P\in\\{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}_{m}\otimes\bar{P}G_{\psi_{t}}\,|\,\bar{P}\in\mathbb{P}_{n-m}\\}$
with probability (13). As in the case of stabilizer states, to gain knowledge
of the stabilizer group $G_{\psi_{t}}$, it is sufficient to obtain two Pauli
operators $P,P^{\prime}$ belonging to the same left coset
$P,P^{\prime}\in({\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{m}\otimes\bar{P})G_{\psi_{t}}$, and
consider the product $PP^{\prime}\in G_{\psi_{t}}$. At this point, the joint
probability that two samples give a product Pauli operator belonging to
$G_{\psi_{t}}$ is lower bounded by

$\operatorname{Pr}(PP^{\prime}\in G_{\psi_{t}})\geq\frac{1}{2^{6t}}$ (14)

where the proof is in Appendix D. Therefore, by repeating the reasoning
outlined in Section 3 after Eq. (6), we conclude that $O(2^{6t}(n+m))$ samples
from $\widetilde{\Xi}_{\psi_{t}}$, plus $O(2^{9t}n(n+6t))$ additional
measurement shots, are sufficient to learn all the generators
$g_{1},\ldots,g_{m}$ and phases $\phi_{g_{i}}$ with exponentially small
probability of failure $O(n2^{-n})$.

Having learned the generators $g_{i}$ and relative phases $\phi_{g_{i}}$, it
is thus possible, through standard tableau manipulation techniques (see Ref.
[18]), to construct and distill the diagonalizer $\mathcal{D}$ in Eq. (4)
using $O(n^{2})$ computational steps and up to $O(n)$ Clifford gates [22].
Applying $\mathcal{D}^{{\dagger}}$ on the $t$-doped stabilizer state
$\ket{\psi_{t}}$, one gets
$\mathcal{D}^{{\dagger}}\ket{\psi_{t}}=\ket{0}^{\otimes m}\otimes\ket{\phi}$.
At this point, one is left to learn the tomographic description of
$\ket{\phi}$ in terms of Pauli operators
$\tilde{h}_{i}\equiv\mathcal{D}^{{\dagger}}h_{i}\mathcal{D}$. To achieve this
task, it is sufficient to measure each Pauli operator $\tilde{h}_{i}$ for
$i=1,\ldots,k$ individually. In virtue of Eq. (5), to estimate the expectation
values $\operatorname{tr}(h_{i}\psi_{t})$ exactly, $O(2^{2bt})$ samples are
sufficient, and thus, to learn the expectation values of $k$ bad generators
$h_{i},\ldots,h_{k}$ one needs $O(4^{t}2^{2bt})$ total measurement shots. In
summary, the above algorithm learns an exact tomographic description of a
$t$-doped stabilizer state using $O(2^{6t}n)$ samples from the distribution
$\tilde{\Xi}$ (which in turn can be obtained by measuring $2$ copies of
$\psi_{t}$ in the basis $\ket{P}$), $O(2^{9t}n(n+6t))$ measurement shots,
$O(n^{2})$ additional computational steps, and fails with probability
$O(n2^{-n})$.

The careful reader might have noticed similarities between the procedure
outlined above and the subroutine known as Bell difference sampling [23],
where one considers two samples from the distribution
$\widetilde{\Xi}_{\psi_{t}}$ and, subtracting the results, obtain sample Pauli
operators $P\in
G_{\psi_{t}}^{\perp}=\\{P\in\mathbb{P}\,|\,[P,G_{\psi_{t}}]=0\\}$ whose
knowledge allows to reconstruct the stabilizer group $G_{\psi_{t}}$, as shown
in [24]. There are two key insights here: first, the derivation outlined above
solely descends from the algebraic structure of $t$-doped stabilizer states
developed in this paper that provide a simple proof of the results. Secondly,
the algorithm outlined above and the Bell difference sampling routine exhibit
similarities, yet they are not entirely identical. Specifically, the above
algorithm exclusively accommodates pairs of Pauli operators, denoted as $P$
and $P^{\prime}$, whose product resides within $G_{\psi_{t}}\subset
G_{\psi_{t}}^{\perp}$. Hence, it does not need any classical postprocessing.
This fact allows for the complete and precise determination of the stabilizer
group $G_{\psi_{t}}$ with overwhelming probability, albeit at the expense of
an exponential increase in computational cost with respect to $t$, a scaling
that Bell difference sampling does not possess.

##  6 Concurrent work

During the finalization of this manuscript, we became aware of two works [24,
25] sharing several similarities with ours, presenting an efficient approach
for learning $t$-doped stabilizer states. This section aims to compare
algorithms. The algorithms presented separately in [24] and [25] are quite
similar. Hence, we focus on comparing the one from [24] with ours for
simplicity.

The algorithm in [24] has a significant advantage: it uses Bell difference
sampling to approximate the stabilizer group $G_{\psi_{t}}$ associated with
the $t$-doped stabilizer state $\ket{\psi_{t}}$ using $O(n)$ resources,
avoiding exponential scaling with the number $t$ of non-Clifford gates.
However, it only learns an approximate version of the stabilizer group, which
might not suit cases where an exact description of a $t$-doped stabilizer
state is required. For T-gates, exact learning is desirable since these states
are countable and form a discrete set. The algorithm presented in Section 5 of
this paper, leveraging the algebraic structure introduced here, can precisely
learn the stabilizer group $G_{\psi_{t}}$ from copies of $\ket{\psi_{t}}$,
with an exponentially small probability of failure. However, this precise
learning comes at the cost of exponential resource scaling with the number of
T-gates. Compared to the algorithm in [24], our algorithm’s primary strength
lies in its exact learning ability for states created by Clifford+T circuits,
enabled by Eq. (5). Both algorithms in Section 3 and 5, with different
methods, whose limitations have been explored above, achieve the exact
learning of the fine algebraic structure of $t$-doped stabilizer state
displayed in Eq. (3). However, it’s important to note that these states are
not the only ones with polynomially many bad generators, and therefore our
algorithms do not cover the larger class of states learnable according to the
algorithm in Ref. [24], which, in this regard, is more general. Overall, we
conclude that the two algorithms exhibit distinct ranges of applicability,
each with its own set of strengths and limitations.

##  7 Conclusions

In conclusion, we presented an efficient and general algorithm that can learn
a classical description of states obtained from the computational basis by the
action of the Clifford group plus a few $T$ gates. To address this challenge,
we introduced a new algebraic structure for $t$-doped stabilizer states that
is of independent interest and plays a crucial role in the learning algorithm.

In perspective, there are several open questions. First, we ask whether the
algebraic structure presented in this paper can be instrumental in solving
tasks beyond quantum state tomography for $t$-doped stabilizer state, e.g. in
computing quantity as entanglement or magic. Second, we would like to know
whether the knowledge of both the generators and the bad generators can be
utilized to synthesize a Clifford+$T$ circuit able to construct the state
$\ket{\psi_{t}}$ from $\ket{0}^{\otimes n}$. Indeed, note that the task is
conceivable for two reasons: 1) because the complexity (i.e. the number of
gates) of Clifford$+T$ circuits scales as $O(n+t^{2})$ 222By Theorem $2$ of
[18] a Clifford+$T$ circuit $C_{t}$ with $t\leq n$ has the following
decomposition $C_{t}=C_{1}({\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\otimes u_{t})C_{2}$,
with $C_{1},C_{2}\in\mathcal{C}_{n}$ and $u_{t}$ a $t$-doped Clifford circuit
on $t$-qubits consisting of at most $t$ many $T$ gates. By Lemma $8$ from
[22], any Clifford circuit can be implemented with at most $9n$ gates. Thus,
$\\#(C_{i})\leq 9n$ for $i,1,2$ and $\\#(u_{t})\leq(9t+1)t=O(t^{2})$, and
consequently the total complexity is $O(n+t^{2})$ as a consequence of the
results of [19, 18, 22]; 2) given a $t$-doped stabilizer state, one can learn
exactly the Clifford circuit $\mathcal{D}$, reducing the task of learning the
circuit description to $u_{t}$ only. Lastly, the estimated resources are
computed for the worst case. We ask whether the average case complexity for
the exact learning of $t$-doped stabilizer states doped with $T$-gates is more
favorable in terms of the exponential scaling in $t$.

## Acknowledgments

The authors acknowledge discussions with M. Hinsche, M. Ioannou, S. Jerbi, J.
Carrasco and G. Esposito. The authors would like to express their gratitude to
Daniel Miller for his valuable insight regarding the existence of a finite
resolution for t-doped stabilizer states. The authors thank the anonymous
Reviewer $1$ for their constructive comments and suggestions that helped to
improve the manuscript. Special thanks go to Lennart Bittel for fundamental
inceptions for the proof of the lower-bound in Eq. (5). AH was supported by
the ENEA project I53C22003030001, the PNRR MUR project PE0000023-NQSTI and
PNRR MUR project CN $00000013$-ICSC. L.L. S.O. acknowledge support from NSF
award number 2014000. L.L. and S.O. contributed equally to this work.

## References

  * [1] M. Paris and J. Řeháček, eds.,  _Quantum State Estimation_ , vol. 649 of _Lecture Notes in Physics_ ,  Springer, Berlin, Heidelberg,  ISBN 978-3-540-22329-0 978-3-540-44481-7,  doi:10.1007/b98673 (2004).
  * [2] M. Cramer, M. B. Plenio _et al._ ,  _Efficient quantum state tomography_ ,  Nature Communications 1(1), 149 (2010),  doi:10.1038/ncomms1147.
  * [3] D. Gross, Y.-K. Liu _et al._ ,  _Quantum State Tomography via Compressed Sensing_ ,  Physical Review Letters 105, 150401 (2010),  doi:10.1103/PhysRevLett.105.150401.
  * [4] S. Aaronson,  _Shadow Tomography of Quantum States_ ,  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 325–338–325–338. Association for Computing Machinery,  doi:10.1145/3188745.3188802 (2018).
  * [5] C. Huang, F. Zhang _et al._ ,  _Classical simulation of quantum supremacy circuits_ ,  arxiv (2020),  [Arxiv:2005.06787].
  * [6] H.-Y. Huang, R. Kueng and J. Preskill,  _Predicting many properties of a quantum system from very few measurements_ ,  Nature Physics 16(10), 1050 (2020),  doi:10.1038/s41567-020-0932-7.
  * [7] S. Arunachalam, S. Bravyi _et al._ ,  _Optimal algorithms for learning quantum phase states_ ,  arxiv,  doi:10.48550/arXiv.2208.07851 (2023),  [quant-ph/2208.07851].
  * [8] S. Aaronson and S. Grewal,  _Efficient Tomography of Non-Interacting Fermion States_ ,  arxiv,  doi:10.48550/arXiv.2102.10458 (2023),  [quant-ph/2102.10458].
  * [9] D. Gottesman,  _The Heisenberg Representation of Quantum Computers_ ,  arxiv,  doi:10.48550/arXiv.quant-ph/9807006 (1998),  [Arxiv:quant-ph/9807006].
  * [10] A. Montanaro,  _Learning stabilizer states by Bell sampling_ ,  arxiv,  doi:10.48550/arXiv.1707.04012 (2017),  [quant-ph/1707.04012].
  * [11] D. Bruß and C. Macchiavello,  _Optimal state estimation for d-dimensional quantum systems_ ,  Physics Letters A 253(5), 249 (1999),  doi:10.1016/S0375-9601(99)00099-7.
  * [12] D. Gottesman,  _Theory of fault-tolerant quantum computation_ ,  Physical Review A 57, 127 (1998),  doi:10.1103/PhysRevA.57.127.
  * [13] D. Gottesman,  _Stabilizer Codes and Quantum Error Correction_ ,  Ph.D. thesis, California Institute of Technology (1997/january).
  * [14] S. F. E. Oliviero, L. Leone and A. Hamma,  _Transitions in entanglement complexity in random quantum circuits by measurements_ ,  Physics Letters A 418, 127721 (2021),  doi:10.1016/j.physleta.2021.127721.
  * [15] C.-Y. Lai and H.-C. Cheng,  _Learning Quantum Circuits of Some T Gates_ ,  IEEE Transactions on Information Theory 68(6), 3951 (2022),  doi:10.1109/tit.2022.3151760.
  * [16] L. Leone, S. F. E. Oliviero and A. Hamma,  _Stabilizer Rényi Entropy_ ,  Physical Review Letters 128, 050402 (2022),  doi:10.1103/PhysRevLett.128.050402.
  * [17] J. Jiang and X. Wang,  _Lower bound the T-count via unitary stabilizer nullity_ ,  arxiv,  doi:10.48550/arXiv.2103.09999 (2021),  [hep-th, physics:quant-ph/2103.09999].
  * [18] L. Leone, S. F. E. Oliviero _et al._ ,  _Learning efficient decoders for quasi-chaotic quantum scramblers_ ,  arxiv,  doi:10.48550/arXiv.2212.11338 (2022),  [quant-ph/2212.11338].
  * [19] S. F. E. Oliviero, L. Leone _et al._ ,  _Black Hole complexity, unscrambling, and stabilizer thermal machines_ ,  arxiv,  doi:10.48550/arXiv.2212.11337 (2022),  [gr-qc, physics:hep-th, physics:quant-ph/2212.11337].
  * [20] M. Beverland, E. Campbell _et al._ ,  _Lower bounds on the non-Clifford resources for quantum computations_ ,  Quantum Science and Technology 5(3), 035009 (2020),  doi:10.1088/2058-9565/ab8963.
  * [21] N. J. Coble, M. Coudron _et al._ ,  _Hamiltonians whose low-energy states require $\Omega(n)$ T gates_,  arxiv (2023),  [quant-ph/2310.01347].
  * [22] S. Bravyi and D. Maslov,  _Hadamard-Free Circuits Expose the Structure of the Clifford Group_ ,  IEEE Transactions on Information Theory 67(7), 4546 (2021),  doi:10.1109/TIT.2021.3081415.
  * [23] D. Gross, S. Nezami and M. Walter,  _Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations_ (2019).
  * [24] S. Grewal, V. Iyer _et al._ ,  _Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates_ ,  arxiv,  doi:10.48550/arXiv.2305.13409 (2023),  [quant-ph/2305.13409].
  * [25] D. Hangleiter and M. J. Gullans,  _Bell sampling from quantum circuits_ ,  arxiv,  doi:10.48550/arXiv.2306.00083 (2023),  [cond-mat, physics:quant-ph/2306.00083].
  * [26] M. R. Murty and P. Rath,  _Liouville’s Theorem_ ,  In M. R. Murty and P. Rath, eds., _Transcendental Numbers_ , pp. 1–6. Springer, New York, NY,  ISBN 978-1-4939-0832-5,  doi:10.1007/978-1-4939-0832-5\\_1 (2014).

##  Appendix A Technical preliminaries

In this section, we will introduce some technical preliminaries that may prove
beneficial to the reader.

###  A.1 Pauli Group, Clifford group, and stabilizer states

The Pauli group $\mathcal{P}_{n}$ is the $n$-tensor fold product of the
single-qubit Pauli group $\mathcal{P}_{1}$, which consists of the elements
${{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}},X,Y,Z}$, each multiplied by a scaling factor of ${\pm 1,\pm
i}$, where $X,Y$ and $Z$ are the standard single-qubit Pauli matrices. Let us
introduce the quotient group $\mathbb{P}_{n}$ of the Pauli group
$\mathbb{P}:=\mathcal{P}/\\{\pm 1,\pm i\\}\,$. In the main text, we refer to
the quotient group as Pauli group. The Clifford group $\mathcal{C}(n)$ on $n$
qubit, i.e. a subgroup of the unitary group is defined as the normalizer of
the Pauli group $\mathcal{P}_{n}$:

$\mathcal{C}_{n}:=\\{C\in\mathcal{U}(n)\,\,\,|\,\,\,C^{{\dagger}}PC\in\mathcal{P},\quad\forall
P\in\mathcal{P}_{n}\\}.$ (15)

With the notion of Pauli and Clifford group, one can then define the notion of
a stabilizer state. Given a Pauli operator $P\in\mathbb{P}_{n}$, we say that
$P$ stabilizes the state $\ket{\psi}$ if

$P\ket{\psi}=\pm\ket{\psi}$ (16)

A state $\ket{\sigma}$ is a stabilizer states if $\ket{\sigma}$ is stabilized
by an group $G$ of $d$ commuting Pauli operators

$P\ket{\sigma}=\pm\ket{\sigma}\quad\forall P\in G$ (17)

Equivalently, one can define a stabilizer state as $\ket{\sigma}\equiv
C\ket{0}^{\otimes n}$ with $C\in\mathcal{C}_{n}$. It is noteworthy to notice
that a stabilizer state can be written as an equal superposition of Pauli
operators that stabilizes it

$\sigma=\frac{1}{d}\sum_{P\in G}\sigma_{P}P$ (18)

where $\sigma$ is the density matrix associated to $\ket{\sigma}$ and
$\sigma_{p}=\pm 1$ is the phase associated to $P$. Being $G$ an Abelian group,
there exists a set of generators $S\equiv\\{g_{1},\ldots,g_{n}\\}$ such that
$G=\langle S\rangle$. Thus, given $S$ the set of generators associate with $G$
the state $\sigma$ can be expressed in terms of the generator $g_{i}\in S$ as

$\sigma=\prod_{i}\left(\frac{{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}+\phi_{g_{i}}g_{i}}{2}\right)$ (19)

where $\phi_{g_{i}}$ are the $\pm 1$ phases associated with the generators
$g_{i}$s.

###  A.2 Bell Sampling

In this section, we will review the concept of Bell sampling [10] and its
application in learning a stabilizer state. To grasp the idea behind Bell
sampling, let’s begin by considering the $2$-qubit maximally entangled state,
denoted as $\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$, which is defined as
$(\ket{00}+\ket{11})/\sqrt{2}$. If we apply the operator ${\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}\otimes P$, where $P={{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}},X,Y,Z}$, to the state
$\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$, we obtain the set of states:
$\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$,
$\ket{X}=(\ket{01}+\ket{10})/\sqrt{2}$,
$\ket{Y}=(\ket{01}-\ket{10})/\sqrt{2}$, and
$\ket{Z}=(\ket{00}-\ket{11})/\sqrt{2}$. This set of states corresponds to the
$2$-qubit Bell basis. This equivalence between Pauli operators and states can
be extended to the $n$-qubit case. The reason behind this extension lies in
the fact that the $n$-qubit Pauli group is constructed as the $n$-fold tensor
product of the $1$-qubit Pauli group. Consequently, we can tensor $2$-qubit
states $\ket{P}$ to establish an equivalence between the $n$-qubit Pauli group
and the $2n$-qubit Bell basis. In this context, a generic basis element can be
written as $\ket{P}\equiv{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\otimes
P\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$, where $\ket{{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$
denotes the $2n$-qubit maximally entangled state, defined as
$\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}}=2^{-n/2}\sum_{i}^{d}\ket{i}\otimes\ket{i}$. Let us consider
the state $\ket{\psi^{*}}\otimes\ket{\psi}$, it is not difficult to show that
measuring in the Bell basis return outcome $P$ with probability
$\operatorname{tr}(P\psi)^{2}/d$, with $\psi$ the density matrix associated to
the state $\psi$. The probability to obtain $P$ is given by
$|\braket{P}{\psi^{*}\otimes\psi}|^{2}$

$\displaystyle|\braket{P}{\psi^{*}\otimes\psi}|^{2}$ $\displaystyle=$
$\displaystyle\braket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}{{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\otimes
P[\psi^{*}\otimes\psi]{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\otimes P}{{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$
(20) $\displaystyle=$ $\displaystyle\braket{{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}}{{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\otimes P\psi P\psi}{{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$
(21) $\displaystyle=$ $\displaystyle\operatorname{tr}(P\psi
P\psi)/2^{n}=\operatorname{tr}(P\psi)^{2}/2^{n}$ (22)

where we used the properties of the maximally entangled state that
$O\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}={\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}\otimes O^{T}\ket{{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}}$, and that the state
$\psi$ is pure. If instead of having access to
$\ket{\psi^{*}}\otimes\ket{\psi}$ one has instead access to
$\ket{\psi}\otimes\ket{\psi}$ the probability of sampling $P$ is given by
$|\braket{\psi}{P}{\psi^{*}}|^{2}/2^{n}$. Through Bell sampling, one can learn
a stabilizer state $\ket{\sigma}$ if provided access to
$\ket{\sigma^{*}}\otimes\ket{\sigma}$. In this process, Bell basis
measurements are performed $K$ times, and the resulting measurement outcomes
yield a set of strings denoted as $T$. This set $T$ consists of
$2n$-dimensional strings, each identifying a Pauli operator $P$ such that
$P\in G_{\sigma}$, where $G_{\sigma}$ is the stabilizer group of
$\ket{\sigma}$. Finding an $n$-dimensional basis for the $T$ is equivalent to
finding a set of generators for the stabilizer group $G_{\sigma}$.

The potential failure of this process occurs when all the $K$ samples lie in a
subspace of $T$ with dimension less than $n$. The probability that all the
obtained samples fall within such a subspace is $2^{-K}$. By applying the
union bound, we find that the probability of these samples lying in one of the
$2^{n}$ $(n-1)$-dimensional subspaces of $T$ is $2^{-K+n}$. To mitigate this
probability of failure, one can choose $K=2n$, resulting in an exponentially
vanishing probability of failure. With the set of generators for $G_{\sigma}$
obtained, one can proceed to learn the phases by making a single-shot
measurement of the expectation value of the learned Pauli generators.

In cases where access is limited to $\ket{\sigma}\otimes\ket{\sigma}$, rather
than $\ket{\sigma^{*}}\otimes\ket{\sigma}$, it is still possible to learn the
stabilizer state through a similar procedure. First, it is worth noting that
for a stabilizer state $\ket{\sigma^{*}}=\bar{P}\ket{\sigma}$, where $P$ is a
Pauli string consisting of $Z,{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}$ operators.
Consequently, the probability of sampling the Pauli operator $P$ can be
rewritten as $|\braket{\sigma}{P\bar{P}}{\sigma}|^{2}/2^{n}$. Although $P$
does not stabilize $\ket{\sigma}$, the Pauli operator $P\bar{P}$ does it;
otherwise, the sampling probability would be zero. Thus, when two Pauli
operators, $P_{1}$ and $P_{2}$, are sampled, their product stabilizes
$\ket{\sigma}$. This can be demonstrated straightforwardly by noting that both
$P_{1}\bar{P}$ and $P_{2}\bar{P}$ stabilize $\ket{\sigma}$, and their product,
$P_{1}\bar{P}P_{2}\bar{P}$, remains a Pauli operator that stabilizes
$\ket{\sigma}$. Furthermore, it is proportional to $P_{1}P_{2}$, with the
proportionality factor possibly being $\pm 1$ due to the commutation relations
between $\bar{P}$ and $P_{2}$.

Thanks to this property, instead of sampling $K$ times, one only needs to
sample $K+1$ times to determine the set of generators for $G_{\sigma}$, while
maintaining the same failure probability.

##  Appendix B Efficient verification of containment

In this section, we provide an alternative algorithm based on the notion of
diagonalizer to efficiently verify the containment of a Pauli operator $P$ to
the set $G_{\psi_{t}}\cup h_{1}G_{\psi_{t}}\cup\ldots\cup h_{l}G_{\psi_{t}}$.
Let $\mathbb{Z}\subset\mathbb{P}_{n}$ the subgroup of the Pauli group
generated by $\\{\sigma_{i}^{z}\\}_{i=1}^{n}$, with
$\sigma_{i}^{z}=\operatorname{diag}(1,-1)$ on the $i$-th qubit. Then let
$\mathcal{D}\in\mathcal{C}_{n}$ be a Clifford circuit such that
$\tilde{G}_{\psi_{t}}\equiv\mathcal{D}^{{\dagger}}G_{\psi_{t}}\mathcal{D}\subset\mathbb{Z}$.
Notice that $\mathcal{D}$ can be found from a set of generators of
$G_{\psi_{t}}$ in time $O(n^{2})$ [18, 19]. Define
$\tilde{h}_{i}\equiv\mathcal{D}^{{\dagger}}h_{i}\mathcal{D}$, which requires
computational complexity $O(n^{2}l)$. To check whether $P\not\in
G_{\psi_{t}}\cup h_{1}G_{\psi_{t}}\cup\ldots\cup h_{k}G_{\psi_{t}}$ is
sufficient to check that
$\mathcal{D}^{{\dagger}}P\mathcal{D}\not\in\tilde{G}_{\psi_{t}}\cup\tilde{h}_{i}\tilde{G}_{\psi_{t}}\cup\ldots\cup\tilde{h}_{l}\tilde{G}_{\psi_{t}}$
that – thanks to the local support of $\sigma_{i}^{z}s$ – can be easily
achieved by a qubit by qubit checking in time $O(nl)$. Consequently, the final
runtime to verify if a Pauli operator $P$ belongs to $G_{\psi_{t}}\cup
h_{1}G_{\psi_{t}}\cup\ldots\cup h_{l}G_{\psi_{t}}$ is $O(n^{2}k)$.

##  Appendix C Proofs

###  C.1 Disjoint cosets.

In this section, we will prove the disjointedness of the cosets. Let us
consider $P\in S_{\psi_{t}}$ such that $P\not\in G_{\psi_{t}}$, then it is
easy to notice that
$\operatorname{tr}(Pg\psi_{t})=\pm\operatorname{tr}(P\psi_{t})$, and so $Pg\in
S_{\psi_{t}}\,\forall g\in G_{\psi_{t}}$. To prove disjointedness let us
consider two Pauli operators $P_{1},P_{2}\in S_{\psi_{t}}$ such that
$P_{1},P_{2}\not\in G_{\psi_{t}}$, then if $P_{1}G_{\psi_{t}}\cap
P_{2}G_{\psi_{t}}\neq 0$ would imply that $\exists g_{1},g_{2}\in
G_{\psi_{t}}$ such that $P_{1}g_{1}=P_{2}g_{2}$. However, we would get that
$P_{1}\in P_{2}G_{\psi_{t}}$, thanks to the group property of $G_{\psi_{t}}$,
and thus $P_{1}G_{\psi_{t}}\equiv P_{2}G_{\psi_{t}}$ .

###  C.2 Failure probability

Let us discuss the failure probability to sample a Pauli operator $P$
belonging to $G_{\psi_{t}}$. The event that has to be analyzed is the case
where sampled a Pauli $P\notin G$ after a set of measurements $M$ we are
unable to distinguish it from a $P\in G_{\psi_{t}}$. Consequently, the failure
probability is given by the joint probability that a measurement yields $1$
$M$ times and $P\notin G_{\psi_{t}}$. The probability that $P\notin
G_{\psi_{t}}$ is given by $1-2^{-t}$, and denoting $p$ as the probability of
obtaining $1$ ($p=\frac{1}{2}(\operatorname{tr}(h\psi_{t})+1)$, where $h$
represents one bad generator), the failure probability is bounded by
$(1-2^{-t})(h_{\max}/2+1/2)^{M}$.

###  C.3 Proof of Eq. (8)

Given the probability $\pi_{l}$ defined in Eq. (7), let us write explicitly
the unity purity of the state $\psi_{t}$. From Eq. (3), we obtain

$1=\frac{|G_{\psi_{t}}|}{d}\left(1+\sum_{i=1}^{l}\operatorname{tr}^{2}(h_{i}\psi_{t})+\sum_{i=l+1}^{k}\operatorname{tr}^{2}(h_{i}\psi_{t})\right)$
(23)

Therefore, one can express $\pi_{l}$ as

$\pi_{l}=\frac{|G_{\psi_{t}}|}{d}\sum_{i=l+1}^{k}\operatorname{tr}^{2}(h_{i}\psi_{t})\geq\frac{|G_{\psi_{t}}|}{d}(k-l)h^{2}_{\min}$
(24)

which concludes the proof.

###  C.4 Finite resolution

In this section, we present the proof of the finite resolution of the
expectation values of Pauli operators for a $t$-doped stabilizer state. We
will proceed as follows: we first bound $\min_{P\in
S_{\psi_{t}}}|\operatorname{tr}(P\psi_{t})|$ and then we bound the gap
$\delta_{t}$, as the second will be just a trivial generalization of the first
one. We will indeed find that

$\min_{P\in
S_{\psi_{t}}}|\operatorname{tr}(P\psi_{t})|\geq\frac{1}{3\sqrt{2}^{t-1}}\left(1-\frac{1}{\sqrt{2}}\right)^{t}$
(25)

while

$\delta_{t}\geq\frac{1}{6\sqrt{2}^{t-1}}\left(1-\frac{1}{\sqrt{2}}\right)^{t}$
(26)

Since a $t$-doped stabilizer state is built out from a $t$-doped Clifford
circuit, we can alternatively bound
$\min_{P}|\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)|$ for $\sigma$
being an arbitrary stabilizer state. Let us look at the action of $C_{t}$ on a
Pauli operator. First decompose $C_{t}=\prod_{i=1}^{t}C_{1}^{(i)}$ where
$C_{1}^{(i)}$ is a $(t=1)$-doped Clifford circuit. Let us set up the following
notation.

$C_{1}^{(1)}PC_{1}^{(1){\dagger}}=x_{(0)}P_{(0)}+\frac{x_{(1)}}{\sqrt{2}}P_{(1)}+\frac{x_{(2)}}{\sqrt{2}}P_{(2)}$
(27)

where $x_{(0)},x_{(1)},x_{(2)}\in\\{-1,0,+1\\}$. Eq. (27) must be understood
as: there is a choice of $x_{(0)},x_{(1)},x_{(2)}$ and the respective Pauli
operators $P_{(0)},P_{(1)},P_{(2)}$ such that the l.h.s. is equal to the
r.h.s. of Eq. (27). Before generalizing to the generic $t$, it is useful to
act again on $C_{1}^{(1)}PC_{1}^{(1){\dagger}}$ with $C_{1}^{(2)}$.

$\displaystyle
C_{1}^{(2)}C_{1}^{(1)}PC_{1}^{(1){\dagger}}C_{1}^{(2){\dagger}}$
$\displaystyle=$ $\displaystyle
x_{(00)}P_{(00)}+\frac{1}{\sqrt{2}}(x_{(10)}P_{(10)}+x_{(01)}P_{(01)}+x_{(20)}P_{(20)}+x_{(02)}P_{(02)})$
(28) $\displaystyle+$
$\displaystyle\frac{1}{2}(x_{(11)}P_{(11)}+x_{(12)}P_{(12)}+x_{(21)}P_{(21)}+x_{(22)}P_{(22)})$

where each variable $x_{(ij)}$ for $i=0,1,2$ can take values in
$x_{(ij)}\in\\{-1,0,+1\\}$. As one can see, the subscript string $(ij)$
attached to each variable $x_{(ij)}$ reveals how many times a $T$-gate splits
the Pauli operator $P$ in $2$ Pauli operator with the corresponding
$\frac{1}{\sqrt{2}}$ factor. Again, Eq. (28) must be understood as: there
exists a choice of the variables $x_{(ij)}$ and the respective Pauli operators
$P_{(ij)}$ for which the l.h.s. and the r.h.s. of Eq. (28) agrees. Now, that
we set up the above general and powerful notation, we can easily generalize
the action to $C_{t}$. We have the following

$C_{t}PC_{t}^{{\dagger}}=\sum_{k=0}^{t}\sum_{\pi\in
S_{k}}\frac{x_{\pi(\bm{y}_{k})}}{\sqrt{2}^{k}}P_{\pi(\bm{y}_{k})}\,.$ (29)

In Eq. (29) above, we have defined a few elements. First of all, we defined
the $t$-long string $\bm{y}_{k}$ with Hamming weight $k$ as

$\bm{y}_{k}=(\underbrace{1,1,\ldots,1}_{k},0,\ldots,0)$ (30)

Next, we defined a set $S_{k}$ of operations $\pi$ that act on $\bm{y}_{k}$.
$S{k}$ is the set containing all the permutations of the $k$ $1$s in
$\bm{y}_{k}$ into $t$ spots, combined with the operation that transforms
$1\leftrightarrow 2$, in accordance with Eq. (28). Let’s illustrate this with
an example. Set $t=2$ and $k=1$, so $\bm{y}_{1}=(10)$. All the possible
permutations of $(10)$, combined with the operation $1\leftrightarrow 2$,
result in the strings $(10),(01),(20),(02)$. Similarly, for $t=2$ and $k=2$,
$\bm{y}_{2}=(11)$ and the set of operations in $S_{2}$ returns
$(11),(22),(21),(12)$.

It is useful to count the number of operations within $S_{k}$ for fixed $k$.
The set $S_{k}$ is the combination of $\binom{t}{k}$ many ways to permute
$\bm{y}_{k}=(1,1,\ldots,1,0,\ldots,0)$ times the $2^{k}$ different choices of
either $1$ or $2$ at any site. The above simple counting thus returns:

$\sum_{\pi\in S_{k}}=2^{k}\binom{t}{k}$ (31)

From Eq. (29), we can formally compute the expectation value of
$C_{t}PC_{t}^{{\dagger}}$ with a generic stabilizer state $\sigma$ and get

$\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)=\sum_{k=0}^{t}\sum_{\pi\in
S_{k}}\frac{\tilde{x}_{\pi(\bm{y}_{k})}}{\sqrt{2}^{k}}$ (32)

where we defined the variables
$\tilde{x}_{\pi(\bm{y}_{k})}:=x_{\pi(\bm{y}_{k})}\operatorname{tr}(P_{\pi(\bm{y}_{k})}\sigma)\in\\{-1,0,+1\\}$
because $\operatorname{tr}(P_{\pi(\bm{y}_{k})}\sigma)\in\\{-1,0,+1\\}$. Now,
we set up all the necessary notation to finally prove Eq. (25).

We are interested in computing the minimum achievable value for
$\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)$. Let us first multiply both
sides for $\sqrt{2}^{t}$. We thus get

$\displaystyle\sqrt{2}^{t}\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)=\sum_{k=0}^{t}\sum_{\pi\in
S_{k}}\sqrt{2}^{t-k}\tilde{x}_{\pi(\bm{y}_{k})}=\sum_{l=0}^{t}\sum_{\pi\in
S_{t-l}}\sqrt{2}^{l}\tilde{x}_{\pi(\bm{y}_{t-l})}$

where in the second equality, we defined $l=t-k$. Let us set $t$ to be even
and split odd and even terms in the sum

$\displaystyle\sum_{l=0}^{t}\sum_{\pi\in
S_{t-l}}\sqrt{2}^{l}\tilde{x}_{\pi(\bm{y}_{t-l})}=\sum_{l=0}^{t/2}2^{l}\sum_{\pi\in
S_{t-2l}}\tilde{x}_{\pi(\bm{y}_{t-2l})}+\sqrt{2}\sum_{l=0}^{t/2-1}2^{l}\sum_{\pi\in
S_{t-(2l+1)}}\tilde{x}_{\pi(\bm{y}_{t-(2l+1)})}$

Define the following function of $t$

$\displaystyle A(t)$ $\displaystyle:=$
$\displaystyle\sum_{l=0}^{t/2}2^{l}\sum_{\pi\in
S_{t-2l}}\tilde{x}_{\pi(\bm{y}_{t-2l})}$ (33) $\displaystyle B(t)$
$\displaystyle:=$ $\displaystyle\sum_{l=0}^{t/2-1}2^{l}\sum_{\pi\in
S_{t-(2l+1)}}\tilde{x}_{\pi(\bm{y}_{t-(2l+1)})}$ (34)

Note that $A(t),B(t)\in\mathbb{Z}$, i.e. they are positive and negative
natural numbers, for any $t=2t^{\prime}$ for $t\in\mathbb{N}$. We can thus
write

$\sqrt{2}^{t}|\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)|=|A(t)+\sqrt{2}B(t)|=|B(t)|\left|\sqrt{2}+\frac{A(t)}{B(t)}\right|$
(35)

Therefore, the lower bound deals with the approximation of the algebraic
number $\sqrt{2}$ by a rational number $A(t)/B(t)$. To make it explicit we can
lower bound the r.h.s. of Eq. (35) as

$\sqrt{2}^{t}|\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)|\geq|B(t)|\left|\sqrt{2}-\frac{|A(t)|}{|B(t)|}\right|$
(36)

and we can invoke the Liouville Theorem (see Ref. [26]) of approximating a
algebraic number $\alpha$ with two rational numbers $p,q\in\mathbb{Q}$ that
reads: there exist a constant $c(\alpha)$ independent from $p,q$ such that

$\left|\sqrt{2}-\frac{p}{q}\right|\geq\frac{c(\alpha)}{q^{D}}$ (37)

where $D$ is the degree of the algebraic number $\alpha$. In the case of
$\alpha=\sqrt{2}$ we have $D=2$ because $\sqrt{2}$ corresponds to the solution
to the irreducible polynomial $z^{2}-2=0$ which has degree $2$, and
$c(\sqrt{2})=\frac{1}{6}$ [26]. Applying Eq. (37) to Eq. (36), we thus get

$|\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)|\geq\frac{1}{6|B(t)|\sqrt{2}^{t}}$
(38)

We now are just left to find an upper bound to $B(t)$. We proceed with the
following equality

$\displaystyle|B(t)|$ $\displaystyle=$
$\displaystyle\left|\sum_{l=0}^{t/2-1}2^{l}\sum_{\pi\in
S_{t-(2l+1)}}\tilde{x}_{\pi(\bm{y}_{t-(2l+1)})}\right|\leq\sum_{l=0}^{t/2-1}2^{l}\sum_{\pi\in
S_{t-(2l+1)}}|\tilde{x}_{\pi(\bm{y}_{t-(2l+1)})}|$ (39) $\displaystyle=$
$\displaystyle\sum_{l=0}^{t/2-1}2^{l}\sum_{\pi\in
S_{t-(2l+1)}}=\sum_{l=0}^{t/2-1}2^{l}2^{t-(2l+1)}\binom{t}{2l+1}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{8}}2^{t}\left[\left(1+\frac{1}{\sqrt{2}}\right)^{t}-\left(1-\frac{1}{\sqrt{2}}\right)^{t}\right]\leq\frac{1}{\sqrt{8}}\left(1-\frac{1}{\sqrt{2}}\right)^{-t}$

where in the second equality, we used the fact that
$\tilde{x}_{\pi(\bm{y}_{t-(2l+1)})}\in\\{-1,0,+1\\}$ and in the last
inequality, we used the fact that

$\frac{1}{\sqrt{8}}2^{t}\left[\left(1+\frac{1}{\sqrt{2}}\right)^{t}-\left(1-\frac{1}{\sqrt{2}}\right)^{t}\right]\leq\frac{1}{\sqrt{8}}2^{t}\left(1+\frac{1}{\sqrt{2}}\right)^{t}=\frac{1}{\sqrt{8}}\left(1-\frac{1}{\sqrt{2}}\right)^{-t}$
(40)

An analogous procedure with $t=2t^{\prime}+1$ with $t^{\prime}$ leads to the
same exact bound. Therefore for any $t\in\mathbb{N}$, we find

$|\operatorname{tr}(C_{t}PC_{t}^{{\dagger}}\sigma)|\geq\frac{\sqrt{8}}{6}\left(\frac{1}{\sqrt{2}}-\frac{1}{2}\right)^{t}$
(41)

Now, let us turn to analyze the gap
$\delta_{t}\equiv\operatorname{tr}[(P-P^{\prime})\psi_{t}]$. Using the same
notation as before, we can write the adjoint action of $C_{t}$ on
$P-P^{\prime}$ as follows

$C_{t}(P-P^{\prime})C^{{\dagger}}_{t}=\sum_{k=0}^{t}\sum_{\pi\in
S_{k}}\left(\frac{x_{\pi(\bm{y}_{k})}}{\sqrt{2}^{k}}P_{\pi(\bm{y}_{k})}+\frac{x^{\prime}_{\pi(\bm{y}_{k})}}{\sqrt{2}^{k}}P^{\prime}_{\pi(\bm{y}_{k})}\right)$
(42)

and therefore, by repeating the same procedure, we can define

$\displaystyle A^{\prime}(t)$ $\displaystyle:=$
$\displaystyle\sum_{l=0}^{t/2}2^{l}\sum_{\pi\in
S_{t-2l}}\tilde{x}_{\pi(\bm{y}_{t-2l})}+\tilde{x}^{\prime}_{\pi(\bm{y}_{t-2l})}$
(43) $\displaystyle B^{\prime}(t)$ $\displaystyle:=$
$\displaystyle\sum_{l=0}^{t/2-1}2^{l}\sum_{\pi\in
S_{t-(2l+1)}}\tilde{x}_{\pi(\bm{y}_{t-(2l+1)})}+\tilde{x}^{\prime}_{\pi(\bm{y}_{t-(2l+1)})}$
(44)

and write the gap as

$\delta_{t}=\frac{1}{\sqrt{2}^{t}}|A^{\prime}(t)+\sqrt{2}B^{\prime}(t)|\geq\frac{|B^{\prime}(t)|}{\sqrt{2}^{t}}\left|\sqrt{2}-\frac{|A^{\prime}(t)|}{|B^{\prime}(t)|}\right|\geq\frac{1}{6\sqrt{2}^{t}|B^{\prime}(t)|}$
(45)

Following the inequalities in Eq. (39), one can find

$|B^{\prime}(t)|\leq\frac{1}{\sqrt{2}}\left(1-\frac{1}{\sqrt{2}}\right)^{-t}$
(46)

which recovers the desired result in Eq. (26)

$\delta_{t}\geq\frac{\sqrt{2}}{6}\left(\frac{1}{\sqrt{2}}-\frac{1}{2}\right)^{t}$
(47)

##  Appendix D Sampling the stabilizer group from Bell measurements

######  Lemma 1.

Given a quantum state $\ket{\omega}$ on $q$-qubits, there exist a Pauli
operator $\bar{P}$ such that $|\braket{\omega}{\bar{P}}{\omega^{*}}|\geq
2^{-q}$.

###### Proof.

To show this, let us assume the contrapositive, i.e. $\forall
P\in\mathbb{P}_{q}$ then $|\braket{\omega}{P}{\omega^{*}}|<2^{-q}$. First of
all, notice that it always holds

$\sum_{P\in\mathbb{P}_{q}}|\braket{\omega}{P}{\omega^{*}}|^{2}=\sum_{P\in\mathbb{P}_{q}}\operatorname{tr}(\omega
P\omega^{*}P)=2^{q}$ (48)

However, sticking to the hypothesis, if we sum up the squares we get

$\sum_{P\in\mathbb{P}_{q}}|\braket{\omega}{P}{\omega^{*}}|^{2}<2^{-q}\sum_{P\in\mathbb{P}_{q}}<2^{q}$
(49)

and this is a contradiction. ∎

In this section, we shall show that given
$P,P^{\prime}\sim\widetilde{\Xi}_{\psi_{t}}$ drawn from
$\widetilde{\Xi}_{\psi_{t}}$, then their product $PP^{\prime}$ belongs to the
stabilizer group $G_{\psi_{t}}$ with probability greater than $2^{-6t}$.
Formally

$\underset{P,P^{\prime}\sim\widetilde{\Xi}_{\psi_{t}}}{\operatorname{Pr}}(PP^{\prime}\in
G_{\psi_{t}})\geq\frac{1}{2^{6t}}$ (50)

First of all, let us refresh some basis about stabilizer states. Consider a
stabilizer state $\ket{\sigma}$ and its conjugate state in the computational
basis $\ket{\sigma^{*}}$. In Ref. [10], it has been shown that there exist a
Pauli operator $P_{\sigma}$ such that

$P_{\sigma}\ket{\sigma}=\ket{\sigma^{*}}$ (51)

which can be understood at the level of the stabilizer group in the following
way. Let $G_{\sigma}=\braket{g_{1},\ldots,g_{n}}$ the stabilizer group of
$\ket{\sigma}$. The stabilizer group of $\ket{\sigma^{*}}$ is, of course,
given by $G_{\sigma^{*}}=\braket{g_{1}^{*},\ldots,g_{n}^{*}}$. Therefore,
thanks to Eq. (51), there exist $P_{\sigma}$ such that

$P_{\sigma}g_{i}P_{\sigma}=g_{i}^{*},\quad\forall g_{i}\in G_{\sigma}$ (52)

Consider now the projector
$\Pi_{\psi_{t}}:=\prod_{i=1}^{m}\frac{{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}+\phi_{g_{j}}g_{j}}{2}$ onto the stabilizer group
$G_{\psi_{t}}$. Since $G_{\psi_{t}}$ can be completed to a maximal stabilizer
group $\widetilde{G_{\psi_{t}}}$, i.e. $|\widetilde{G_{\psi_{t}}}|=d$, there
exists $P_{\psi_{t}}$ such that

$P_{\psi_{t}}\Pi_{\psi_{t}}P_{\psi_{t}}=\Pi_{\psi_{t}}^{*}$ (53)

where $\Pi_{\psi_{t}}^{*}=\prod_{i=1}^{m}\left(\frac{{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}+\phi_{g_{j}}g_{j}^{*}}{2}\right)$. On the state vector level,
the action of $P_{\psi_{t}}$ on $\ket{\psi_{t}^{*}}$ results in
$\ket{\psi_{t}^{*\prime}}=P_{\psi_{t}}\ket{\psi_{t}^{*}}$ with a density
matrix representation equal to

$\ket{\psi_{t}^{*\prime}}\\!\\!\bra{\psi_{t}^{*\prime}}=\left(\frac{1}{2^{t}}\sum_{i=0}^{k}\operatorname{tr}(h_{i}\psi_{t}^{*})h_{i}\right)\Pi_{\psi_{t}}$
(54)

i.e. having the same projector $\Pi_{\psi_{t}}$ of $\ket{\psi_{t}}$. To
demonstrate the validity of Eq. (54), is sufficient to compute the overlap
$\operatorname{tr}(\Pi_{\psi_{t}}P_{\psi_{t}}\psi_{t}^{*}P_{\psi_{t}})=1$.
Thanks to Eq. (54), given $\mathcal{D}_{\psi_{t}}$ being the diagonalizer
associated to $\ket{\psi_{t}}$, one has that

$\mathcal{D}_{\psi_{t}}\ket{\psi_{t}^{*\prime}}=\ket{0}^{\otimes
m}\otimes\ket{\phi^{*}}$ (55)

The last step before proving the statement comes from the result of Lemma 1
that ensures the existence of a Pauli operator $\bar{P}$ such that
$|\braket{\phi}{\bar{P}}{\phi^{*}}|\geq 2^{-(n-m)}$. Therefore, let us prove
the statement, i.e. that the probability that Bell measurements sample a Pauli
$P$ such that $PP_{\psi_{t}}\mathcal{D}^{{\dagger}}\bar{P}\mathcal{D}\in
G_{\psi_{t}}$ is greater than $d^{-1}8^{-t}$. Starting Eq. (10), we have

$\displaystyle|\braket{\psi_{t}}{P}{\psi_{t}^{*}}|$ $\displaystyle=$
$\displaystyle|\braket{\psi_{t}}{PP_{\psi_{t}}}{\psi_{t}^{*\prime}}|$
$\displaystyle=$
$\displaystyle|\braket{0^{m}\otimes\phi}{\mathcal{D}PP_{\psi_{t}}\mathcal{D}^{{\dagger}}}{0^{m}\otimes\phi^{*}}|$
$\displaystyle=$
$\displaystyle|\braket{0^{m}\otimes\phi}{\mathcal{D}PP_{\psi_{t}}\mathcal{D}^{{\dagger}}\bar{P}\bar{P}}{0^{m}\otimes\phi^{*}}|$

Let us impose $PP_{\psi_{t}}\mathcal{D}^{{\dagger}}\bar{P}\mathcal{D}\in
G_{\psi_{t}}$; therefore, we have the following bound:

$\displaystyle|\braket{\psi_{t}}{P}{\psi_{t}^{*}}|$ $\displaystyle=$
$\displaystyle|\braket{0^{m}\otimes\phi}{\bar{P}}{0^{m}\otimes\phi^{*}}|$ (56)
$\displaystyle=$ $\displaystyle|\braket{\phi}{\bar{P}}{\phi^{*}}|\geq
2^{-(n-m)}$

And therefore, we can formally write

$\operatorname{Pr}(PP_{\psi_{t}}\mathcal{D}^{{\dagger}}\bar{P}\mathcal{D}\in
G_{\psi_{t}})\geq\frac{|G_{\psi_{t}}|}{d}\frac{1}{2^{2(n-m)}}\geq\frac{1}{8^{t}}$
(57)

For fixed $P_{\psi_{t}}$ and $\bar{P}$, one has that the probability that two
samples Pauli operators $P,P^{\prime}$ obeys the property in Eq. (57) is
$\frac{1}{{2}^{6t}}$, and one has that the probability that the product
$PP^{\prime}\in G_{\psi_{t}}$ is, by a simple shift for
$P_{\psi_{t}}\mathcal{D}^{{\dagger}}\bar{P}\mathcal{D}$, is the one in Eq.
(50).