# Efficient information recovery from Pauli noise via classical shadow

Yifei Chen  Zhan Yu  Chenghong Zhu  Xin Wang<EMAIL_ADDRESS>Institute
for Quantum Computing, Baidu Research, Beijing 100193, China

###### Abstract

The rapid advancement of quantum computing has led to an extensive demand for
effective techniques to extract classical information from quantum systems,
particularly in fields like quantum machine learning and quantum chemistry.
However, quantum systems are inherently susceptible to noises, which adversely
corrupt the information encoded in quantum systems. In this work, we introduce
an efficient algorithm that can recover information from quantum states under
Pauli noise. The core idea is to learn the necessary information of the
unknown Pauli channel by post-processing the classical shadows of the channel.
For a local and bounded-degree observable, only partial knowledge of the
channel is required rather than its complete classical description to recover
the ideal information, resulting in a polynomial-time algorithm. This
contrasts with conventional methods such as probabilistic error cancellation,
which requires the full information of the channel and exhibits exponential
scaling with the number of qubits. We also prove that this scalable method is
optimal on the sample complexity and generalise the algorithm to the weight
contracting channel. Furthermore, we demonstrate the validity of the algorithm
on the 1D anisotropic Heisenberg-type model via numerical simulations. As a
notable application, our method can be severed as a sample-efficient error
mitigation scheme for Clifford circuits.

##  I Introduction

Quantum computers are shown to be able to solve certain problems significantly
faster than classical computers [1]. However, current quantum devices are
susceptible to noise from various sources like the environment, crosstalk, and
quantum decoherence, which sets an ultimate time and size limit for quantum
computation. Thus the near-term state of quantum computing is referred to as
the noisy intermediate-scale quantum (NISQ) era [2]. To unleash the potential
of near-term quantum computers, a major challenge is to reduce the effect of
noise in the quantum system.

One of the most important ingredients in quantum computing is to extract
information from a quantum system by measuring the quantum state, which is
described as the expectation value of some observable $O$ of interest. The
expectation value of some chosen observable unravels many properties of the
quantum system, which is extensively used in many quantum algorithms,
including variational quantum eigensolver [3], quantum approximate
optimization algoirhtm [4], and quantum machine learning [5].

For an ideal quantum state $\sigma$, the information that we seek to obtain is
$\operatorname{tr}(O\sigma)$. However, due to the noise present in the quantum
computer, the actual state in practice is some _noisy state_ $\tilde{\sigma}$
instead. One of the most standard theoretical models for quantum noise in the
study of quantum error correction and mitigation is _Pauli noise_. On one
hand, Pauli noise provides a simple model that describes common incoherent
noise such as bit-flip, depolarizing, and dephasing. On the other hand,
general quantum noise can be mapped to Pauli noise without incurring a loss of
fidelity by the technique of randomised compiling [6, 7].

The problem of recovering from Pauli noise is that, given access to an unknown
Pauli noise ${\cal P}$ and copies of the noisy state $\tilde{\sigma}={\cal
P}(\sigma)$, retrieve the information $\operatorname{tr}(O\sigma)$ for some
observable $O$. To recover from a noise ${\cal P}$, a natural way is to
construct a map ${\cal Q}$ such that the composed map ${\cal Q}\circ{\cal P}$
is an identity map [8], which could covert the noisy state ${\cal P}(\sigma)$
to the ideal state $\sigma$. Such a map is actually not necessary if we are
only concerned with the target expectation value $\operatorname{tr}(O\sigma)$
instead of the ideal state $\sigma$. Zhao  _et al._ [9] proved the necessary
and sufficient condition for retrieving the target information from noisy
quantum states, and utilised semidefinite programming to determine an optimal
protocol for constructing the map ${\cal D}$ that satisfies
$\operatorname{tr}({\cal D}\circ{\cal
P}(\sigma)O)=\operatorname{tr}(O\sigma)$. While this method is not restricted
to the class of Pauli channels, it requires complete information of the
quantum noise. Obtaining the full classical description of an unknown Pauli
channel often uses techniques like quantum process tomography [10, 11, 12],
typically requiring a number of copies of the channel that scales
exponentially in the number of qubits, which is resource-consuming and
inefficient. Furthermore, the map ${\cal D}$ proposed in Ref. [9] needs to be
simulated via probabilistic sampling, which requires additional resources. How
to efficiently recover information from a Pauli channel with no prior
information still remains an open and challenging problem.

Fig 1: Illustration of the algorithm for recovering information from Pauli
noise. (a) The classical information contains eigenvalues of the Pauli channel
defined in Section II.1. It is first estimated using the classical shadows of
the channel, which is obtained by preparing random Pauli eigenstates as input
and measuring the output states in random Pauli basis. (b) Then given any
quantum states $\mathcal{P}(\sigma)$ that is subjected to this Pauli noise,
estimation of $\operatorname{tr}(O\sigma)$ can be obtained by post-processing
measurement results of the noisy state and the classical information we
learnt. We note that the same classical information can be reused to recover
information for different noisy states.

To make progress towards resolving this open problem, we consider only
obtaining partial information of the unknown Pauli channel instead of its full
classical description, which would be sufficient for retrieving the
expectation value of specific observables. We then note that there are
efficient methods such as shadow tomography [13], classical shadow [14] and
recently proposed quantum estimation algorithms [15, 16, 17, 18] that can
estimate these properties of a quantum system using very few quantum
resources. This provides us the intuition that the technique of classical
shadow tomography has the potential to lead to an efficient method of
retrieving information from Pauli noise.

In this work, we propose an efficient algorithm that retrieves the information
$\operatorname{tr}(O\sigma)$ from unknown Pauli noise ${\cal P}$ for arbitrary
$n$-qubit noisy state ${\cal P}(\sigma)$ and _bounded-degree $k$-local
observables_ $O$. The main idea is that, when the observable of interest is
local and bounded-degree, then only partial eigenvalues of the channel are
required to recover the ideal information. The algorithm consists of two
steps: learning the necessary information of the unknown Pauli channel and
using the information to estimate the expectation value
$\operatorname{tr}(O\sigma)$ in classical post-processing. The main scheme is
illustrated in Fig. 1. For the learning process, we leverage the techniques of
classical shadow tomography [14, 15] to estimate the eigenvalues of the Pauli
channel up to precision $\epsilon$ with probability $1-\delta$, which only
requires ${\cal O}(\log(n^{k}/\delta)/\epsilon^{2})$ copies of the Pauli
channel. Furthermore, we utilise information-theoretic techniques [19, 17] to
prove a lower bound on the sample complexity, showing the optimality of our
learning algorithm. We could apply classical shadow tomography on the noisy
state $\tilde{\sigma}$ for bounded-degree observables to obtain necessary
classical information, the sample complexity of which is also optimal [15]. By
post-processing the obtained information from these two steps, we retrieve the
target expectation value $\operatorname{tr}(O\sigma)$ in computational time
${\cal O}(n^{k}\log(n^{k}))$. As a notable application, we apply our method to
mitigate Pauli errors in Clifford circuits, which leads to a more sample-
efficient Pauli error mitigation scheme than previous methods such as
probabilistic error cancellation [20].

We will start by giving some background and introducing the idea of classical
shadows in Section II, and then present the algorithm for recovering
information from Pauli noise in Section III. In Section IV, we analyse the
sample complexity and computational complexity of our proposed algorithm,
which shows the efficiency and optimality of the algorithm. We present a
numerical experiment in Section V showing the correctness of our algorithm. An
application of the algorithm, which is error mitigation of Clifford circuits,
is described in Section VII. We discuss the comparison with prior work in
Section VIII and conclude with outlook in Section IX.

##  II Preliminaries

###  II.1 Quantum channels and observables

In the theory of quantum information [21, 22, 23], noise of quantum systems
are modelled by _quantum channels_ , which are completely positive and trace-
preserving (CPTP) maps between spaces of operators. An $n$-qubit _Pauli
channel_ is defined as

${\cal P}(\sigma)\coloneqq\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}p(P)\cdot
P\sigma P^{\dagger},$ (1)

where $P$ is an $n$-fold tensor product of Pauli operators in $\\{I,X,Y,Z\\}$,
and $p$ is a probability distribution on $\\{I,X,Y,Z\\}^{\otimes n}$. A
quantum channel is _unital_ if it maps the identity operator to the identity
operator. The adjoint map of an $n$-qubit quantum channel $\mathcal{N}$ is the
unique map $\mathcal{N}^{\dagger}$ that satisfies

$\operatorname{tr}(X\mathcal{N}(Y))=\operatorname{tr}(\mathcal{N}^{\dagger}(X)Y)$
(2)

for all linear operators $X,Y\in\mathcal{L}_{\mathbb{C}^{2n}}$ and
$\mathcal{N}^{\dagger}$ is a completely positive and unital map. In
particular, $\mathcal{N}^{\dagger}$ maps hermitian operators to hermitian
operators.

A Pauli channel $\mathcal{P}$ is in fact self-adjoint, meaning
$\mathcal{P}^{\dagger}=\mathcal{P}$, which can be verified directly from the
definition, so throughout this paper, we omit $\dagger$ on
$\mathcal{P}^{\dagger}$. Another observation is that every $n$-qubit Pauli
operator $P$ is an eigenoperator of $\mathcal{P}$ since

$\displaystyle\mathcal{P}(P)$ $\displaystyle=\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes
n}}p(Q)QPQ$ (3) $\displaystyle=\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes
n}}(-1)^{\langle P,Q\rangle}p(Q)Q^{2}P$ (4)
$\displaystyle=\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes n}}(-1)^{\langle
P,Q\rangle}p(Q)P,$ (5) $\displaystyle\text{where }\langle P,Q\rangle$
$\displaystyle=\begin{cases}0&\text{if $P$ and $Q$ commute},\\\ 1&\text{if $P$
and $Q$ anti-commute}.\end{cases}$ (6)

The quantity $\sum_{Q\in\\{I,X,Y,Z\\}^{\otimes n}}(-1)^{\langle
P,Q\rangle}p(Q)$ is the eigenvalue of $P$ which we denote as $\lambda_{P}$. We
refer to the collection of $\lambda_{P}$ as eigenvalues of the Pauli channel.

Observables are represented by hermitian operators. An observable $O$ is _$k$
-local_ if it can be written as a linear combination
$O=\sum_{j}\alpha_{j}O_{j}$ where each $O_{j}$ acts on at most $k$ qubits. An
observable is _bounded-degree_ if only a constant number of terms $O_{j}$ in
the sum act on each qubit. The _weight_ of an $n$-qubit Pauli operator $P$,
denoted as $\left\lvert P\right\rvert$, is the number of tensor factors that
are not identity $I$. Since Pauli operators form a basis of hermitian
operators, any observable $O$ has a unique Pauli decomposition
$O=\sum_{P}\alpha_{P}P$. This allows us to define the _weight_ of an
observable $O$ to be the maximum weight of Pauli operators whose coefficient
$\alpha_{P}$ is non-zero in the expansion of $O$. We also define the Pauli
$p$-norm of an observable $O$, denoted as $\left\lVert
O\right\rVert_{\mathrm{Pauli},p}$, to be the $l_{p}$-norm of $\bm{\alpha}$,
where $\bm{\alpha}$ is the vector of Pauli coefficients $\alpha_{P}$.

###  II.2 Classical shadow tomography

In Ref. [13], the author showed that for the task of estimating multiple
measurement probability of an unknown state, only a sample size that is
logarithmic in the number of measurements to predict and the dimension of the
quantum state is required. Based on this work, huang2020predicting Huang  _et
al._ [14] considered the task of predicting $\operatorname{tr}(O\sigma)$ for a
set of $O$ simultaneously under some mild conditions and the method proposed
is called _classical shadow tomography_. Classical shadows refer to the
classical data acquired by performing randomised measurements on an unknown
state. This can be realised by randomly selecting a unitary from a given set,
applying it to the state and measuring the output state in the computational
basis. It was shown that if the set of unitaries satisfies certain conditions,
we can always construct an unbiased estimator for the state using classical
shadows. There have been various recent progresses exploring applications and
extensions of classical shadows, see, e.g., Refs. [24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35].

A common set of measurements is Pauli measurements. Its estimator is easy to
compute and has the following performance guarantee:

######  Proposition 1 (Theorem 1 and Proposition 3 in Ref. [14])

Adopting a random Pauli basis primitive, where each random unitary is of the
form $U_{1}\otimes\cdots\otimes U_{n}$, and each $U_{i}$ is uniformly selected
from the single-qubit Clifford group. Given a collection of $k$-local
observables $\\{O_{1},O_{2},\ldots,O_{M}\\}$, accuracy parameters
$\epsilon,\delta\in[0,1]$, then

$\displaystyle
N=\mathcal{O}\left(\frac{\log(M/\delta)}{\epsilon^{2}}\max_{i}4^{k}\lVert
O_{i}\rVert^{2}_{\infty}\right)$ (7)

samples are required to simultaneously predict each
$\operatorname{tr}(O_{i}\rho)$ up to accuracy $\epsilon$ with success
probability $1-\delta$.

Here, adopting a random Pauli basis primitive means we are measuring each
qubit in random Pauli basis. This is realised by applying a random single-
qubit Clifford gate to each qubit and measuring in computational basis. One
can obtain this result by combining Theorem 1 and Proposition 3 in Ref. [14].
Theorem 1 states that the number of samples $N$ is in
$\mathcal{O}(\log(M/\delta)/\epsilon^{2})$ multiplied by a quantity that
depends on the set of random unitaries. Proposition 3 further shows that this
quantity for random Pauli measurement is upper bounded by $\max_{i}4^{k}\lVert
O_{i}\rVert^{2}_{\infty}$.

##  III Algorithm for Information Recovery

Firstly, we formally define the problem of information recovery from noisy
quantum states. Given access to an unknown $n$-qubit Pauli channel
$\mathcal{P}$ and a noisy state ${\cal P}(\sigma)$, for a known bounded-degree
$k$-local observable $O$, the task is to provide a function $f({\cal
P}(\sigma),O)$ that approximates the ideal expectation value
$\operatorname{tr}(O\sigma)$ within some precision $\epsilon$, i.e.,

$\left\lvert f({\cal
P}(\sigma),O)-\operatorname{tr}(O\sigma)\right\rvert\leq\epsilon.$ (8)

For the target expectation value, the action of the channel ${\cal P}$ on
state $\sigma$ can be viewed as its adjoint map acting on the observable $O$,

$\operatorname{tr}(O\mathcal{P}(\sigma))=\operatorname{tr}(\mathcal{P}(O)\sigma).$
(9)

Hence, an estimation for $\operatorname{tr}(O\sigma)$ can be obtained by
calculating $\operatorname{tr}(\overleftarrow{O}\mathcal{P}(\sigma))$ for an
observable $\overleftarrow{O}$ such that $\mathcal{P}(\overleftarrow{O})=O$.
We have that any Pauli operator $P$ is an eigenoperator of $\mathcal{P}$,
i.e., $\mathcal{P}(P)=\lambda_{P}P$. This means that if we obtain the
estimated value $\widehat{\lambda}_{P}$ of $\lambda_{P}$, we can construct
$\overleftarrow{O}=\sum_{P}\overleftarrow{\alpha}_{P}P$ by simply taking the
Pauli decomposition $O=\sum_{P}\alpha_{P}P$ and let
$\overleftarrow{\alpha}_{P}=\alpha_{P}/\widehat{\lambda}_{P}$, so that

$\mathcal{P}(\overleftarrow{O})=\sum_{P}\frac{\lambda_{P}}{\widehat{\lambda}_{P}}\alpha_{P}P\approx\sum_{P}\alpha_{P}P=O.$
(10)

If $O$ is $k$-local then $\alpha_{P}$ is zero for every $P$ that has weight
greater than $k$. Hence our estimate for $\operatorname{tr}(O\sigma)$ is given
by

$f(\mathcal{P}(\sigma),O)=\operatorname{tr}(\overleftarrow{O}\mathcal{P}(\sigma))=\sum_{P\mathrel{\mathop{\mathchar
58\relax}}\left\lvert P\right\rvert\leq
k}\overleftarrow{\alpha}_{P}\operatorname{tr}(P\mathcal{P}(\sigma)).$ (11)

We now formalise the concepts and propose the algorithm that can recover
information from Pauli channels. The detailed procedure is given in Algorithm
1:

Algorithm 1 Information recovery from Pauli noise

1:Access to an unknown $n$-qubit Pauli channel $\mathcal{P}$, a bounded-degree
$k$-local observable $O=\sum_{P}\alpha_{P}P$, copies of unknown noisy state
$\mathcal{P}(\sigma)$.

2:An estimation of $\operatorname{tr}(O\sigma)$.

3:Prepare $N$ random $n$-fold product Pauli eigenstates
$\\{\rho_{i}=\bigotimes_{j=1}^{n}\lvert s_{ij}\rangle\\!\langle
s_{ij}\rvert\\}_{i=1}^{N}$, where each $\ket{s_{ij}}$ is one of the six
eigenstates of single-qubit Pauli operators.

4:Apply the unknown channel $\mathcal{P}$ on the $N$ random states and perform
random Pauli measurements on each qubit, obtaining data
$\\{\bigotimes_{j=1}^{n}\lvert t_{ij}\rangle\\!\langle
t_{ij}\rvert\\}_{i=1}^{N}$.

5:For each $n$-qubit Pauli operator $P$ with $|P|\leq k$, compute
$\widehat{\lambda}_{P}$ by Eqs. 12 and 13.

6:For $O=\sum_{P\mathrel{\mathop{\mathchar 58\relax}}|P|\leq k}\alpha_{P}P$,
let $\overleftarrow{\alpha}_{P}=\alpha_{P}/\widehat{\lambda}_{P}$ for $|P|\leq
k$.

7:Perform Pauli measurement on the noisy state $\mathcal{P}(\sigma)$ for each
Pauli operator $P$ with $\left\lvert P\right\rvert\leq k$ and construct the
estimation as  $f(\mathcal{P}(\sigma),O)=\sum_{P\mathrel{\mathop{\mathchar
58\relax}}|P|\leq
k}\overleftarrow{\alpha}_{P}\operatorname{tr}(P\mathcal{P}(\sigma)).$

In steps $1$ and $2$, we send random Pauli eigenstates into the unknown
channel ${\cal P}$ and measure the output state in random Pauli basis. The
data acquired in the first two steps, which bear similarity to classical
shadows of a quantum state, are indeed classical shadows of the quantum
process ${\cal P}$. Next, we use the classical shadows to estimate the
eigenvalues of $\mathcal{P}$. Specifically, we calculate the estimated
eigenvalues $\widehat{\lambda}_{P}$ as follows. Let $x_{P}=(1/3)^{\left\lvert
P\right\rvert}\lambda_{P}$, then by Lemma 2 below, we can construct an
estimator for $x_{P}$ as

$\displaystyle\widehat{x}_{P}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\operatorname{tr}\big{(}P\bigotimes_{j=1}^{n}(3\lvert
t_{ij}\rangle\\!\langle t_{ij}\rvert-I)\big{)}\operatorname{tr}(P\rho_{i})$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\prod_{j=1}^{n}\operatorname{tr}(P_{j}(3\lvert
t_{ij}\rangle\\!\langle t_{ij}\rvert-I)\operatorname{tr}(P_{j}\lvert
s_{ij}\rangle\\!\langle s_{ij}\rvert),$ (12)

where $\bigotimes_{j=1}^{n}(3\lvert t_{ij}\rangle\\!\langle t_{ij}\rvert-I)$
is the unbiased estimator of $\mathcal{P}(\rho_{i})$ using classical shadows
as presented in Refs. [14, 15]. Then we obtain an estimator of the eigenvalue
as

$\widehat{\lambda}_{P}=3^{|P|}\widehat{x}_{P},$ (13)

since $\lambda_{P}=3^{|P|}x_{P}$. A special case is when $P=I$, the fact that
$\mathcal{P}$ is unital implies $\lambda_{I}=1$ so there is no need to
estimate its value.

This estimator is obtained by an adapted version of Lemma 16 in Ref. [15], the
full statement of which can be found in Lemma S12. The purpose of the original
lemma is to extract a particular expansion coefficient of a general
$O=\sum_{P}\alpha_{P}P$. We focus on the case $O=\mathcal{P}(P)=\lambda_{P}P$
to extract the eigenvalue $\lambda_{P}$.

###### Lemma 2

Let $\mathcal{P}$ be an $n$-qubit Pauli channel with eigenvalues
$\\{\lambda_{P}\\}_{P}$ so that $\mathcal{P}(P)=\lambda_{P}P$ for Pauli
operators $P\in\\{I,X,Y,Z\\}^{\otimes n}$, $\mathcal{D}^{0}$ be the uniform
distribution of $n$-fold product Pauli eigenstates. We have

$\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)=\bigg{(}\frac{1}{3}\bigg{)}^{|P|}\lambda_{P}.$
(14)

We can see that $\widehat{x}_{P}$ is simply an empirical estimation of the
expectation value on the left hand side of Eq. 14. This lemma is derived as an
adapted version of Lemma 16 in Ref. [15] and the detailed proof is provided in
Appendix A.

In step $4$, we divide each coefficient $\alpha_{P}$ by the corresponding
estimated eigenvalue to construct the observable $\overleftarrow{O}$ that can
achieve
$\lvert\operatorname{tr}(\overleftarrow{O}\mathcal{P}(\sigma))-\operatorname{tr}(O\sigma)\rvert\leq\epsilon$.
In step $5$, we obtain the estimation
$\operatorname{tr}(\overleftarrow{O}\mathcal{P}(\sigma))$ by performing Pauli
measurements on the noisy state $\mathcal{P}(\sigma)$. Note that steps $1$ to
$3$ do not require information about $O$ and $\sigma$ but a promise of $O$
being $k$-local, hence can be done beforehand. Whenever we are given a new
observable $O$ and noisy state $\mathcal{P}(\sigma)$, we only need to re-apply
steps $4$ and $5$.

In step $5$ of the algorithm, we require the values of
$\operatorname{tr}(P\mathcal{P}(\sigma))$ for all Pauli operators $P$ such
that $\left\lvert P\right\rvert\leq k$. We denote the total number of such $P$
to be $T(n,k)$, which satisfies $T(n,k)=\mathcal{O}(n^{k})$. Note that it is a
problem which can be solved using classical shadows of quantum state. By
Proposition 1, we can estimate each $\operatorname{tr}(P\mathcal{P}(\sigma))$
up to $\frac{\epsilon}{2T(n,k)}$ using

$\mathcal{O}\left(\frac{T(n,k)^{2}\log(T(n,k))}{\epsilon^{2}}\right)=\mathcal{O}\left(\frac{n^{2k}\log(n^{k})}{\epsilon^{2}}\right)$
(15)

copies of $\mathcal{P}(\sigma)$. This has been proven to be optimal for this
prediction task [15]. Since this task has been studied thoroughly and the
complexity is polynomial in $n$, for simplicity, we assume that we have
$\operatorname{tr}(P\mathcal{P}(\sigma))$ and we do not consider sample
complexity for obtaining $\operatorname{tr}(P\mathcal{P}(\sigma))$ for the
rest of the paper.

##  IV Analysis of sample complexity

Next, we analyse the sample complexity and computational complexity of our
proposed algorithm.

###### Theorem 3

Given an unknown $n$-qubit Pauli channel $\mathcal{P}$, a noisy state ${\cal
P}(\sigma)$, and an $n$-qubit bounded-degree $k$-local observable $O$ where
$k=\mathcal{O}(1)$ and $\lVert O\rVert=1$. For $\epsilon,\delta>0$, there
exists an algorithm that uses $N=\mathcal{O}(\log(n^{k}/\delta)/\epsilon^{2})$
accesses to the channel to obtain a function $f(\mathcal{P}(\sigma),O)$ such
that

$\left\lvert
f(\mathcal{P}(\sigma),O)-\operatorname{tr}(O\sigma)\right\rvert\leq\epsilon$
(16)

with probability at least $1-\delta$. The computation time is
$\mathcal{O}(n^{k}\log(n^{k}))$.

This theorem provides a strong guarantee that both sample complexity and total
computation time scale polynomially as the number of qubits increases, meaning
that our algorithm is practical and scalable for large quantum systems.

By using the formula in Lemma 2 and Hoeffding’s inequality, the sample
complexity has direct connection with how accurate we need to estimate the
eigenvalues, which is denoted by $\epsilon^{\prime}$. We then use a series of
bounding to create connection between $\epsilon^{\prime}$ and $\epsilon$ which
translates to the final sample complexity. The detailed proof can be found in
Appendix B.

In the first part of the algorithm where we learn the eigenvalues of the
channel, the number of channels that we use is in
$\mathcal{O}(\log(n^{k})/\epsilon^{2})$. We now use information-theoretic
techniques in Refs. [19, 36, 17] to prove a lower bound on the sample
complexity for achieving this channel learning task.

###### Proposition 4

Let $\mathbb{K}$ denote the set of $n$-qubit Pauli operators whose weight is
at most $k$, i.e., $\mathbb{K}\coloneqq\Set{P\in\\{I,X,Y,Z\\}^{\otimes
n}\mathrel{\mathop{\mathchar 58\relax}}\left\lvert P\right\rvert\leq k}$.
Given an unknown Pauli channel $\mathcal{P}$, if an algorithm can estimate the
eigenvalue of every $P\in\mathbb{K}$ up to accuracy $\epsilon$ from $N$ access
of $\mathcal{P}$, where arbitrary input state can be prepared to be sent
through the channel and arbitrary POVM can be used to measure the output state
during each access, then $N=\Omega(\log(n^{k})/\epsilon^{2})$.

The proof is given in Appendix C. The lower bound obtained matches our upper
bound, which shows the optimality of our algorithm when channel can only be
used once in each access. On the other hand, if more quantum resources are
available, such as ancilla qubits or even using multiple copies of channel at
the same time, similar to what is proven in Ref. [17], more efficient
algorithms could be possible.

###### Remark 1

Algorithm 1 involves the collection of Pauli shadows of the channel. In
Appendix D, we further explore the utilisation of Clifford shadows and we show
that Clifford shadows cannot provide any improvement for sample complexity
under the assumption that the locality of the observable $k=\mathcal{O}(1)$.

##  V Numerical experiments

Estimating the expectation value $\operatorname{tr}(O\sigma)$ has many
applications in quantum information processing. For example, variational
quantum eigensolvers [3] are proposed for estimating the ground state energy,
which requires tuning the parameters to minimise the expectation value as a
cost function. Subsequently, we use numerical simulations to demonstrate that
our algorithm can estimate $\operatorname{tr}(\overleftarrow{O}{\cal
P}(\sigma))\approx\operatorname{tr}(O\sigma)$. In our simulations, the 2-qubit
product Pauli channel is utilised. We also consider the noise level in current
quantum devices and choose the noise parameters of the channel as shown in
Table 1. Each row in the table corresponds to the noise parameters associated
with each qubit. The target observable we choose is the 1D anisotropic
Heisenberg-type Hamiltonian with $n$ sites. When the periodic boundary
condition is closed and the magnetic field is included, the observable can be
expressed as

$O=\sum_{j=1}^{n-1}(J_{x}\sigma_{j}^{x}\sigma_{j+1}^{x}+J_{y}\sigma_{j}^{y}\sigma_{j+1}^{y}+J_{z}\sigma_{j}^{z}\sigma_{j+1}^{z}+h\sigma_{j}^{z}),$
(17)

where $\sigma_{i}^{a}$ represents Pauli-$a$ operator acting on the $i$th
qubit, $J_{x}$, $J_{y}$, $J_{z}$ are the spin coupling strengths and $h_{z}$
is the magnetic field applied along the $z$ direction. We randomly choose
these coefficients to be $J_{x}=0.27$, $J_{y}=0.42$, $J_{z}=0.76$ and
$h_{z}=0.6$, then normalise it to have $\lVert O\rVert_{\infty}=1$.

Then the algorithm starts by collecting classical shadows of the channel and
we choose to sample $[1,20]\times 10^{4}$ classical shadows for estimating
eigenvalues, and divide $\alpha_{P}$ by the estimated eigenvalue. To estimate
the accuracy with the increased number of classical shadows, we randomly
generate 500 Haar-random $n$-qubit states
$\\{\sigma_{1},\ldots,\sigma_{500}\\}$ and directly calculate the ideal
expectation value with respect to $H$. We then send the state through the
channel $\mathcal{P}$ and compute the mean absolute error (MAE) for not
performing any post-processing and performing our information recovery
algorithm, respectively:

MAE with no post-processing
$\displaystyle=\frac{1}{500}\sum_{i=1}^{500}\left\lvert\operatorname{tr}(O\mathcal{P}(\sigma_{i}))-\operatorname{tr}(O\sigma_{i})\right\rvert,$
(18) MAE with post-processing
$\displaystyle=\frac{1}{500}\sum_{i=1}^{500}\left\lvert
f(\mathcal{P}(\sigma_{i}),O)-\operatorname{tr}(O\sigma_{i})\right\rvert.$ (19)

Finally, to make comparisons, we find the ratio between the two MAEs,

$r=\frac{\text{MAE with post-processing}}{\text{MAE with no post-
processing}},$ (20)

to show how much our algorithm improves the estimation. For every $10^{4}$
classical shadows, we repeat the above procedures 10 times and average over
$r$. The experiment results are shown in Fig. 2. It can be seen clearly that
the ratio $r$ decreases as the number of samples increases, which indicates
more precise classical information we are extracting.

qubit number | $p_{I}$ | $p_{X}$ | $p_{Y}$ | $p_{Z}$
---|---|---|---|---
1 | 0.75 | 0.10 | 0.10 | 0.05
2 | 0.77 | 0.09 | 0.09 | 0.05
Table 1: Noise parameters for each qubit. Fig 2: Information recovery on a
2-qubit anisoptropic Heisenberg-type model under product Pauli channels. The
x-axis indicates the number of classical shadows we use, with a unit of
$10^{4}$. The y-axis represents the ratio of error between when post-
processing is performed and when no post-processing is performed. In
comparison to extracting the expectation value from noisy states without post-
processing, our algorithm provides a moderate increase in precision.

Hence, we have demonstrated that our method can successfully predict the
expectation value from noisy states and showed that the accuracy improves with
more samples.

##  VI Extensions in channel types

In the previous section, we have demonstrated that our algorithm can recover
information efficiently for Pauli channels. It is a natural question to ask
what other types of channels lead to this efficiency. A sufficient criterion
is that the adjoint matrix of the channel written in Pauli basis is upper
block triangular, where each block contains Pauli operators with the same
weight and the block is arranged in increasing order of weight. An equivalent
description is that the channel is _weight contracting_ , in the sense that
the weight of the operator does not increase under the action of the adjoint
map. One such example is product channel. In Appendix E, we provide an updated
version of the algorithm that can recover information from weight contracting
channel which has the following updated performance guarantee:

###### Proposition 5

Given an unknown $n$-qubit weight contracting channel $\mathcal{E}$, a noisy
state ${\cal E}(\sigma)$, and an $n$-qubit bounded-degree $k$-local observable
O with $\left\lVert O\right\rVert_{\infty}=1$. For $\varepsilon,\delta>0$,
there exists an algorithm that uses
$N=\mathcal{O}(n^{2k}\log(n^{2k}/\delta)/\epsilon^{2})$ access to the channel
to obtain a function $f$ such that

$\lvert f(\mathcal{E}(\sigma))-\operatorname{tr}(O\sigma)\rvert\leq\epsilon$
(21)

with probability at least $1-\delta$. The computation time is
$\mathcal{O}(n^{4k}\log(n^{2k}))$.

The proposition shows that the sample complexity of channels increases to
$\mathcal{O}(n^{2k}\log(n^{2k}/\delta)/\epsilon^{2})$ due to more information
of the channel needs to be estimated, and the total computational time
increases to $\mathcal{O}(n^{4k}\log(n^{2k}))$ accordingly, but still remains
efficient and scalable.

##  VII Application in Clifford circuit error mitigation

An application of our method is mitigating Pauli errors in Clifford circuits,
in which we only consider a circuit $\mathcal{C}$ consisting of $H$, $S$ and
$\mathrm{CNOT}$ gates. Then, each gate is followed by a Pauli noise channel
and we assume that noise for the same type of gate is the same. This is a
stronger setting than the usual gate-independent time-stationary Markovian
(GTM) noise considered in Refs. [37, 38, 17] which assumes the noise channel
after each gate is identical. We denote the resultant circuit as
$\tilde{\mathcal{C}}$. For any input state $\sigma$, the expected output is
$\mathcal{C}(\sigma)$ but the actual output is $\tilde{\mathcal{C}}(\sigma)$.
The goal of error mitigation is then obtaining the exact expectation value
$\operatorname{tr}(O\mathcal{C}(\sigma))$ for given observable $O$ when only
the noisy version is available. To achieve this, we first learn the
eigenvalues of the noise channel associated to the three types of gate. The
method is the same as steps $1$ to $3$ of Algorithm 1, but the noisy channel
is replaced by different noisy gates, and the corresponding estimators require
slight modification. For single qubit gate, they become

$\displaystyle\widehat{x}_{P}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\operatorname{tr}(P(3\lvert
t_{i}\rangle\\!\langle
t_{i}\rvert-I))\operatorname{tr}(P(U\rho_{i}U^{\dagger})),$ (22)
$\displaystyle\widehat{\lambda}_{P}$ $\displaystyle=3\widehat{x}_{P},$ (23)

where $U\in\\{H,S\\}$. For $\mathrm{CNOT}$ gate, the matrix of noisy
$\mathrm{CNOT}$ gate is a monomial matrix. If we label the matrix entries by
Pauli operators, then $(\pi(P),P)$ entry takes the value of $\lambda_{P}$
where $\pi(P)$ is the resultant Pauli operator by conjugating $P$ by
$\mathrm{CNOT}$. In this case, estimation is done by

$\displaystyle\widehat{x}_{P}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\operatorname{tr}(P\bigotimes_{j=1}^{n}(3\lvert
t_{ij}\rangle\\!\langle t_{ij}\rvert-I))\operatorname{tr}(\pi(P)\rho_{i}),$
(24) $\displaystyle\widehat{\lambda}_{P}$
$\displaystyle=3^{|\pi(P)|}\widehat{x}_{P}.$ (25)

Next, we show how to error mitigate a Clifford circuit consisting of two gates
and a higher number of gates follows the same idea. Let

$\mathcal{C}=\mathcal{U}_{2}\circ\mathcal{U}_{1},$ (26)

where $\mathcal{U}_{i}(\rho)=U_{i}\rho U_{i}^{\dagger}$,
$U_{i}\in\\{H,S,\mathrm{CNOT}\\}$. The corresponding noisy circuit
$\tilde{\mathcal{C}}$ is given by

$\tilde{\mathcal{C}}=\mathcal{P}_{\mathcal{U}_{2}}\circ\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}$
(27)

Let $\lambda_{i,P}$ denotes the eigenvalue of $P$ under
$\mathcal{P}_{\mathcal{U}_{i}}$, i.e. the eigenvalue of $P$ under the noise
channel coupled with the $i$th gate and $\pi_{i}(P)=U^{\dagger}_{i}PU_{i}$ be
the Pauli operator we get when conjugate $P$ by $U_{i}^{\dagger}$. It can be
shown that

$\operatorname{tr}(P\tilde{\mathcal{C}}(\rho))=\lambda_{2,P}\lambda_{1,\pi_{2}(P)}\operatorname{tr}(P\mathcal{C}(\rho)),$
(28)

hence we can construct

$\overleftarrow{\alpha}_{P}=\frac{\alpha_{P}}{\widehat{\lambda}_{2,P}\widehat{\lambda}_{1,\pi_{2}(P)}},$
(29)

which would have
$\operatorname{tr}(\overleftarrow{O}\tilde{\mathcal{C}}(\rho))\approx\operatorname{tr}(O\mathcal{C}(\rho))$.

##  VIII Comparison with prior work

Comparison with prior methods of information recovery and error mitigation.
Existing information recovery method [9] is not limited to Pauli channels but
it necessitates the full information of the channel is known. Prior to
applying this method of information recovery, if the channel is unknown, it is
necessary to obtain the full description of the channel via tomography, which
requires an extensive amount of quantum resources. Another limitation of the
method is that the effect of inaccurate channel description on the error of
information recovery has not been adequately investigated, hence the sample
complexity under approximate channel description is theoretically incomplete.
Compared to the method in Ref. [9], our proposed algorithm of information
recovery requires zero knowledge of a Pauli channel, and the computational
complexity scales polynomially with the number of qubits. Moreover, to
implement the method outlined in Ref. [9], one needs to implement arbitrary
CPTP maps, whereas our method only requires preparing Pauli eigenstates and
performing Pauli measurements, both of which are considerably easier to
realise on a quantum device.

There are also some methods used in quantum error mitigation that aim to
obtain an estimate of noiseless information $\operatorname{tr}(O\sigma)$ using
only copies of the noisy state. A commonly used method in error mitigation is
probabilistic error cancellation (PEC) [20], which starts by decomposing a
target process as a linear combination of implementable noisy processes. Using
this decomposition, the ideal circuit is realised by probabilistic sampling of
noisy processes. By definition, it works for arbitrary quantum processes, but
still faces similar problem of requiring full knowledge of the noisy
processes. Another example is virtual distillation [39, 40], which assumes the
dominant pure eigenvector of the mixed noisy state is the noiseless state. By
using multiple copies of the noisy states, we can obtain the noiseless
expectation value. However, copies need to be used at the same time which
means the circuit width is high. Although there are some variants that trade
circuit depth with width [41] or combine with the framework of classical
shadows [42] to reduce the circuit width, the total complexity is still
exponential in the number of qubits.

Differences with learning to predict quantum processes. Our proposed algorithm
is inspired by the method proposed in Ref. [15] that aims to predict the value
of $\operatorname{tr}(O\mathcal{P}(\rho))$ from access to $\mathcal{P}$ and
$\rho$, whereas we want to recover the original information from noisy
$\mathcal{P}(\rho)$. The authors do so by estimating the resultant observable
$\mathcal{P}(O)$ from collected classical shadows. We use similar estimation
techniques to learn the eigenvalues of the Pauli channel. In the end, they can
guarantee accuracy to $\epsilon$ for the mean squared error over a restricted
set of states but allow for arbitrary observable to be predicted. Whereas we
can predict up to accuracy for the absolute error for any noisy state but only
local observables.

Comparison with Pauli channel learning. Not requiring a complete description
of the noise channel is one of the main advantages of our algorithm over
existing methods. We remark that numerous algorithms are capable of estimating
the probability distribution $p(P)$ or the error rates for Pauli channels,
which is commonly referred to as Pauli channel learning [17, 43, 38, 36, 44].
We make careful comparison with Ref. [43] whose setting is the most similar to
the learning part of our algorithm. In Ref. [43], their main method involves
preparing random product Pauli eigenstates whose eigenvalue is $+1$, send them
through the channel then measure each qubit in the same basis as the input
state. Using the data collected, they turn the problem of estimating error
rates into a population recovery-type problem and use tools from that area to
estimate single Pauli error rate. They do this for $\frac{4}{\epsilon}$ of the
Pauli operators whose estimates are greater than $\frac{\epsilon}{2}$ and set
the rest to $0$ to guarantee the efficiency of the algorithm while making sure
that the $l_{\infty}$-norm of the difference is less than $\epsilon$. The
sample complexity is $\mathcal{O}(\log(n/\epsilon\delta)/\epsilon^{2})$.
Although the data collected is similar to our method, the post-processing and
the quantity to estimate are quite different. Firstly, we also measure the
output state in random Pauli basis. This allows us to extend our framework to
a broader group of channel like product channels, which we have discussed in
Section VI. Secondly, the Pauli error rates are related to the Pauli
eigenvalues by a Hadamard transform, i.e.

$\displaystyle\lambda_{P}$ $\displaystyle=\sum_{Q\in\\{I.X.Y.Z\\}^{\otimes
n}}(-1)^{\langle P,Q\rangle}p(Q)$ (30) $\displaystyle\text{where }\langle
P,Q\rangle$ $\displaystyle=\begin{cases}0&\text{if $P$ and $Q$ commute}\\\
1&\text{if $P$ and $Q$ anti-commute}\end{cases}$ (31)

This means that obtaining the eigenvalue of a single Pauli operator requires
knowledge of all Pauli error rates and vice versa. Also estimating error rates
element wise to accuracy $\epsilon$ cannot guarantee to estimate eigenvalues
element wise to accuracy $\epsilon$ and vice versa. The authors also present a
method for estimating single eigenvalue for a given Pauli operator with sample
complexity $\mathcal{O}(\log(1/\delta)/\epsilon^{2})$, then treat it as a
query access and use it to estimate the error rates, which is similar in
spirit but their estimate is restricted to the specific Pauli that they query.

##  IX Concluding remarks

In this work, we have introduced an efficient quantum algorithm that could
retrieve information from an unknown Pauli noise by learning the channel and
the noisy state, using quantum resources that scale polynomially in the number
of qubits. The efficiency of the proposed algorithm comes from the fact that
only partial knowledge of the channel is required to recover the ideal
information for a local and bounded-degree observable. For learning partial
eigenvalues of the Pauli channel, we have proved a lower bound on the sample
complexity that matches the upper bound of our channel learning algorithm,
which implies the optimality of the algorithm. We have also shown that the
method can be directly applied to recover information from noisy Clifford
circuits in a more efficient way than that of previous error mitigation
methods such as probabilistic error cancellation.

The method described in our work should be broadly applicable to mitigate
Pauli noise for large-scale quantum devices. For further theoretical
exploration, it would be interesting to extend the algorithm for information
recovery to a wider range of quantum channels. For the practical aspect of
this method, it is worthwhile to investigate the integration of general error
mitigation schemes, which could lead to a potential resource-efficient method
for early fault-tolerant quantum computers [45, 46]. We also anticipate that
this method will be useful for reducing the effect of noise and improving the
accuracy in near-term experiments. Specifically, we expect it to be applied
for enhancing the performance of variational quantum algorithms on noisy
devices with limited number of resources and contributing for exploring
physically relevant properties in material science [47] and chemistry [48,
49].

###### Acknowledgements.

Part of this work was done when Y. C., Z. Y., and C. Z. were research interns
at Baidu Research. X. W. would like to thank Xuanqiang Zhao for helpful
discussions.

## References

  * Childs and van Dam [2010] A. M. Childs and W. van Dam, Quantum algorithms for algebraic problems, Reviews of Modern Physics 82, 1 (2010).
  * Preskill [2018] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm (2014), arxiv:arXiv:1411.4028 .
  * Biamonte  _et al._ [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).
  * Wallman and Emerson [2016] J. J. Wallman and J. Emerson, Noise tailoring for scalable quantum computation via randomized compiling, Physical Review A 94, 052325 (2016).
  * Hashim  _et al._ [2021] A. Hashim, R. K. Naik, A. Morvan, J.-L. Ville, B. Mitchell, J. M. Kreikebaum, M. Davis, E. Smith, C. Iancu, K. P. O’Brien, I. Hincks, J. J. Wallman, J. Emerson, and I. Siddiqi, Randomized Compiling for Scalable Quantum Computing on a Noisy Superconducting Quantum Processor, Physical Review X 11, 041039 (2021).
  * Jiang  _et al._ [2021] J. Jiang, K. Wang, and X. Wang, Physical Implementability of Linear Maps and Its Application in Error Mitigation, Quantum 5, 600 (2021).
  * Zhao  _et al._ [2023] X. Zhao, B. Zhao, Z. Xia, and X. Wang, Information recoverability of noisy quantum states, Quantum 7, 978 (2023).
  * Chuang and Nielsen [1997] I. L. Chuang and M. A. Nielsen, Prescription for experimental determination of the dynamics of a quantum black box, Journal of Modern Optics 44, 2455 (1997).
  * Altepeter  _et al._ [2003] J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O’Brien, M. A. Nielsen, and A. G. White, Ancilla-Assisted Quantum Process Tomography, Physical Review Letters 90, 193601 (2003).
  * Mohseni  _et al._ [2008] M. Mohseni, A. T. Rezakhani, and D. A. Lidar, Quantum-process tomography: Resource analysis of different strategies, Physical Review A 77, 032322 (2008).
  * Aaronson [2018] S. Aaronson, Shadow tomography of quantum states, in  _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_, STOC 2018 (Association for Computing Machinery, New York, NY, USA, 2018) pp. 325–338.
  * Huang  _et al._ [2020] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050 (2020).
  * Huang  _et al._ [2022] H.-Y. Huang, S. Chen, and J. Preskill, Learning to predict arbitrary quantum processes (2022), arxiv:arXiv:2210.14894 .
  * Flammia and O’Donnell [2021a] S. T. Flammia and R. O’Donnell, Pauli error estimation via Population Recovery, Quantum 5, 549 (2021a), arxiv:2105.02885 [quant-ph] .
  * Chen  _et al._ [2022] S. Chen, S. Zhou, A. Seif, and L. Jiang, Quantum advantages for Pauli channel estimation, Physical Review A 105, 032435 (2022), arxiv:2108.08488 [quant-ph] .
  * Caro [2022] M. C. Caro, Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix (2022), arxiv:arXiv:2212.04471 .
  * Huang  _et al._ [2021] H.-Y. Huang, R. Kueng, and J. Preskill, Information-Theoretic Bounds on Quantum Advantage in Machine Learning, Physical Review Letters 126, 190505 (2021).
  * Temme  _et al._ [2017] K. Temme, S. Bravyi, and J. M. Gambetta, Error Mitigation for Short-Depth Quantum Circuits, Physical Review Letters 119, 180509 (2017).
  * Wilde [2017] M. M. Wilde,  _Quantum Information Theory_ (Cambridge University Press, Cambridge, 2017).
  * Watrous [2018] J. Watrous,  _The Theory of Quantum Information_ (Cambridge University Press, 2018).
  * Hayashi [2017] M. Hayashi,  _Quantum Information Theory_, Graduate Texts in Physics (Springer Berlin Heidelberg, Berlin, Heidelberg, 2017).
  * Hadfield  _et al._ [2022] C. Hadfield, S. Bravyi, R. Raymond, and A. Mezzacapo, Measurements of Quantum Hamiltonians with Locally-Biased Classical Shadows, Communications in Mathematical Physics 391, 951 (2022), arXiv:2006.15788 .
  * Wu  _et al._ [2023] B. Wu, J. Sun, Q. Huang, and X. Yuan, Overlapped grouping measurement: A unified framework for measuring quantum states, Quantum 7, 896 (2023), arXiv:2105.13091 .
  * Gebhart  _et al._ [2023] V. Gebhart, R. Santagati, A. A. Gentile, E. M. Gauger, D. Craig, N. Ares, L. Banchi, F. Marquardt, L. Pezzè, and C. Bonato, Learning quantum systems, Nature Reviews Physics 5, 141 (2023).
  * Coopmans  _et al._ [2023] L. Coopmans, Y. Kikuchi, and M. Benedetti, Predicting Gibbs-State Expectation Values with Pure Thermal Shadows, PRX Quantum 4, 010305 (2023).
  * Nguyen  _et al._ [2022] H. C. Nguyen, J. L. Bönsel, J. Steinberg, and O. Gühne, Optimizing Shadow Tomography with Generalized Measurements, Physical Review Letters 129, 220502 (2022).
  * Zhao  _et al._ [2021] A. Zhao, N. C. Rubin, and A. Miyake, Fermionic Partial Tomography via Classical Shadows, Physical Review Letters 127, 110504 (2021).
  * Huang [2022] H.-Y. Huang, Learning quantum states from their classical shadows, Nature Reviews Physics 4, 81 (2022).
  * Elben  _et al._ [2022] A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The randomized measurement toolbox, Nature Reviews Physics 5, 9 (2022).
  * Low [2022] G. H. Low, Classical shadows of fermions with particle number symmetry, arXiv preprint arXiv:2208.08964 (2022), arXiv:2208.08964 .
  * Bu  _et al._ [2022] K. Bu, D. E. Koh, R. J. Garcia, and A. Jaffe, Classical shadows with Pauli-invariant unitary ensembles, arXiv preprint arXiv:2202.03272 (2022), arXiv:2202.03272 .
  * Wan  _et al._ [2022] K. Wan, W. J. Huggins, J. Lee, and R. Babbush, Matchgate Shadows for Fermionic Quantum Simulation, arXiv preprint arXiv:2207.13723 (2022), arXiv:2207.13723 .
  * Becker  _et al._ [2022] S. Becker, N. Datta, L. Lami, and C. Rouzé, Classical shadow tomography for continuous variables quantum systems, arXiv preprint arXiv:2211.07578 (2022), arXiv:2211.07578 .
  * Fawzi  _et al._ [2023] O. Fawzi, A. Oufkir, and D. S. França, Lower Bounds on Learning Pauli Channels (2023), arxiv:2301.09192 [quant-ph] .
  * Chen  _et al._ [2021] S. Chen, W. Yu, P. Zeng, and S. T. Flammia, Robust shadow estimation, PRX Quantum 2, 030348 (2021).
  * Flammia and Wallman [2020] S. T. Flammia and J. J. Wallman, Efficient estimation of pauli channels, ACM Transactions on Quantum Computing 1, 1 (2020).
  * Koczor [2021] B. Koczor, Exponential Error Suppression for Near-Term Quantum Devices, Physical Review X 11, 031057 (2021).
  * Huggins  _et al._ [2021] W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean, Virtual Distillation for Quantum Error Mitigation, Physical Review X 11, 041036 (2021).
  * Czarnik  _et al._ [2021] P. Czarnik, A. Arrasmith, L. Cincio, and P. J. Coles, Qubit-efficient exponential suppression of errors (2021), arxiv:2102.06056 [quant-ph] .
  * Seif  _et al._ [2023] A. Seif, Z.-P. Cian, S. Zhou, S. Chen, and L. Jiang, Shadow Distillation: Quantum Error Mitigation with Classical Shadows for Near-Term Quantum Processors, PRX Quantum 4, 010303 (2023).
  * Flammia and O’Donnell [2021b] S. T. Flammia and R. O’Donnell, Pauli error estimation via population recovery, Quantum 5, 549 (2021b).
  * Harper  _et al._ [2020] R. Harper, S. T. Flammia, and J. J. Wallman, Efficient learning of quantum noise, Nature Physics 16, 1184 (2020).
  * Suzuki  _et al._ [2022] Y. Suzuki, S. Endo, K. Fujii, and Y. Tokunaga, Quantum error mitigation as a universal error reduction technique: Applications from the NISQ to the fault-tolerant quantum computing eras, PRX Quantum 3, 10.1103/prxquantum.3.010345 (2022).
  * Piveteau  _et al._ [2021] C. Piveteau, D. Sutter, S. Bravyi, J. M. Gambetta, and K. Temme, Error mitigation for universal gates on encoded qubits, Physical Review Letters 127, 10.1103/physrevlett.127.200505 (2021).
  * Ma  _et al._ [2020] H. Ma, M. Govoni, and G. Galli, Quantum simulations of materials on near-term quantum computers, npj Computational Materials 6, 85 (2020).
  * Nam  _et al._ [2020] Y. Nam, J.-S. Chen, N. C. Pisenti, K. Wright, C. Delaney, D. Maslov, K. R. Brown, S. Allen, J. M. Amini, J. Apisdorf, _et al._ , Ground-state energy estimation of the water molecule on a trapped-ion quantum computer, npj Quantum Information 6, 33 (2020).
  * Cao  _et al._ [2019] Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, and N. P. D. Sawaya, Quantum chemistry in the age of quantum computing, Chemical reviews 119, 10856 (2019).

##  Appendix A Proof of Lemma 2

###### Lemma S1

Let $\mathcal{P}$ be an $n$-qubit Pauli channel with eigenvalues
$\\{\lambda_{P}\\}_{P}$ so that $\mathcal{P}(P)=\lambda_{P}P$ for Pauli
operators $P\in\\{I,X,Y,Z\\}^{\otimes n}$, $\mathcal{D}^{0}$ be the uniform
distribution of product state of Pauli eigenstates. We have

$\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)=\bigg{(}\frac{1}{3}\bigg{)}^{|P|}\lambda_{P}.$
(A.1)

###### Proof.

We have

$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)$
(A.2) $\displaystyle=$
$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(\mathcal{P}(P)\rho)\operatorname{tr}(P\rho)$
(A.3) $\displaystyle=$
$\displaystyle\lambda_{P}\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(P\rho)^{2}.$
(A.4)

Writing $\operatorname{tr}(P\rho)=\prod_{i}\operatorname{tr}(P_{i}\rho_{i})$,
we can see that if $P_{i}=I$, then $\operatorname{tr}(P_{i}\rho_{i})=1$. If
$P_{i}\neq I$, then $\operatorname{tr}(P_{i}\rho_{i})^{2}=1$ with probability
$1/3$ and $\operatorname{tr}(P_{i}\rho_{i})^{2}=0$ with probability $2/3$,
hence
$\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(P\rho)^{2}=(1/3)^{|P|}$
and complete the proof.  $\sqcap$$\sqcup$

##  Appendix B Proof of Theorem 3

Before proving the proposition, we first introduce a few lemmas that help us
to bound the error.

###### Lemma S2

The difference between two observable expectation estimations can be upper
bounded by the difference in the Pauli decomposition of observables,

$\lvert\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\rvert\leq\sum_{P}\lvert\Delta\alpha_{P}\rvert,$
(B.1)

where $\Delta\alpha_{P}$ is the coefficient of $P$ in the Pauli expansion of
$O_{1}-O_{2}$.

###### Proof.

$\displaystyle\lvert\operatorname{tr}(O_{1}\rho)-\operatorname{tr}(O_{2}\rho)\rvert$
(B.2) $\displaystyle\leq$
$\displaystyle\lvert\sum_{P}\Delta\alpha_{P}\operatorname{tr}(P\rho)\rvert$
(B.3) $\displaystyle\leq$ $\displaystyle\sum_{P}|\Delta\alpha_{P}\rvert,$
(B.4)

where in the last line we use the triangle inequality and the fact that
$\left\lvert\operatorname{tr}(P\rho)\right\rvert\leq 1$.  $\sqcap$$\sqcup$

###### Definition S1

The _degree_ of a bounded-degree observable is the maximum number of terms in
the sum that act on each qubit.

######  Lemma S3 (Corollary 12 in Ref. [15])

Given an $n$-qubit $k$-local bounded-degree Hamiltonian $O$ with degree $d$.
We have

$\frac{1}{3}C(k,d)\left\lVert O\right\rVert_{\mathrm{Pauli},1}\leq\lVert
O\rVert,$ (B.5)

where $C(k,d)=\frac{\sqrt{2(k!)}}{\sqrt{d}k^{k+2.5}(2\sqrt{6}+4\sqrt{3})^{k}}$
and $\lVert O\rVert$ is the spectral norm of $O$.

###### Theorem S4

Given an unknown $n$-qubit Pauli channel $\mathcal{P}$, a noisy state ${\cal
P}(\sigma)$, and an $n$-qubit bounded-degree $k$-local observable $O$ where
$k=\mathcal{O}(1)$. For $\epsilon,\delta>0$, there exists an algorithm that
uses $N=\mathcal{O}(\log(n^{k}/\delta)/\epsilon^{2})$ accesses to the channel
to obtain a function $f(\mathcal{P}(\sigma),O)$ such that

$\left\lvert
f(\mathcal{P}(\sigma),O)-\operatorname{tr}(O\sigma)\right\rvert\leq\epsilon$
(B.6)

with probability at least $1-\delta$. The computation time is
$\mathcal{O}(n^{k}\log(n^{k}))$.

###### Proof.

The structure of the proof is as follows: we first use Hoeffding’s lemma to
establish a relation between $N$, the number of channel uses, and
$\tilde{\epsilon}$, the accuracy which we need to estimate $\lambda_{P}$ to.
The proof is concluded once we find the relation between $\tilde{\epsilon}$
and $\epsilon$.
We let $x_{P}=(1/3)^{\left\lvert P\right\rvert}\lambda_{P}$, $D(n,k)$ be the
number of n-qubit Pauli operator with weight $k$ and
$T(n,k)=\sum_{l=0}^{k}D(n,l)$. Note that
$D(n,k)=\binom{n}{k}3^{k}=\mathcal{O}(n^{k})$.
We let $\tilde{\epsilon}$ to be determined later,
$\tilde{\epsilon}^{\prime}=\tilde{\epsilon}/3^{k}$. By Lemma 2 and Hoeffding’s
inequality,

$\mathbb{P}(|\widehat{x}_{P}-x_{P}|\geq\tilde{\epsilon}^{\prime})\leq
2e^{-N\tilde{\epsilon}^{\prime 2}/2\times 3^{2k}}\quad\forall P,|P|\leq k.$
(B.7)

By a union bound,

$\displaystyle\mathbb{P}(|\widehat{x}_{P}-x_{P}|\leq\tilde{\epsilon}^{\prime}\quad\forall
P,|P|\leq k)$ (B.8) $\displaystyle\geq$ $\displaystyle
1-\bigcup_{P}\mathbb{P}(|\widehat{x}_{P}-x_{P}|\geq\tilde{\epsilon}^{\prime})$
(B.9) $\displaystyle\geq$ $\displaystyle
1-2\sum_{l=0}^{k}D(n,l)e^{-N\tilde{\epsilon}^{\prime 2}/{2\times 3^{2k}}}.$
(B.10)

Equating the last term to $1-\delta$ we get that we require

$N=\frac{2\times 3^{2k}\log(2T(n,k)/\delta)}{\tilde{\epsilon}^{\prime 2}}.$
(B.11)

Using the fact that $T(n,k)=\mathcal{O}(n^{k})$, we have
$N=\mathcal{O}(\log(n^{k}/\delta)/\tilde{\epsilon}^{\prime 2})$. By definition
of $\tilde{\epsilon}^{\prime}$, we also have with probability at least
$1-\delta$,

$|\widehat{\lambda}_{P}-\lambda_{P}|\leq\tilde{\epsilon}\quad\forall P,|P|\leq
k.$ (B.12)

From now on, conditioned on the above event. Using Lemma S2,

$\displaystyle\lvert
f(\mathcal{P}(\sigma),O)-\operatorname{tr}(O\sigma)\rvert$ (B.13)
$\displaystyle=$
$\displaystyle\lvert\operatorname{tr}(\mathcal{P}(\overleftarrow{O})\sigma)-\operatorname{tr}(O\sigma)|$
(B.14) $\displaystyle\leq$ $\displaystyle\sum_{P\mathrel{\mathop{\mathchar
58\relax}}|P|\leq k}|\lambda_{P}\overleftarrow{\alpha}_{P}-\alpha_{P}|$ (B.15)
$\displaystyle=$ $\displaystyle\sum_{P\mathrel{\mathop{\mathchar
58\relax}}|P|\leq
k}\left\lvert\frac{\lambda_{P}}{\widehat{\lambda}_{P}}\alpha_{P}-\alpha_{P}\right\rvert.$
(B.16)

We can write $\widehat{\lambda}_{P}=\lambda_{P}+\Delta_{P}$ where by Eq. B.12
we have that $\left\lvert\Delta_{P}\right\rvert<\tilde{\epsilon}$. We also
assume that $\tilde{\epsilon}<\lambda_{P}$, which will be validated when we
determine the value of $\tilde{\epsilon}$ later. Hence,

$\displaystyle\sum_{P\mathrel{\mathop{\mathchar 58\relax}}|P|\leq
k}\left\lvert\lambda_{P}\widehat{\lambda}_{P}^{-1}\alpha_{P}-\alpha_{P}\right\rvert$
(B.17) $\displaystyle=$ $\displaystyle\sum_{P\mathrel{\mathop{\mathchar
58\relax}}|P|\leq
k}\left\lvert\lambda_{P}\lambda_{P}^{-1}\left(1+\frac{\Delta_{P}}{\lambda_{P}}\right)^{-1}\alpha_{P}-\alpha_{P}\right\rvert$
(B.18) $\displaystyle=$ $\displaystyle\sum_{P\mathrel{\mathop{\mathchar
58\relax}}|P|\leq
k}\left\lvert\left(1-\frac{\Delta_{P}}{\lambda_{P}}+\mathcal{O}(\Delta_{P}^{2})\right)\alpha_{P}-\alpha_{P}\right\rvert.$
(B.19)

Assume $\tilde{\epsilon}^{2}$ is negligible, and define
$\lambda^{(k)}_{\min}=\min_{P\mathrel{\mathop{\mathchar 58\relax}}|P|\leq
k}|\lambda_{P}|$. So
$|\Delta_{P}/\lambda_{P}|\leq|\tilde{\epsilon}/\lambda^{(k)}_{\min}|$,

$\displaystyle\sum_{P\mathrel{\mathop{\mathchar 58\relax}}|P|\leq
k}\left\lvert\left(1-\frac{\Delta_{P}}{\lambda_{P}}+\mathcal{O}(\Delta_{P}^{2})\right)\alpha_{P}-\alpha_{P}\right\rvert$
(B.20) $\displaystyle\leq$
$\displaystyle\bigg{(}\frac{\tilde{\epsilon}}{\lambda^{(k)}_{\min}}\bigg{)}\bigg{(}\sum_{P\mathrel{\mathop{\mathchar
58\relax}}|P|\leq k}|\alpha_{P}|\bigg{)}$ (B.21) $\displaystyle\leq$
$\displaystyle\bigg{(}\frac{\tilde{\epsilon}}{\lambda^{(k)}_{\min}}\bigg{)}\bigg{(}\left\lVert
O\right\rVert_{\mathrm{Pauli},1}\bigg{)}$ (B.22) $\displaystyle\leq$
$\displaystyle\bigg{(}\frac{\tilde{\epsilon}}{\lambda^{(k)}_{\min}}\bigg{)}\bigg{(}\frac{3\lVert
O\rVert}{C(k,d)}\bigg{)}$ (B.23) $\displaystyle=$
$\displaystyle\frac{3}{\lambda^{(k)}_{\min}C(k,d)}\tilde{\epsilon},$ (B.24)

where we used the bound on Pauli-1 norm from Lemma S3 and $d$ is the degree of
$O$. By setting

$\tilde{\epsilon}=\frac{\lambda^{(k)}_{\min}C(k,d)}{3}\epsilon,$ (B.25)

we have

$\left\lvert
f(\mathcal{P}(\sigma))-\operatorname{tr}(O\sigma)\right\rvert\leq\epsilon.$
(B.26)

In conclusion,
$N=\mathcal{O}(\log(n^{k}/\delta)/\tilde{\epsilon}^{2})=\mathcal{O}(\log(n^{k}/\delta)/\epsilon^{2})$.
For total computational complexity, step 3 of the algorithm requires
$\mathcal{O}(n^{k}\cdot N\cdot k)$ computations, step 4 and 5 of the algorithm
both require $\mathcal{O}(n^{k})$ computations conditioned on our assumptions
that values of $\operatorname{tr}(P\mathcal{P}(\sigma))$ is known. So the
overall computational complexity is
$\mathcal{O}(Nkn^{k})=\mathcal{O}(n^{k}\log(n^{k}))$.  $\sqcap$$\sqcup$

##  Appendix C Optimality of sample complexity of channel

First, we elaborate the task mentioned in Proposition 4:

###### Problem S1

Given a Pauli channel $\mathcal{P}$. Let $\lambda^{(k)}$ denote the vector of
eigenvalue of $\mathcal{P}$ for Pauli operators whose weight are at most $k$.
We suppress the superscript when the value of $k$ does not change. We would
like an algorithm that learns $\widehat{\lambda}$ such that
$\lvert\widehat{\lambda}_{P}-\lambda_{P}\lvert\leq\epsilon$ with high
probability by $N$ accesses of the channel. More precisely, for each access,
the user can prepare an arbitrary input state, send it through the channel and
measure the output state using arbitrary POVM. In terms of notations, for the
$t$th access, the user prepare the state $\rho_{t}$ and obtain output state
$\mathcal{P}(\rho_{t})$. Finally, the user measures using POVM
$\\{\lambda^{t}_{i}\lvert\phi_{i}\rangle\\!\langle\phi_{i}\rvert\\}$ where
$\sum_{i}\lambda^{t}_{i}\lvert\phi_{i}\rangle\\!\langle\phi_{i}\rvert=I$.

Algorithm 1 indeed fits the above description and provides an upper bound for
the problem. We now prove that

###### Proposition S5

To solve S1, the number of channel use $N$ is at least
$\Omega(\log(n^{k})/\epsilon^{2})$.

###### Proof.

We follow the idea outlined in [17, 19] and [36]. We first construct a set of
Pauli channels labelled by $(P,s)$:

$\mathcal{P}_{(P,s)}(\rho)\coloneqq\operatorname{tr}(\rho)\frac{I}{2^{n}}+2\epsilon
s\frac{\operatorname{tr}(P\rho)}{2^{n}}P,$ (C.1)

for $P\mathrel{\mathop{\mathchar 58\relax}}P\neq I,|P|\leq k$, $s\in\\{\pm
1\\}$. We further define $T(n,k)=\sum_{l=1}^{k}\binom{n}{l}3^{l}$, each term
in the summation is the number of Pauli operators with weight $l$, so the set
defined by Eq. C.1 contains $2T(n,k)$ elements. The eigenvalues of each
channel is either $0$ or $\pm 2\epsilon$, so if we can learn each element of
$\lambda^{(k)}$ up to accuracy $\epsilon$ with probability at least
$1-\delta$, then we can determine which Pauli channel has been given. Hence we
can use this set for a theoretical quantum communication task. Suppose Alice
and Bob agreed an ordering of $\\{\mathcal{P}_{(P,s)}\\}_{(P,s)}$. Then Alice
picks a number in $[2T(n,k)]$ uniformly at random and sends $N$ copies of the
corresponding channel to Bob. Once Bob received them, he can use the protocol
that can solve S1 to successfully decode Alice’s message with probability at
least $1-\delta$. If we call the uniform distribution on $(P,s)$ $X$, and
distribution of Bob’s guesses $\widehat{X}$, then by Fano’s inequality,

$H(X\mid\widehat{X})\leq\delta\log(2T(n,k)-1)+h(\delta),$ (C.2)

where $h(p)$ is the binary entropy of $\\{p,1-p\\}$. This then implies that

$I(X\mathrel{\mathop{\mathchar
58\relax}}\widehat{X})=H(X)-H(X\mid\widehat{X})\geq\log(2T(n,k))-h(\delta)-\delta\log(2T(n,k)-1)=\Omega(\log(n^{k})).$
(C.3)

Recall that Bob’s protocol involves choosing an input state $\rho$, sending it
through the channel and measuring using POVM. Let $I_{t}$ denotes the random
variable for Bob’s $t$th measurement outcome. Since $\widehat{X}$ is a
function of $I_{1},\ldots,I_{N}$, by data processing inequality and the chain
rule,

$\displaystyle I(X\mathrel{\mathop{\mathchar 58\relax}}\widehat{X})$
$\displaystyle\leq I(X\mathrel{\mathop{\mathchar
58\relax}}I_{1},\ldots,I_{N})$ (C.4)
$\displaystyle=\sum_{t=1}^{N}I(X\mathrel{\mathop{\mathchar 58\relax}}I_{t}\mid
I_{1},\ldots,I_{t-1})$ (C.5)
$\displaystyle\leq\sum_{t=1}^{N}I(X\mathrel{\mathop{\mathchar
58\relax}}I_{t}).$ (C.6)

Before we proceed, we make some preliminary calculations. Let
$\Pr(i_{t}\mid(P,s))$ be the probability that the $t$th measurement result is
$i_{t}$ given that the channel received is $(P,s)$, we have that

$\displaystyle\Pr(i_{t}\mid(P,s))$
$\displaystyle=\lambda_{i_{t}}\bra{\phi^{t}_{i_{t}}}\frac{I}{2^{n}}+2\epsilon
s\frac{\operatorname{tr}(P\rho_{t})}{2^{n}}P\ket{\phi_{i_{t}}}$ (C.7)
$\displaystyle=\frac{\lambda_{i_{t}}}{2^{n}}[1+2\epsilon
s\operatorname{tr}(P\rho_{t})\bra{\phi^{t}_{i_{t}}}P\ket{\phi^{t}_{i_{t}}}].$
(C.8)

From this, we can calculate $\Pr(i_{t})$ by taking the marginal:

$\Pr(i_{t})=\underset{P,s}{\mathbb{E}}\Pr(i_{t}\mid(P,s))=\frac{\lambda_{i_{t}}}{2^{n}}.$
(C.9)

Furthermore, we calculate the squared quantities,

$\underset{P,s}{\mathbb{E}}\Pr(i_{t}\mid(P,s))^{2}=\frac{(\lambda^{t}_{i_{t}})^{2}}{2^{2n}}[1+4\epsilon^{2}\underset{P}{\mathbb{E}}\big{[}\operatorname{tr}(P\rho_{t})]^{2}\bra{\phi^{t}_{i_{t}}}P\ket{\phi^{t}_{i_{t}}}^{2}\big{]}\leq\frac{(\lambda^{t}_{i_{t}})^{2}}{2^{2n}}[1+4\epsilon^{2}].$
(C.10)

Now continue from Eq. C.6, we want to bound $I(X\mathrel{\mathop{\mathchar
58\relax}}I_{t})$. By definition of mutual information, we have

$\displaystyle I(X\mathrel{\mathop{\mathchar 58\relax}}I_{t})$
$\displaystyle=H(I_{t})-H(I_{t}\mid X)$ (C.11)
$\displaystyle=-\sum_{i_{t}}\Pr(i_{t})\log\Pr(i_{t})+\underset{P,s}{\mathbb{E}}\sum_{i_{t}}\Pr(i_{t}\mid(P,s))\log\Pr(i_{t}\mid(P,s))$
(C.12)
$\displaystyle\leq-\sum_{i_{t}}\Pr(i_{t})\log\Pr(i_{t})+\underset{P,s}{\mathbb{E}}\sum_{i_{t}}\Pr(i_{t}\mid(P,s))\bigg{[}\log\Pr(i_{t})+\frac{\Pr(i_{t}\mid(P,s))-\Pr(i_{t})}{\Pr(i_{t})}\bigg{]}$
(C.13)
$\displaystyle=\sum_{i_{t}}\frac{\underset{P,s}{\mathbb{E}}\Pr(i_{t}\mid(P,s))^{2}-\Pr(i_{t})^{2}}{\Pr(i_{t})}$
(C.14)
$\displaystyle\leq\sum_{i_{t}}\frac{\lambda^{t}_{i_{t}}}{2^{n}}4\epsilon^{2}$
(C.15) $\displaystyle=4\epsilon^{2},$ (C.16)

where the third line follows from $\log x\leq\log y+\frac{x-y}{y}$ and taking
$x=\Pr(i_{t}\mid(P,s))$, $y=\Pr(i_{t})$. The second to last line comes from
Eq. C.10 and the last line follows from the fact that
$\sum_{i_{t}}\lambda^{t}_{i_{t}}=2^{n}$.
Combine this with Eqs. C.3, LABEL: and C.6, we have that
$N=\Omega(\log(n^{k})/\epsilon^{2})$.  $\sqcap$$\sqcup$

##  Appendix D Clifford shadows

In Algorithm 1, we only consider collecting Pauli shadows of the channel, and
a natural question to ask is what happens if we use the highly related
Clifford shadow and whether it yields better sample complexity. For classical
shadows of a quantum state, the complexity for using Clifford shadow is given
by

######  Proposition S6 ([14])

Adopt a random Clifford basis primitive, where each random unitary is
uniformly selected from the $n$-qubit Clifford group. Given a collection of
observables $O_{1},O_{2},\ldots,O_{M}$, accuracy parameters
$\epsilon,\delta\in[0,1]$, then

$\displaystyle
N=\mathcal{O}\left(\frac{\log(M/\delta)}{\epsilon^{2}}\max_{i}\operatorname{tr}(O_{i}^{2})\right)$
(D.1)

samples are required to simultaneously predict each
$\operatorname{tr}(O_{i}\rho)$ up to accuracy $\epsilon$ with success
probability $1-\delta$.

Compared to Proposition 1, we can see that Pauli shadows have better
complexity when the locality of the observables is low, but in the case of
$k=n$, Clifford shadows give better complexity. Here, we show a similar result
stating that Clifford shadows cannot provide any benefits for sample
complexity under the assumption that the locality of the observable is
$k=\mathcal{O}(1)$. Firstly, we have the following result when we change the
input distribution:

###### Proposition S7

Given an $n$-qubit observable $O=\sum_{P}\alpha_{P}P$ and let $\mathcal{D}$ be
a distribution of $n$-qubit states that is invariant under any $n$-qubit
Clifford gate. Then for Pauli $P\in\\{I,X,Y,Z\\}^{\otimes
n}\backslash\\{I^{\otimes n}\\}$, we have

$\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)=\frac{2^{n}\mathbb{E}_{\rho\sim\mathcal{D}}\operatorname{tr}(\rho^{2})-1}{4^{n}-1}\alpha_{P}.$
(D.2)

For $P=I^{\otimes n}$, we have that

$\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)=\alpha_{I}.$
(D.3)

###### Proof.

We follow the same spirit as proof of Lemma 16 of [15]. Writing
$O=\sum_{Q}\alpha_{Q}Q$, we have that

$\displaystyle\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)$
(D.4) $\displaystyle=$
$\displaystyle\sum_{Q}\alpha_{Q}\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\operatorname{tr}(Q\rho)\operatorname{tr}(P\rho)$
(D.5) $\displaystyle=$
$\displaystyle\sum_{Q}\alpha_{Q}\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\operatorname{tr}\big{(}(Q\otimes
P)(\rho\otimes\rho)\big{)}.$ (D.6)

Since $\mathcal{D}$ is invariant under Clifford gates, we can conjugate $\rho$
by any Clifford gate and the expectation over $\rho$ does not change. In fact,
we can conjugate $\rho$ by a random Clifford gate. let $U$ be a random
$n$-qubit Clifford gate, we have that

$\displaystyle\sum_{Q}\alpha_{Q}\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\operatorname{tr}\big{(}(Q\otimes
P)(\rho\otimes\rho)\big{)}$ (D.7) $\displaystyle=$
$\displaystyle\sum_{Q}\alpha_{Q}\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\,\underset{U}{\mathbb{E}}\operatorname{tr}\big{(}(Q\otimes
P)(U\otimes U)(\rho\otimes\rho)(U\otimes U)^{\dagger}\big{)}$ (D.8)
$\displaystyle=$
$\displaystyle\sum_{Q}\alpha_{Q}\underset{\rho\sim\mathcal{D}}{\mathbb{E}}\,\underset{U}{\mathbb{E}}\operatorname{tr}\big{(}(U\otimes
U)^{\dagger}(Q\otimes P)(U\otimes U)(\rho\otimes\rho)\big{)}.$ (D.9)

To evaluate $\mathbb{E}_{U}(U\otimes U)^{\dagger}(Q\otimes P)(U\otimes U)$, we
use the property that Clifford gates form a 2-design which means that

$\underset{U}{\mathbb{E}}(U\otimes U)^{\dagger}(Q\otimes P)(U\otimes
U)=\int_{\mathcal{U}}(U\otimes U)(Q\otimes P)(U\otimes
U)^{\dagger}d\mathcal{U},$ (D.10)

where $\mathcal{U}$ is the Haar measure on the unitary group of $n$-qubits. To
evaluate the integral, we can use standard result:

###### Proposition S8

Let $\mathcal{U}(d)$ be the unitary group of $\mathbb{C}^{d}$, then for any
$X$ which is a linear operator acting on
$\mathbb{C}^{d}\otimes\mathbb{C}^{d}$, we have that

$\int_{\mathcal{U}(d)}(U\otimes U)X(U\otimes
U)^{\dagger}d\mathcal{U}=\bigg{(}\frac{\operatorname{tr}(X)}{d^{2}-1}-\frac{\operatorname{tr}(XF)}{d(d^{2}-1)}\bigg{)}id_{d^{2}}-\bigg{(}\frac{\operatorname{tr}(X)}{d(d^{2}-1)}-\frac{\operatorname{tr}(XF)}{d^{2}-1}\bigg{)}F,$
(D.11)

where $F$ is the swap operator.

Equation D.11 allows us to evaluate the integral in Eq. D.10 to obtain

$\int_{\mathcal{U}}(U\otimes U)(Q\otimes P)(U\otimes
U)^{\dagger}d\mathcal{U}=\begin{cases}\frac{2^{n}}{4^{n}-1}F-\frac{1}{4^{n}-1}id_{d^{2}}&\text{if
}Q=P\neq I^{\otimes n},\\\ id_{d^{2}}&\text{if }Q=P=I^{\otimes n},\\\
0&\text{if }Q\neq P,\end{cases}$ (D.12)

where $id$ denotes the identity map. Substitute this into Eq. D.6 and we
obtain the desired result.  $\sqcap$$\sqcup$

This means that our empirical estimation is exponentially small in $n$, which
gives an exponential factor to our sample complexity.

Secondly, if we reconstruct $\mathcal{P}(\rho_{i})$ using Clifford shadow, we
replace $\bigotimes_{j}(3\lvert t_{ij}\rangle\\!\langle t_{ij}\rvert-I)$ with
$(2^{n}+1)U^{\dagger}\lvert b\rangle\\!\langle b\rvert U-I$ during calculation
of $\widehat{x}_{P}$. Our empirical estimation still equals to $\lambda_{P}$
in expectation but the range of value it takes extends to
$[-(2^{n}+1),2^{n}+1]$, which also gives an exponential factor to our sample
complexity following Hoeffding’s inequality.

###### Remark 2

For $k=n$, using Pauli shadows would give a $3^{n}$ factor to our sampling
complexity. This is worse than both factors above which are about $2^{n}$.
This agrees with the intuition that random Pauli is preferred only for local
observables over random Clifford.

##  Appendix E Extension to other channels

For a general channel $\mathcal{E}$, the action of the adjoint map of the
channel $\mathcal{E}^{\dagger}$ is also a linear map. In fact, it is a
completely positive unital map, and it can be written as a matrix. We denote
$M$ be the matrix in Pauli basis. For Pauli channel, $M$ is a diagonal matrix.
It is formally defined as
$M_{PQ}=\frac{1}{2^{n}}\operatorname{tr}(P\mathcal{E}^{\dagger}(Q))$. This is
very similar to the Pauli transfer matrix of a quantum channel.

###### Definition S2

The Pauli transfer matrix $T$ of a quantum channel $\mathcal{N}$ is defined as
$T_{PQ}=\frac{1}{2^{n}}\operatorname{tr}(P\mathcal{N}(Q))$.

###### Proposition S9

Given a quantum channel $\mathcal{N}$, and let $T$ and $M$ be defined as
above, then $M=T^{\intercal}$, the transpose of $T$ taken with respect to the
Pauli basis.

###### Proof.

$M_{PQ}=\frac{1}{2^{n}}\operatorname{tr}(P\mathcal{N}^{\dagger}(Q))=\frac{1}{2^{n}}\operatorname{tr}(\mathcal{N}(P)Q)=T_{QP}$
where the second equality comes from definition of adjoint map.
$\sqcap$$\sqcup$

###### Proposition S10

Let $A$ be an $n\times n$ upper block triangular matrix with block size
$\\{a_{1},a_{2},\ldots,a_{m}\\}$. Let $s_{i}=\sum_{j=1}^{m}a_{j}$, so
$s_{m}=n$ and the $s_{i}\times s_{i}$ submatrices of $A$ are all upper block
triangular. Denote each submatrix as $A_{i}$ and assume each $A_{i}$ is
invertible. Given $b$ with $b_{k}=0$ $\forall k>s_{i}$ for some $i$, then
there exists $x$ with $x_{k}=0$ $\forall k>s_{i}$ such that $Ax=b$. To be more
specific, $x$ is given by $\begin{pmatrix}A_{i}^{-1}b^{(i)}\\\ 0\end{pmatrix}$
where $b^{(i)}$ denotes the subvector
$(b_{1},b_{2},\ldots,b_{s_{i}})^{\intercal}$ of $b$.

###### Proof.

Direct verification.  $\sqcap$$\sqcup$

The above observation ensures that if $M$ is upper block triangular with block
$i$ being the set of $i$-local Pauli operators, then to find the inverse of a
$k$-local observable under the adjoint map, one can achieve by finding
$s_{k}\times s_{k}$ submatrix of $M$ and the inverse is also a $k$-local
observable. From now on, when we refer to the term ‘upper block triangular’,
we mean upper block triangular with block $i$ being the set of $i$-local Pauli
operators. Pauli channel being a diagonal channel automatically satisfies the
upper block triangular condition. Another class of channels that meets this
criterion is product channel. Using Proposition S9, this condition also
translates to the Pauli transfer matrix being lower block triangular.

###### Proposition S11

If a noise channel factorises, i.e.
$\mathcal{N}=\bigotimes_{i}\mathcal{N}_{i}$, then the matrix of
$\mathcal{N}^{\dagger}$ in Pauli basis is upper block triangular.

###### Proof.

We notice that a necessary and sufficient condition for an adjoint map to be
upper triangular is that it preserves the weight of a Pauli operator. That is,
the Pauli decomposition of $\mathcal{N}^{\dagger}(P)$ does not contain terms
whose weight is greater than $P$, i.e.

$\mathcal{N}^{\dagger}(P)=\sum_{Q\mathrel{\mathop{\mathchar
58\relax}}\left\lvert Q\right\rvert\leq\left\lvert P\right\rvert}\alpha_{Q}Q.$
(E.1)

We say that $\mathcal{N}^{\dagger}$ is weight contracting. If a noise channel
$\mathcal{N}$ factorises, then its adjoint map also factorises, i.e.
$\mathcal{N}^{\dagger}=\bigotimes_{i}\mathcal{N}^{\dagger}_{i}$. Given a Pauli
operator $P=\bigotimes_{i}P_{i}$,
$\mathcal{N}^{\dagger}(P)=\bigotimes_{i}\mathcal{N}^{\dagger}_{i}(P_{i})$. If
$P_{i}=I$, $\mathcal{N}^{\dagger}_{i}(P_{i})=I$ since each
$\mathcal{N}^{\dagger}_{i}$ is an adjoint map itself and hence is unital.
Therefore the weight of $\mathcal{N}^{\dagger}(P)$ does not increases, hence
$\mathcal{N}^{\dagger}$ is weight contracting.  $\sqcap$$\sqcup$

To extend the previous method, instead of calculating the diagonal elements,
we need to calculate the entire upper triangular block matrix. Then taking the
inverse of the resultant matrix gives us estimation for $\overleftarrow{O}$.
Hence we can generalise the algorithm and theorem in Sections III and IV to
extend the set of channels which we can recover information for. Before doing
that, we will show how to estimate the non-diagonal element of $M$.

######  Lemma S12 (Lemma 16 of Ref. [15])

Given an n-qubit observable $O=\sum_{P}\alpha_{P}P$ and let $\mathcal{D}^{0}$
be the uniform distribution of product state of Pauli eigenstates. Then for
Pauli $P\in\\{I,X,Y,Z\\}^{\otimes n}$, we have

$\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(O\rho)\operatorname{tr}(P\rho)=\bigg{(}\frac{1}{3}\bigg{)}^{|P|}\alpha_{P}.$
(E.2)

If we take $O=\mathcal{E}^{\dagger}(Q)$ where $Q$ is a Pauli operator, then
the above lemma allows us to obtain the coefficient of
$\mathcal{E}^{\dagger}(Q)$, which corresponds to column $Q$ of $M$. More
specifically,

$\bigg{(}\frac{1}{3}\bigg{)}^{|P|}M_{PQ}=\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(\mathcal{E}^{\dagger}(Q)\rho)\operatorname{tr}(P\rho)=\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(Q\mathcal{E}(\rho))\operatorname{tr}(P\rho).$
(E.3)

Another difference is that instead of dividing each coefficient of our
observable by the corresponding estimated eigenvalue, we need to apply the
inverse of our estimated $M$ to the vector of coefficients. This involves
inverting a square matrix whose dimension of $\mathcal{O}(n^{k})$ which has
computational complexity of $\mathcal{O}(n^{3k})$. The updated algorithm and
its complexity are as follows:

Algorithm 2 Modified algorithm for weight contracting channel

1:Unknown weight contracting channel $\mathcal{E}$, $k$-local observable
$O=\sum_{P}\alpha_{P}P$, copies of unknown noisy state $\mathcal{E}(\sigma)$

2:Estimation of $\operatorname{tr}(O\sigma)$

3:Prepare $N$ random product Pauli eigenstates
$\\{\rho_{i}=\bigotimes_{j=1}^{n}\lvert s_{ij}\rangle\\!\langle
s_{ij}\rvert\\}_{i=1}^{N}$. Send them through the unknown channel
$\mathcal{E}$ and make random Pauli measurements on each qubit and obtain data
$\\{\bigotimes_{j=1}^{n}\lvert t_{ij}\rangle\\!\langle
t_{ij}\rvert\\}_{i=1}^{N}$.

4:For each n-qubit Pauli operator $Q$ with $\lvert Q\rvert\leq k$, compute
$\widehat{\lambda}_{P}(Q)$ described below for P such that |P|$\leq$ |Q|.
$\triangleright$ The computation time is $\mathcal{O}(n^{2k}\cdot N\cdot k)$

5:Construct matrix $\tilde{M}$ such that
$\tilde{M}_{PQ}=\widehat{\lambda}_{P}(Q)$. $\tilde{M}$ is an upper block
triangular matrix.

6:For $O=\sum_{P\mathrel{\mathop{\mathchar 58\relax}}|P|\leq k}\alpha_{P}P$.
Let $\overleftarrow{\alpha}=\tilde{M}^{-1}\alpha$. $\triangleright$ The
computation time is $\mathcal{O}(n^{3k})$

7:To make prediction, given $\mathcal{E}(\sigma)$, we compute
$f(\mathcal{E}(\sigma))=\sum_{P\mathrel{\mathop{\mathchar 58\relax}}|P|\leq
k}\overleftarrow{\alpha}_{P}\operatorname{tr}(P\mathcal{E}(\sigma))$.
$\triangleright$ The computation time is $\mathcal{O}(n^{k})$

We compute $\widehat{\alpha}_{P}(Q)$ as follows:

We first let

$\displaystyle\widehat{x}_{P}(Q)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\operatorname{tr}\big{(}Q\bigotimes_{j=1}^{n}(3\lvert
t_{ij}\rangle\\!\langle t_{ij}\rvert-I)\big{)}\operatorname{tr}(P\rho_{i})$
(E.4)
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\prod_{j=1}^{n}\operatorname{tr}(Q_{j}(3\lvert
t_{ij}\rangle\\!\langle t_{ij}\rvert-I)\operatorname{tr}(P_{j}\lvert
s_{ij}\rangle\\!\langle s_{ij}\rvert),$ (E.5)

then

$\widehat{\lambda}_{P}(Q)=3^{|P|}\widehat{x}_{P}(Q).$ (E.6)

Again, we have the special case of $\lambda_{P}(I)=\delta_{PI}$ from
$\mathcal{E}^{\dagger}$ being a unital map, so there is no need to perform
estimation.

###### Proposition 5

Given an unknown $n$-qubit weight contracting channel $\mathcal{E}$, a noisy
state ${\cal E}(\sigma)$, and an $n$-qubit bounded-degree $k$-local observable
O with $\left\lVert O\right\rVert_{\infty}=1$. For $\varepsilon,\delta>0$,
there exists an algorithm that uses
$N=\mathcal{O}(n^{2k}\log(n^{2k}/\delta)/\epsilon^{2})$ access to the channel
to obtain a function $f$ such that

$\left\lvert
f(\mathcal{E}(\sigma))-\operatorname{tr}(O\sigma)\right\rvert\leq\epsilon$
(E.7)

with probability at least $1-\delta$. The computation time is
$\mathcal{O}(n^{4k}\log(n^{2k}))$.

###### Proof.

The general structure of the proof is the same as before, but we have more
coefficients. For ease of comparison to previous proof, we let
$\lambda_{P}(Q)=M_{PQ}=\frac{1}{2^{n}}\operatorname{tr}(P\mathcal{N}^{\dagger}(Q))$,
$x_{P}(Q)=(1/3)^{|P|}\lambda_{P}(Q)$. $D(n,k)$ be the number of $n$-qubit
Pauli operator with weight $k$ and $T(n,k)=\sum_{l=0}^{k}D(n,l)$.

We let $\tilde{\epsilon}$ to be determined later,
$\tilde{\epsilon}^{\prime}=\tilde{\epsilon}/3^{k}$. By Hoeffding’s inequality,
we have

$\mathbb{P}(\left\lvert\widehat{x}_{P}(Q)-x_{P}(Q)\right\rvert>\tilde{\epsilon}^{\prime})\leq
2e^{-N\tilde{\epsilon}^{\prime 2}/2\times 3^{2k}}\quad\forall
P,Q,|P|\leq|Q|\leq k.$ (E.8)

By a union bound,

$\displaystyle\mathbb{P}(|\widehat{x}_{P}(Q)-x_{P}(Q)|\leq\tilde{\epsilon}^{\prime}\quad\forall
P,Q,|P|\leq|Q|\leq k)$ (E.9) $\displaystyle\geq$ $\displaystyle
1-\bigcup_{P,Q}\mathbb{P}(|\widehat{x}_{P}(Q)-x_{P}(Q)|>\tilde{\epsilon})$
(E.10) $\displaystyle\geq$ $\displaystyle
1-2\sum_{l=0}^{k}D(n,l)\sum_{m=0}^{l}D(n,m)e^{-N\tilde{\epsilon}^{\prime
2}/2\times 3^{2k}}$ (E.11) $\displaystyle=$ $\displaystyle
1-2\sum_{l=0}^{k}D(n,l)T(n,l)e^{-N\tilde{\epsilon}^{\prime 2}/2\times
3^{2k}}.$ (E.12)

Equating the last term to $1-\delta$, we get that we require

$N=\frac{2\times
3^{2k}\log(2\sum_{l}D(n,l)T(n,l)/\delta)}{\tilde{\epsilon}^{\prime 2}}.$
(E.14)

We note that $\sum_{l}D(n,l)T(n,l)<T(n,k)^{2}=\mathcal{O}(n^{2k})$, so it
holds that $N=\mathcal{O}(\log(n^{2k}/\delta)/\tilde{\epsilon}^{\prime 2})$.
By definition of $\tilde{\epsilon}^{\prime}$, this $N$ also ensures that with
probability at least $1-\delta$,

$|\widehat{\lambda}_{P}(Q)-\lambda_{P}(Q)|\leq\tilde{\epsilon}\quad\forall
P,Q,|P|<|Q|\leq k.$ (E.15)

Conditioned on this, following the same error analysis, we have that

$\displaystyle\left\lvert\operatorname{tr}(\mathcal{E}^{\dagger}(\overleftarrow{O})\sigma)-\operatorname{tr}(O\sigma)\right\rvert$
(E.16) $\displaystyle=$ $\displaystyle\sum_{P\mathrel{\mathop{\mathchar
58\relax}}\left\lvert P\right\rvert\leq
k}\left\lvert(M\overleftarrow{\alpha})_{P}-\alpha_{P}\right\rvert$ (E.17)
$\displaystyle\leq$ $\displaystyle\left\lVert
M\overleftarrow{\alpha}-\alpha\right\rVert_{1}$ (E.18) $\displaystyle=$
$\displaystyle\left\lVert M(\tilde{M})^{-1}\alpha-\alpha\right\rVert_{1}.$
(E.19)

We can write $\tilde{M}=M+\Delta$, where by construction, each element of
$\Delta$ has modulus at most $\tilde{\epsilon}$. So
$\lVert\Delta\rVert_{1}\leq T(n,k)\tilde{\epsilon}$. We also use the fact that
$(M+\Delta)^{-1}=M^{-1}-M^{-1}\Delta
M^{-1}+\mathcal{O}(\lVert\Delta\rVert^{2})$. Assuming
$\mathcal{O}(\lVert\Delta\rVert^{2})$ is negligible,

$\displaystyle\lVert M(\tilde{M})^{-1}\alpha-\alpha\rVert_{1}$ (E.20)
$\displaystyle\leq$ $\displaystyle\lVert M\rVert_{1}\lVert(M^{-1}-M^{-1}\Delta
M^{-1})\alpha-M^{-1}\alpha\rVert_{1}$ (E.21) $\displaystyle=$
$\displaystyle\lVert M\rVert_{1}\lVert-M^{-1}\Delta M^{-1}\alpha\rVert_{1}$
(E.22) $\displaystyle\leq$ $\displaystyle\lVert M\rVert_{1}\lVert
M^{-1}\rVert_{1}\lVert
M^{-1}\rVert_{1}\lVert\Delta\rVert_{1}\lVert\alpha\rVert_{1}$ (E.23)
$\displaystyle\leq$ $\displaystyle
B(M)T(n,k)\tilde{\epsilon}\bigg{(}\frac{3\lVert O\rVert}{C(k,d)}\bigg{)},$
(E.24)

where we define $B(M)=\lVert M\rVert_{1}\lVert M^{-1}\rVert^{2}_{1}$ and note
that $\lVert\alpha\rVert_{1}=\left\lVert O\right\rVert_{\mathrm{Pauli},1}$.
Again, $d$ is the degree of $O$.
By setting

$\tilde{\epsilon}=\frac{C(k,d)}{3B(M)T(n,k)}\epsilon,$ (E.25)

we have

$\lvert f(\mathcal{E}(\sigma))-\operatorname{tr}(O\sigma)\rvert\leq\epsilon.$
(E.26)

In conclusion,
$N=\mathcal{O}(\log(n^{2k}/\delta)/\tilde{\epsilon}^{2})=\mathcal{O}(n^{2k}\log(n^{2k}/\delta)/\epsilon^{2})$,
and the corresponding total computation time is
$\mathcal{O}(n^{4k}\log(n^{2k}))$.  $\sqcap$$\sqcup$

##  Appendix F Application in error mitigation for Clifford circuits

In error mitigation, the most widely used noise model is GTM, stands for gate-
independent, time-stationary Markovian noise. In the case of a Clifford
circuit made of H, S and CNOT gates, it means that every time a gate is used,
it is followed by the same noise channel. We consider the slightly stronger
case where the noise is dependent on gate, i.e. we assume that the same
channel follows the same type of gates and each noise channel is a Pauli
channel. Hence given a circuit $\mathcal{C}$ and arbitrary input state
$\sigma$, the ideal output state is $\mathcal{C}(\sigma)$ but instead, we get
the noisy state $\tilde{\mathcal{C}}(\sigma)$ where the noise is described as
above. And subsequently, when measured using an observable $O$, this would
produce an error. The goal of error mitigation is recovering the true value of
$\operatorname{tr}(O\mathcal{C}(\sigma))$ when we only have access to the
noisy states $\tilde{\mathcal{C}}(\sigma)$. We show how we can adapt our
method to perform this task when the observable is $k$-local. The main idea is
still first by accessing the gates with random Pauli eigenstates to learn the
eigenvalues of the Pauli channels, then using properties of Clifford gates
being stabilizers of the Pauli groups, we show how we still only need to scale
coefficients of the observables to make an estimation, similar to what we did
in Theorem 3. In the learning part, we once again send random Pauli
eigenstates to a single gate and then measure in random Pauli basis. The
circuit can be depicted as:

$\begin{array}[]{c}\Qcircuit@C=1em@R=1em{&\lstick{\rho_{i}}&\gate{U}&\gate{\mathcal{P}_{U}}&\qw}\end{array}$

where $U\in\\{H,S,CNOT\\}$, $\mathcal{P}_{U}$ is the corresponding Pauli noise
and $\rho_{i}$ is a Pauli eigenstate. The effect of single qubit $U$ acting on
$\rho_{i}$ simply changes it to a different Pauli eigenstate. This brings it
back to the same setting as Theorem 3, and we can estimate eigenvalues of
$\mathcal{P}_{U}$ following Algorithm 1 except in Eq. 12, we need to change it
to

$\widehat{x}_{P}=\frac{1}{N}\sum_{i=1}^{N}\operatorname{tr}(P(3\lvert
t_{i}\rangle\\!\langle
t_{i}\rvert-I))\operatorname{tr}(P(U\rho_{i}U^{\dagger})).$ (F.1)

For $\mathrm{CNOT}$ gate, the matrix of noisy $\mathrm{CNOT}$ gate is a
monomial matrix. If we label entries by Pauli operators, then $(\pi(P),P)$
entry takes the value of $\lambda_{P}$ where $\pi(P)$ is the resultant Pauli
operator by conjugating $P$ by $\mathrm{CNOT}$. In this case, by modifying
Lemma S12, we can estimate $\lambda_{P}$ as follows:

$\displaystyle\widehat{x}_{P}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\operatorname{tr}(P\bigotimes_{j=1}^{2}(3\lvert
t_{ij}\rangle\\!\langle t_{ij}\rvert-I))\operatorname{tr}(\pi(P)\rho_{i}),$
(F.2) $\displaystyle\widehat{\lambda}_{P}$
$\displaystyle=3^{|\pi(P)|}\widehat{x}_{P}.$ (F.3)

Next, given an $n$-qubit Clifford circuit $\mathcal{C}$, it can be written as

$\mathcal{C}=\mathcal{U}_{d}\circ\mathcal{U}_{d-1}\circ\cdots\circ\mathcal{U}_{1},$
(F.4)

where $\mathcal{U}_{i}(\rho)=U_{i}\rho U_{i}^{\dagger}$,
$U_{i}\in\\{H,S,CNOT\\}$. The corresponding noisy circuit
$\tilde{\mathcal{C}}$ is given by

$\tilde{\mathcal{C}}=\mathcal{P}_{\mathcal{U}_{d}}\circ\mathcal{U}_{d}\circ\cdots\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}.$
(F.5)

Furthermore, since each $U_{i}$ is a Clifford gate, it permutes the $n$-qubit
Pauli group. We denote the permutation as $\pi_{i}$, i.e.
$\pi_{i}(P)=U_{i}^{\dagger}PU_{i}$. The eigenvalue of $P$ under
$\mathcal{P}_{\mathcal{U}_{i}}$ is denoted as $\lambda_{i,P}$. We note that
after the learning part, both $\pi_{i}$ and $\lambda_{i,P}$ can be efficiently
computed classically. (since we can view each gate (and noise) as gate (and
noise) on $n$-qubits by taking tensor product with identity.)

Finally, given $k$-local observable $O=\sum\alpha_{P}P$ and copies of
$\tilde{\mathcal{C}}(\sigma)$, we would like to find estimation for
$\operatorname{tr}(O\mathcal{C}(\sigma))$. The idea would be once again find
$\overleftarrow{O}=\sum_{P}\overleftarrow{\alpha}_{P}P$ so that
$\operatorname{tr}(\overleftarrow{O}\tilde{\mathcal{C}}(\sigma))=\operatorname{tr}(O\mathcal{C}(\sigma))$.
Take $d=2$ as an example and it can be extended to arbitrary $d$ by induction.
Let

$\tilde{\mathcal{C}}=\mathcal{P}_{\mathcal{U}_{2}}\circ\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1},$
(F.6)

then $\operatorname{tr}(\overleftarrow{O}\tilde{\mathcal{C}}(\sigma))$ can be
written as

$\operatorname{tr}(\overleftarrow{O}\tilde{\mathcal{C}}(\sigma))=\sum_{P}\overleftarrow{\alpha}_{P}\operatorname{tr}(P\>\mathcal{P}_{\mathcal{U}_{2}}\circ\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}(\sigma)).$
(F.7)

Considering the trace term, we can simplify it as follows:

$\displaystyle\operatorname{tr}(P\mathcal{P}_{\mathcal{U}_{2}}\circ\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}(\sigma))$
$\displaystyle=\operatorname{tr}(\mathcal{P}_{\mathcal{U}_{2}}(P)\>\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}(\sigma))$
(F.8)
$\displaystyle=\lambda_{2,P}\operatorname{tr}(P\>\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}(\sigma))$
(F.9)
$\displaystyle=\lambda_{2,P}\operatorname{tr}(\mathcal{U}^{\dagger}_{2}(P)\>\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}(\sigma))$
(F.10)
$\displaystyle=\lambda_{2,P}\operatorname{tr}(\mathcal{P}_{\mathcal{U}_{1}}(\pi_{2}(P))\>\mathcal{U}_{1}(\sigma))$
(F.11)
$\displaystyle=\lambda_{2,P}\lambda_{1,\pi_{2}(P)}\operatorname{tr}(\pi_{2}(P)\>\mathcal{U}_{1}(\sigma))$
(F.12)
$\displaystyle=\lambda_{2,P}\lambda_{1,\pi_{2}(P)}\operatorname{tr}(\mathcal{U}^{\dagger}_{2}(P)\>\mathcal{U}_{1}(\sigma))$
(F.13)
$\displaystyle=\lambda_{2,P}\lambda_{1,\pi_{2}(P)}\operatorname{tr}(P\>\mathcal{U}_{2}\circ\mathcal{U}_{1}(\sigma))$
(F.14)
$\displaystyle=\lambda_{2,P}\lambda_{1,\pi_{2}(P)}\operatorname{tr}(P\>\mathcal{U}_{2}\circ\mathcal{U}_{1}(\sigma))$
(F.15)
$\displaystyle=\lambda_{2,P}\lambda_{1,\pi_{2}(P)}\operatorname{tr}(P\>\mathcal{C}(\sigma)).$
(F.16)

Hence by setting

$\overleftarrow{\alpha}_{P}=\frac{\alpha_{P}}{\lambda_{2,P}\lambda_{1,\pi_{2}(P)}},$
(F.17)

we have that

$\displaystyle\operatorname{tr}(\overleftarrow{O}\tilde{\mathcal{C}}(\sigma))$
$\displaystyle=\sum_{P}\overleftarrow{\alpha}_{P}\operatorname{tr}(P\mathcal{P}_{\mathcal{U}_{2}}\circ\mathcal{U}_{2}\circ\mathcal{P}_{\mathcal{U}_{1}}\circ\mathcal{U}_{1}(\sigma))$
(F.18)
$\displaystyle=\sum_{P}\alpha_{P}\operatorname{tr}(P\>\mathcal{C}(\sigma))$
(F.19) $\displaystyle=\operatorname{tr}(P\mathcal{C}(\sigma)).$ (F.20)

SPAM error. Random Pauli input states are prepared by applying a single gate
to the zero state. Suppose these gates also have Pauli noise (so there is
state preparation error), how does this affect our estimation? The effect of
Pauli noise on Pauli eigenstates is flipping it to the eigenstate with the
negative eigenvalue with probability related to the parameters of the channel.
For example, $X\ket{0}=\ket{1},\ Y\ket{0}=\ket{1},\ Z\ket{0}=\ket{0},\
I\ket{0}=\ket{0}$. So if Pauli channel has probability
$\\{p_{I},p_{X},p_{Y},p_{Z}\\}$, then it will keep $\ket{0}$ unchanged with
probability $p_{I}+p_{Z}$ and flip it to $\ket{1}$ with probability
$p_{X}+p_{Y}$. This applies to the other 5 states as well but with different
probability. Now, if we consider the case where the noise is a depolarizing
channel with probability of $p$, then the probability of flipping for every
Pauli eigenstate is the same. Let $\rho$ denotes a Pauli eigenstate,
$\rho^{\prime}$ be the state orthogonal to it, $p_{0}$ be the probability that
the depolarizing channel preserves $\rho$ and $p_{1}$ be the probability of
flipping to $\rho^{\prime}$. Now, substitute this into the left hand side of
Lemma 2, we have that

$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}\operatorname{tr}(P\mathcal{P}(p_{0}\rho+p_{1}\rho^{\prime}))\operatorname{tr}(P(p_{0}\rho+p_{1}\rho^{\prime}))$
(F.21) $\displaystyle=$
$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}p_{0}^{2}\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)+p_{0}p_{1}\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho^{\prime})+p_{0}p_{1}\operatorname{tr}(P\mathcal{P}(\rho^{\prime}))\operatorname{tr}(P\rho)+p_{1}^{2}\operatorname{tr}(P\mathcal{P}(\rho^{\prime}))\operatorname{tr}(P\rho^{\prime})$
(F.22) $\displaystyle=$
$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}p_{0}(p_{0}-p_{1})\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)-p_{1}(p_{0}-p_{1})\operatorname{tr}(P\mathcal{P}(\rho^{\prime}))\operatorname{tr}(P\rho^{\prime})$
(F.23) $\displaystyle=$
$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}p_{0}(p_{0}-p_{1})\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)-p_{1}(p_{0}-p_{1})\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)$
(F.24) $\displaystyle=$
$\displaystyle\underset{\rho\sim\mathcal{D}^{0}}{\mathbb{E}}(p_{0}-p_{1})^{2}\operatorname{tr}(P\mathcal{P}(\rho))\operatorname{tr}(P\rho)$
(F.25) $\displaystyle=$
$\displaystyle(p_{0}-p_{1})^{2}\frac{1}{3^{|P|}}\lambda_{P},$ (F.26)

where in the second line we use linearity of trace and $\mathcal{P}$, in the
third line we use
$\operatorname{tr}(P\rho)=-\operatorname{tr}(P\rho^{\prime})$, in the fourth
line we use linearity of expectation and the fact that $\rho^{\prime}$ has the
same distribution as $\rho$. Finally, in the last line we used the result of
Lemma 2. This means that when we are estimating using Eq. 12 to Eq. 13, we
would pick up an extra factor of $(p_{0}-p_{1})^{2}$ to all coefficients
(expect the one for identity where we just set it to 1). This factor can be
obtained if we perform the whole procedure with only state preparation and
measurement, and use it to estimate known quantity of traceless observable,
for example estimate the expectation value of
$\lvert+\rangle\\!\langle+\rvert$ with respect to $X$. Their ratio is our
estimation for the prefactor, and we can divide it out from our estimate to
remove the effect of state preparation error.