††thanks: Co-first authors.††thanks: Co-first authors.

# Classical Shadows for Quantum Process Tomography on Near-term Quantum
Computers

Ryan Levy  Institute for Condensed Matter Theory and IQUIST and NCSA Center
for Artificial Intelligence Innovation and Department of Physics, University
of Illinois at Urbana-Champaign, IL 61801, USA  Di Luo  Institute for
Condensed Matter Theory and IQUIST and NCSA Center for Artificial Intelligence
Innovation and Department of Physics, University of Illinois at Urbana-
Champaign, IL 61801, USA  The NSF AI Institute for Artificial Intelligence and
Fundamental Interactions  Center for Theoretical Physics, Massachusetts
Institute of Technology, Cambridge, MA 02139, USA  Bryan K. Clark  Institute
for Condensed Matter Theory and IQUIST and NCSA Center for Artificial
Intelligence Innovation and Department of Physics, University of Illinois at
Urbana-Champaign, IL 61801, USA

###### Abstract

Quantum process tomography is a powerful tool for understanding quantum
channels and characterizing properties of quantum devices. Inspired by recent
advances using classical shadows in quantum state tomography [1], we have
developed ShadowQPT, a classical shadow method for quantum process tomography.
We introduce two related formulations with and without ancilla qubits.
ShadowQPT stochastically reconstructs the Choi matrix of the device allowing
for an a-posteri classical evaluation of the device on arbitrary inputs with
respect to arbitrary outputs. Using shadows we then show how to compute
overlaps, generate all $k$-weight reduced processes, and perform
reconstruction via Hamiltonian learning. These latter two tasks are efficient
for large systems as the number of quantum measurements needed scales only
logarithmically with the number of qubits. A number of additional
approximations and improvements are developed including the use of a pair-
factorized Clifford shadow and a series of post-processing techniques which
significantly enhance the accuracy for recovering the quantum channel. We have
implemented ShadowQPT using both Pauli and Clifford measurements on the IonQ
trapped ion quantum computer for quantum processes up to $n=4$ qubits and
achieved good performance.

##  I Introduction

Quantum technologies have been developing rapidly in recent years. Quantum
devices are used for various applications, such as quantum metrology, quantum
teleportation, and quantum simulation [2, 3, 4, 5, 6]. One important task in
the development of near-term quantum devices is their characterization.

For Noisy Intermediate-Scale Quantum (NISQ) technology, a first step to
characterization is to use quantum state tomography (QST) which attempts to
characterize the output state of the quantum circuit. A next crucial step,
quantum process tomography (QPT), characterizes not just one output state but
the entire quantum dynamics of the device. Earlier attempts at QPT used the
linear inversion method [7, 8]. Later various statistical methods were
developed including maximum likelihood methods [9, 10, 11, 12, 13], Bayesian
methods [14, 15, 16], compressed sensing methods [17], tensor network methods
[18] and other optimization techniques [19, 20, 21, 22, 23, 24, 25].
Theoretically, quantum process tomography can be related to quantum state
tomography through the Jamiołkowski process-state isomorphism [26, 27]. One
recent important advancement in QST comes from classical shadow tomography
[1], which allows for the prediction of multiple observables with few quantum
measurements both theoretically and experimentally [28, 29, 30, 31, 32, 33,
34, 35, 36, 37, 38, 39, 40, 35, 41].

In this work, we propose a classical shadows algorithm for quantum process
tomography on near-term quantum computers giving both a theoretical analysis
and explicit implementations on an IonQ quantum computer. Using Jamiołkowski
process-state isomorphism and techniques in process tomography, we develop the
first classical shadow quantum process tomography (ShadowQPT). In Section II,
we prove two theorems related to the effectiveness of ShadowQPT. Theorem II.2
bounds the amount of ShadowQPT data needed to compute the overlap between any
target density matrix $\sigma$ with the output of the measured quantum process
on any input $\rho$. Theorem II.1 discusses the complexity of process matrix
tomography. In Section III, we show a corollary III.1, which describes the
sample complexity scaling of applying ShadowQPT to Hamiltonian learning, which
is logarithmic in system size, following from Theorem II.1. In Section IV, we
develop shadow algorithms with both Pauli and Clifford measurements. Both an
ancilla-based scheme as well as a two-sided scheme which applies unitaries
both before and after the channel are introduced. We proceed to show practical
improvements to these algorithms for near term devices by using two qubit
Clifford unitaries instead a global Clifford and using multiple repetitions
per circuit. Furthermore, we develop a series of post-processing techniques
such as projecting into the space of physical channels and purifying outputs
which significantly improve our results. In Section V, we implemented our
algorithms on IonQ quantum computers for both unitary and non-unitary process
tomography on $n=2,3,4$ qubits systems. We benchmark both the process matrix
construction as well as test predicting the overlap for pairs of input and
output pure states and compare to direct measurement outcomes. In Section VI,
we numerically simulate Hamiltonian learning and reconstruct a random 1D Ising
model using ShadowQPT, showing efficient scalability with system size. We
conclude in Section VII with discussion on opportunities and future
explorations of our ShadowQPT algorithms.

##  II Theoretical Analysis of ShadowQPT

In this work, we have developed shadow tomography algorithms for quantum
process tomography. The key idea is based on the recent development of shadow
tomography on quantum state [1] and the Jamiołkowski process-state isomorphism
[26]. An important result in classical shadow tomography states that [1]:
Classical shadows of size $N$ suffice to predict $M$ linear functions
$\\{tr(O_{i}\rho)\\}_{i=1,\dots,M}$ up to additive error $\epsilon$ given that
$N\geq$ (order) log($M$) $\max_{i}||O_{i}||^{2}_{shadow}/\epsilon^{2}$.

To connect quantum process tomography with the quantum state tomography, we
utilize the Jamiołkowski process-state isomorphism [26]. It provides a
positive semi-definite operator representation $\Lambda_{\mathcal{E}}$ for a
$n$ qubits process $\mathcal{E}$, which is the Choi matrix representation [27]

$\Lambda_{\mathcal{E}}=(\mathds{I}\otimes\mathcal{E})(\ket{\phi^{+}}\bra{\phi^{+}}^{\otimes
n})$ (1)

where $\ket{\phi^{+}}=\ket{00}+\ket{11}$. For an input density matrix $\rho$
to the channel $\mathcal{E}$, we have
$\mathcal{E}(\rho)=\textup{tr}[(\rho^{T}\otimes\mathds{I})\Lambda_{\mathcal{E}}]$.
In the following of the paper, we implicitly denote $\Lambda_{\mathcal{E}}$ as
$\Lambda$. Notice that $\textup{tr}(\Lambda_{\epsilon})=2^{n}$ and we further
denote the normalized process matrix $\Lambda$ with trace 1 as
$\rho_{\Lambda}=\frac{1}{2^{n}}\Lambda$. We notate a reduced $k$-qubit ($k\leq
n$) process Choi matrix as the Choi matrix representation for the quantum
channel on a particular $k$-qubit subsystem where the other $n-k$ qubits are
traced out.

Based on the classical shadow tomography property and the Choi matrix
representation, we state the following two informal versions of the theorems
for classical shadow tomography for quantum process.

###### Theorem II.1

For a $n$-qubit process Choi matrix $\rho_{\Lambda}$ and
$\epsilon,\delta\in(0,1)$, the number of random global Clifford measurements
$N$ that suffices to simultaneously predict any reduced $k$-qubit process Choi
matrix $\rho_{\Lambda^{(k)}}$ with

  * •

Frobenius norm error up to $\epsilon$ with probability $1-\delta$ is of order
$\frac{4^{n+k}}{\epsilon^{2}}\textup{log}(2(8n)^{2k}/\delta)$

Meanwhile, the number of Pauli-6 POVM measurements $N$ that suffices to
simultaneously predict any reduced $k$-qubit process Choi matrix
$\rho_{\Lambda^{(k)}}$ with

  * •

Frobenius norm error up to $\epsilon$ with probability $1-\delta$ is of order
$\frac{36^{k}}{\epsilon^{2}}\textup{log}(2(8n)^{2k}/\delta)$

  * •

Trace norm error up to $\epsilon$ with probability $1-\delta$ is of order
$\frac{144^{k}}{\epsilon^{2}}\textup{log}((24n)^{2k}/\delta)$

The Pauli-6 POVM measurement includes
$\\{\frac{1}{3}\ket{0}\bra{0},\frac{1}{3}\ket{1}\bra{1},\frac{1}{3}\ket{+}\bra{+},\frac{1}{3}\ket{-}\bra{-},\frac{1}{3}\ket{r}\bra{r},\frac{1}{3}\ket{l}\bra{l}\\}$,
where $(\ket{0},\ket{1}),(\ket{+},\ket{-}),(\ket{r},\ket{l})$ are eigenvectors
of $\sigma_{z}$, $\sigma_{x}$ and $\sigma_{y}$. We note that the Pauli-6 POVM
measurement and the random single qubit Clifford measurement usually share
similar results since the two measurements have the same shadow norm for
factorized Pauli observables [1, 36]. In this work, the term ‘random Pauli
measurement’ or ‘Pauli’ in the figures refer to Pauli-6 POVM measurement,
though one can also apply random single qubit Clifford in those contexts.

Notice that for any fixed $k$, the shadow methods allow simultaneous
prediction of all ${\binom{n}{k}}$ reduced $k$-qubit processes in time
logarithmic in $n$. This is useful for learning quantum dynamics of local
observables, and provides a foundation for us to develop an efficient k-local
Hamiltonian learning scheme (see Sec. III). For full process tomography
($k=n$), Theorem II.1 states that the quantum measurement complexity of
ShadowQPT scales exponentially which is consistent with the known lower bound
[]. We note that each measurement of ShadowQPT gives a full unbiased
(potentially noisy) stochastic representation of the entire Choi matrix; this
stands in contrast with standard MLE which requires exponential classical
post-processing to generate the Choi matrix even from small amounts of data.

Theorem II.1 focuses on predicting the complete set of reduced $k$-qubit
process Choi matrices. Instead, one can ask about computing the result of the
quantum channel run on a series of (input $\rho$, output $\sigma$) pairs -
i.e. the quantum device run on the density matrix $\rho$ and traced against
the observable $\sigma$.

###### Theorem II.2

For a $n$-qubit quantum process $\rho_{\Lambda}$ and
$\epsilon,\delta\in(0,1)$, given a set of density matrix pairs
$\\{(\rho^{in}_{1},\sigma_{1}),\dots,(\rho^{in}_{M},\sigma_{M})\\}$, the
number of measurements $N$ that suffices to predict
$\textup{tr}((\rho^{in\,T}_{i}\otimes\sigma_{i})\rho_{\Lambda})$ for any $i$
up to error $\epsilon$ with probability $1-\delta$ is of order

$\frac{\textup{log}(2M/\delta)}{\epsilon^{2}}\textup{max}_{i}||O_{i}-\frac{\textup{tr}(O_{i})}{2}\mathds{I}||^{2}_{shadow}$
(2)

where $O_{i}=\rho^{in}_{i}\otimes\sigma_{i}$, $||\cdot||_{shadow}$ is the
shadow norm (see Appendix Theorem A.1 for definition).

For random global Clifford measurement, it requires order
$\frac{\textup{log}(2M)}{\epsilon^{2}}\textup{max}_{i}\textup{tr}(O_{i}^{2})$.
In particular, if $\rho^{in}_{i}$ and $\sigma_{i}$ are all pure states, then
$\textup{tr}(O_{i}^{2})=1$. For random single qubit Clifford measurement, it
requires order
$\frac{\textup{log}(2M)}{\epsilon^{2}}\textup{max}_{i}4^{k_{i}}||O_{i}||_{\infty}^{2}$
,where $O_{i}$ acts nontrivially on $k_{i}$-qubits, $||\cdot||_{\infty}$ is
the spectral norm. If $\rho^{in}_{i}$ and $\sigma_{i}$ are all pure states,
then $||O_{i}||_{\infty}^{2}=1$.

If $\sigma_{i}$ and $\rho_{i}^{in}$ are $k$-qubit reduced density matrices
with the same support, then the overlap between $\sigma_{i}$ and
$\rho_{i}^{in}$ through the channel corresponds to
$\textup{tr}(\mathcal{E}(\rho^{in}_{i})\sigma_{i})=2^{k}\textup{tr}(\rho_{\Lambda^{(k)}}(\rho^{in\,T}_{i}\otimes\sigma_{i}))$.
Note that the Clifford ShadowQPT allows us to compute the overlap of pairs of
pure states $(\rho^{in},\sigma)$ using a number of measurements which scales
logarithmically with the number of pairs being considered. If $\rho^{in}$ and
$\sigma$ are stabilizer states, the classical resources required to compute
are also efficient as one can use the stabilizer algorithm [42].

Notice to compute $M$ pairs of
$\textup{tr}(\mathcal{E}(\rho^{in}_{i})\sigma_{i})$, ShadowQPT requires time
independent of $n$ and scales as $\textup{log}(M)$, when $\rho^{in}_{i}$ and
$\sigma_{i}$ have support over a $k$-qubit system. The detailed proofs for
Theorems II.1 and II.2 and are given in Appendix A.

##  III Hamiltonian Learning via ShadowQPT

A corollary of Theorem II.1 implies that certain applications of ShadowQPT can
also be efficient. One such application is Hamiltonian learning [43, 44],
which seeks to determine an unknown Hamiltonian given access to a time
evolution operator $U(t)$. In this context, we consider applications of
ShadowQPT to Hamiltonian learning. For a $k$-local Hamiltonian
$H=\sum_{i}c_{i}h_{i}$, $h_{i}$ is a $k$-body operator as a Pauli string and
$c_{i}$ is the coefficient to learn.

One scheme that we develop is to learn $c_{i}$ through ShadowQPT on
$e^{-iHt}$. Notice that access to $e^{-iHt}$ also gives us an ability to time
evolve to all $t^{\prime}$ which are integer multiples of $t$. Consider $t$
sufficiently small such that
$U=e^{-iHt}\approx\mathrm{I}-iHt=\mathrm{I}-it\sum_{i}c_{i}h_{i}$, then $U$
can be approximated by a sum of $k$-local operators. To characterize $U$, we
first perform ShadowQPT on $U$ and attain a representation of
$\rho_{\Lambda^{(k)}}$. To learn $c_{i}$, we choose a $k^{\prime}$-local
operator $p_{i}$ where $k^{\prime}<k$ such that $q_{i}\equiv[h_{i},p_{i}]\neq
0$, and then classically evaluate

$\displaystyle\text{tr}(\Lambda(p_{i})q_{i})$
$\displaystyle\approx\text{tr}((p_{i}-itc_{i}q_{i})q_{i});$ (3)
$\displaystyle\text{tr}(\rho_{\Lambda}(p_{i})q_{i})$ $\displaystyle\approx-
itc_{i}$ (4)

Hence we can attain $c_{i}$ from evaluating data from ShadowQPT. According to
Theorem. II.1, the sampling complexity $S$ of estimating $c_{i}$ is given by
the following.

###### Corollary III.1

Consider an unknown $k$ local Hamiltonian $H=\sum_{i}c_{i}h_{i}$ where $h_{i}$
is a $k$-body operator and $c_{i}$ are real coefficients. Given access to
$U(t)=e^{iHt}$, then ShadowQPT can estimate $c_{i}$ up to error $\epsilon$
with probability $1-\delta$ with sample complexity $S$

$S\sim\frac{36^{k}}{t^{2}\epsilon^{2}}2k\log(8n)\log(1/\delta),$ (5)

where $t$ is sufficiently small that the linear approximation error is much
smaller than $\epsilon$.

Thus for fixed $k$, ShadowQPT can efficiently predict $c_{i}$ in $O(\log(n))$
samples. Note that one can systematically reduce the (currently linear)
approximation error by a higher order Taylor expansion at the cost of
additional classical processing. We also note that our approach is related to
the latest version of Ref. [44] on real-time dynamics of Hamiltonian learning,
which is proved in an alternative way by extending the results of finite-
temperature Hamiltonian learning.

##  IV ShadowQPT Post-processing Algorithms

(a)

(b)

(c)

Figure 1: (a) Unitary channel $\mathcal{E}$, which is the GHZ process that can
create a GHZ state for $n$ qubits from $\ket{0}^{\otimes n}$. (b) Circuit for
two-sided quantum process tomography to produce a Choi matrix $\Lambda$ of a
quantum channel $\mathcal{E}$. The application of two unitary circuits,
denoted $U_{L}^{\dagger}$ and $U_{R}$ (e.g. random Pauli/Clifford) can be
applied to reconstruct the channel. (c) Circuit for ancilla-based quantum
process tomography to produce a Choi matrix $\Lambda$ of a quantum channel
$\mathcal{E}$. After preparation of a bell state input (dashed box) to
$\mathcal{E}$, a unitary rotation $U$ (e.g. random Pauli/Clifford) is applied
before measurement.

In this work, we perform classical shadow process tomography algorithms on a
unitary process as well as non-unitary reduced process. We exemplify our
approach on the unitary channel $\Lambda$ which is the GHZ process and its
reduced process. The GHZ process $\Lambda$ is shown in Fig. 1a and it
generates a $n$-qubit GHZ state [45]
$|\textrm{GHZ}_{n}\rangle=(|0\rangle^{\otimes n}+|1\rangle^{\otimes
n})/\sqrt{2}$ from $\ket{0}^{\otimes n}$. The GHZ processes are constructed
such that the circuits have a depth of $2,3,3$ for $n=2,3,4$ qubits
respectively [46].

###  IV.1 Unitary full process classical shadows

In this section, we are going to introduce two schemes for ShadowQPT, the two-
sided scheme and the ancilla-based scheme. The two sided scheme is shown in
Fig. 1b, where random unitary circuits $U^{\dagger}_{L}$ and $U_{R}$ are
applied to the left and right hand side of the channel. For the ancilla-based
scheme, we use the circuit shown in Fig. 1c. This circuit produces an $2n$
qubit output density matrix which represents the $n$ qubit normalized Choi
matrix $\rho_{\Lambda}$, for the $n$ qubit process $\mathcal{E}$. This
approach is often called ancilla-assisted quantum process tomography [47]
(AAPT). In our work, for the ancilla-based approach we perform shadow
tomography on this $2n$ qubit state. It turns out that the two-sided scheme
can be viewed as a special case of the ancilla-based scheme, where the random
unitary in the ancilla-based is factorized into a product of two unitaries
$U_{R}$ and $U_{L}$ which respectively act on the top and bottom $n$ wires
each. The details for the proof of equivalence can be found in Appendix. B.

Both schemes can realize a random Pauli measurement scheme. For the ancilla-
based scheme, the Pauli-6 POVM measurement can be realized by randomly
applying a series of basis rotation gates chosen from $G_{R}=\\{I,H,SH\\}$ as
the unitary $U$ after the channel and measuring in the computational basis,
where $H$ is the Hadamard gate, $S$ is the phase gate and $I$ is the identity.
For the two-sided scheme, one can realize the Pauli-6 POVM measurements by
randomly selecting $U_{L},U_{R}$ as a tensor product from
$G=\\{I,H,SH,X,HX,SHX\\}$ where $X$ is the Pauli X gate. In practice, this
selection from $G$ only needs to be done for $U_{L}$ and for $U_{R}$ we can
still randomly draw from $G_{R}$, just as the ancilla-based scheme, since the
application of the last $X$ is irrelevant if a measurement is immediately
performed afterwards. It is also possible to replace the Pauli-6 POVM
measurements with random single qubit Clifford gates ($k=1$). This may be
advantageous on certain quantum devices [33]. We numerically simulate their
equivalence in Appendix Fig. A7.

Additionally, both schemes can utilize random Clifford measurements, which can
have better performance or scaling compared to Pauli measurements. Since most
NISQ devices have limited gate depth, a global $n$ or $2n$ qubit random
Clifford unitary needs gate depth $O(n^{2}/\log n)$ in general, which could be
challenging to implement accurately; instead, we use a tensor product of
2-qubit Clifford unitaries ($k=2$) to realize the improved scaling of the
Clifford group while minimizing the additional gate depth to the circuit.
Random Clifford circuits are generated via the Qiskit library [48], which uses
an optimal number of Control-Not gates for 2 qubits [49].

Figure 2: Visualization of the GHZ process Choi matrix, for various numbers of
qubits (rows) constructed exactly or via classical shadow quantum process
tomography. The first column corresponds to the exact unitary process
$\Lambda$, which has no imaginary component. The next columns correspond to
real and imaginary parts of the Pauli/Clifford shadow reconstructed Choi
matrix $\Lambda^{O}$ followed by their corresponding purification. The $N=4$
visualization is zoomed into the first $60\times 60$ elements.

After we attain the random Pauli/Clifford measurements, we can construct a
Choi matrix from the classical shadows (denoted Pauli or Clifford in figures).
Precisely, after applying a Unitary $U$ and measuring in the computational
basis a bitstring $|b_{i}\rangle\in\\{0,1\\}^{\otimes n}$, we form the $i$-th
classical shadow $\hat{\Lambda}_{i}$ as

$\displaystyle\hat{\Lambda}_{i}=2^{n}\mathcal{M}^{-1}\left(U_{i}^{\dagger}|b_{i}\rangle\langle
b_{i}|U_{i}\right),$ (6)

where the inverse channel is $\mathcal{M}_{n}^{-1}(X)=(2^{n}+1)X-\mathds{I}$
for $n$-qubit Clifford circuits or
$\mathcal{M}_{n}^{-1}(X)=\otimes_{i}\mathcal{M}_{k}^{-1}(X)$ for Pauli ($k=1)$
and 2-qubit Clifford ($k=2$) circuits. These objects can be held in memory
efficiently, as Clifford circuits and bitstrings have a polynomial
representation as well as polynomial evaluation cost [42]. We average over all
classical shadows $\hat{\Lambda}_{i}$ to obtain the final shadow reconstructed
Choi matrix $\Lambda^{O}$. Note that it is suggested in Ref. [1] to utilize a
median-of-means rather than direct mean. Our data has little dependence on
this difference after projection (see Supplementary Fig. A1), which agrees
with the observations of Ref. [32].

We add an additional extension in which a given unitary is repeatedly measured
under some number of repetitions. In practice, it is often the case that
loading a different unitary on a quantum computer is significantly slower than
taking additional measurements over the same unitary. The above theorems do
not directly apply in this case, but we show via simulations (see
supplementary Fig. A4) that including additional repetitions improves the
quality of the result, up to a saturation threshold.

###  IV.2 Non-unitary reduced process classical shadows

An interesting additional extension is the ability to characterize a non-
unitary quantum process. By separating the $n$ qubit process into subsystems
of size 1 and up to size $n-1$ , we can produce a reduced process on a
subsystem of up to $n-1$ qubits. All subsets of the GHZ process are then non-
unitary. Note that a general process $\Lambda_{\mathcal{E}}$ need not be
unitary, nor have all subsystems be non-unitary. In this work, we focus on a
unitary GHZ process $\Lambda$ and simultaneously measuring all corresponding
non-unitary reduced processes on each subsystems.

In a Pauli measurement based tomography scheme, including Pauli shadow
tomography, we can directly use the operators that act over the relevant
subsystem. Here, the partial trace over the Choi matrix is equivalent to this
direct scheme, although for many expensive post-processing schemes it is far
easier to optimize in the subsystem space directly.

For a Clifford shadows scheme however, a general $n$-qubit Clifford (or $2n$)
will not be separable in the same manner as a Pauli based scheme. Despite
this, if a particular subsystem or set of subsystems is known before hand, the
Clifford unitaries can be chosen to respect separability. It has not been well
studied, however, the trade off between the benefits of using non-separable
large $n$-qubit Clifford gates or using separable ones.

###  IV.3 Post-processing of classical shadows

A physical quantum process $\Lambda$ is a completely positive trace-preserving
($\mathcal{CPTP}$) map between density matrices. For any positive semi-
definite density matrix $\rho^{in}$ with trace one, $\mathcal{E}(\rho^{in})$
should also be positive semi-definite with unit trace. Even though the shadow
reconstructed Choi matrix in Eq. 1 has the correct trace, it is not a valid
$\mathcal{CPTP}$ map in general. We further explore various post-processing
projection techniques for improving the classical shadow reconstruction in
this section.

We denote the projection of $\Lambda^{O}$ as $\Lambda^{\prime}$. To project
$\Lambda^{O}$ into the space of completely positive preserving
($\mathcal{CP}$) matrices, we use the technique of Ref. [50], which removes
negative eigenvalues and rescales the remaining non-negative eigenvalues. We
find this operation has the biggest reduction of trace distance from the
target density matrix in our data. This does not guarantee that
$\Lambda^{\prime}$ is $\mathcal{CPTP}$, but ensures that the resulting
$\Lambda^{\prime}$ is normalized and positive semi-definite.

In cases where we know the true underlying process should be unitary, we can
remove extraneous statistical noise, by purifying the shadow reconstructions
to create a unitary shadow Choi matrix. Purifying in this manner can also be
seen as an extreme $\mathcal{CP}$-projection method, in which all but the
dominant eigenvector are thrown out. We find this approach significantly
improves our result in the case where the target process is indeed unitary.

###  IV.4 Predicting Overlaps

Given a set of density matrix pairs $(\rho^{in}_{i},\sigma_{i})$ as in Theorem
II.2, we can utilize shadow reconstructed Choi matrices to obtain predictions
of the overlap $\textup{tr}[\mathcal{E}(\rho_{i}^{in})\sigma_{i}]$; we work
with the pure state $\sigma_{i}(\theta)=U(\bm{\theta})^{\dagger}|0\rangle$
where $\theta$ is a set of parameters which specify the quantum circuit which
generates $U$ and we use $|0\rangle$ as a placeholder for $|0\rangle^{\otimes
n}$.

When evolving an initial density matrix $\rho^{in}$ through the process
generated by $\Lambda^{O}$ to produce $\rho^{out}$, we additionally project a
$\mathcal{CP}$-projected Choi matrix into the trace preserving
($\mathcal{TP}$) space using the method outlined in Ref. [51], followed by
projecting $\rho^{out}$ into $\mathcal{CP}$ space. Precisely, we have
$\Lambda^{\prime}=\mathcal{TP}(\mathcal{CP}[\Lambda^{O}])$ and
$\rho^{out}=\mathcal{CP}\left[\textup{tr}((\rho^{in\,T}\otimes\mathds{I}))\Lambda^{\prime}\right]$.

We then take the pure state density matrix $\sigma_{i}$ to calculate the
overlap $\textup{tr}[\rho^{out}_{i}\sigma_{i}]=\langle
0|U(\bm{\theta})\rho^{\prime out}_{i}U(\bm{\theta})^{\dagger}|0\rangle$. For
this to be classically efficient (even without postprocessing), $\sigma_{i}$
has to be representable either as a short tensor network for Pauli or be
within the Clifford group for Clifford unitaries respectively.

When scaling to large numbers of qubits, the post-processing required to
generate $\Lambda^{\prime}$ becomes infeasible, so we introduce a more
efficient routine. To compute the overlap, we consider
$\textup{tr}[(\rho_{i}^{in\,T}\otimes\sigma_{i})\,\Lambda^{\prime O}]$ where
$\Lambda^{\prime O}$ here represents a purified $\Lambda^{O}$ without any
additional projection.

##  V Experimental Results of ShadowQPT on Quantum Hardware

We exemplify our ShadowQPT methods via quantum circuit measurements on the
IonQ trapped ion quantum device. The IonQ system consists of 11 trapped ion
qubits [52], available via Amazon Braket on Amazon Web Services (AWS). At the
time of simulation, the machine was reported111This information can be found
via the AWS status page to have a 1 qubit gate average fidelity of 0.99717, 2
qubit gate average fidelity of 0.9696, and a state preparation and measurement
(SPAM) mean of 0.9961, which agrees with the data presented in Ref. [52]. We
use 51200 shadows each for $n=2,3,4$ in the experiments with at most 1024
unitary circuits; see Appendix. C.

Included against our ShadowQPT results is a maximum-likelihood estimation
(MLE) for reconstructing the Choi matrix using our random Pauli measurements.
We use the iterative method outlined in Ref. [11]. Due to the size of the
Clifford POVM, Clifford-MLE reconstructions are done within the space of
observed measurements, as is $n=4$ Pauli data. Notice that the MLE method is
classically exponentially costly in general. To perform MLE, we begin with a
random complex matrix, taking at least 100 iteration steps such that the
iteration has converged, i.e. $\|\rho_{k}-\rho_{k-1}\|\leq 10^{-3}$ or that
the $L_{2}$-norm of the difference between steps has reached a small value. We
include purification of the resulting Choi matrix alongside our shadow
reconstructions as well.

We explore the effect of using ‘fixed’ and ‘non-fixed’ schemes by using either
a number of random Clifford unitaries or a set of random Clifford unitaries
that are separable between the first qubit and the rest of the system. For a
‘non-fixed’ unitary, a two-qubit Clifford unitary may be applied to any two
wires of the circuit. For the ‘fixed’ unitary, one Clifford is applied to
qubits 1 and $N+1$ (its corresponding ancilla), and the remaining Clifford
unitaries are randomly applied in the ‘non-fixed’ scheme. Our data has 0%,
50%, and 43.75% of the Clifford unitaries manually fixed for $n=2,3,4$
respectively. These various schemes alternatively target respectively a
situation where one might ask about any reduced density matrix a posteriori
(i.e. the non-fixed scheme) or target density matrices on a particular fixed
set of qubits (i.e the fixed scheme).

Figure 3: Left: Normalized trace distance $T(\Lambda,\Lambda^{O})$ between the
unitary Choi matrix $\Lambda$ and a Pauli/Clifford shadow reconstructed Choi
matrix $\Lambda^{O}$. Solid lines represent single repetition shadows with 512
unitaries on IonQ for Pauli/Clifford measurements and in green, simulated
$2n$-Clifford circuits; dotted lines includes all data/repetitions collected;
dot-dashed lines are purified. The corresponding purified MLE results are
shown in blue/orange stars for Pauli/Clifford measurements respectively.
Right: Trace distance for various post-processing for $n=3$. The
projection/post-processing method is shown in parenthesis above the bar.
Figure 4: Left: Simulated normalized trace distance $T(\Lambda,\Lambda^{O})$
scaling for 512 unitaries with a single repetition (top) and 50 repetitions
(bottom) between the unitary Choi matrix $\Lambda$ and a reconstruction via
Pauli/Clifford ancilla based ShadowQPT or two sided ShadowQPT. Ancilla results
are nearly identical to the two sided results with a single repetition, but
with multiple repetitions ancilla simulations (squares) have lower trace
distance than their two sided counterparts (circles). Middle: Normalized trace
distance between (IonQ measured) Pauli two-sided ShadowQPT and ancilla
ShadowQPT with 512 unitaries and 50 repetitions for a 3 qubit GHZ process.
Right: Normalized trace distance between (IonQ measured) Clifford two-sided
ShadowQPT and ancilla ShadowQPT with 512 unitaries and 50 repetitions for a 2
qubit GHZ process. The ancilla Cliffords are decomposed into $k=2$ as in Fig.
3.

###  V.1 Full Process

Using classical shadows we directly reconstruct the Choi matrix and compare it
using the normalized trace distance in Fig. 3.

$T(\Lambda_{1},\Lambda_{2})=\frac{1}{2^{n+1}}\textup{tr}\left[\sqrt{(\Lambda_{1}-\Lambda_{2})^{\dagger}(\Lambda_{1}-\Lambda_{2})}\right]$
(7)

First, to illustrate the scaling of ShadowQPT, a comparison of the Pauli and
Clifford shadow measurements using a uniform number of shadows is shown in
solid lines in Fig. 3. While each method is inherently exponential in scaling
across process size, $k=2$ Clifford measurements performs better than Pauli
measurements, where a full $k=2n$ Clifford measurement scheme should have
performed the best.

In dashed lines, we then show the results when using all of our available
measurements (i.e. multiple repetitions of the same unitary). A visualization
of each of these Choi matrices is shown in Fig. 2 (see Appendix Fig. A2 for a
3D version of the plot). We see that even in the regime where all possible
Pauli strings are measured ($n=2,3$), the Clifford circuits have a smaller
trace distance.

If we consider that our underlying process should be unitary, we can
additionally purify our noisy Choi matrix (dash-dotted lines). Purification
appears to have an enormous effect, improving the trace distance by up to a
factor of 34x. For all $n$, purified Clifford shadows have a smaller trace
distance compared to the Pauli shadows, but is followed closely by the
purified Clifford MLE reconstruction, which has a narrowly smaller distance
for $n=3,4$ (see a further comparison in Fig. A3).

(a)

(b)

Figure 5: Normalized trace distance $T(\Lambda_{B},\Lambda^{O}_{B})$ of all
subsystems of $k=1$ qubit (a) and $k=2$ qubits (b) between the unitary Choi
matrix $\Lambda_{B}$ and a Pauli/Clifford shadow reconstructed Choi matrix
$\Lambda^{O}_{B}$. Solid lines represent single repetition shadows with 512
unitaries on IonQ for Pauli/Clifford measurements and in green, simulated
$2n$-Clifford circuits; dot-dashed lines are $\mathcal{CP}$-projected after
the partial trace. The corresponding MLE results are shown in blue/orange
stars for Pauli/Clifford measurements respectively. Pauli MLE is done directly
in the reduced problem space of $k$ qubit reconstruction.

Here we have selected only the purification post-processing step, but there
are additional projections, namely $\mathcal{CP}$-projection of Ref. [50],
that one may do. Shown in the right of Fig. 3 is an example of the effects on
the trace distance each post-processing method has for $n=3$. We see a
dramatic improvement in the trace distance after purification or projection,
with Pauli shadows marginally performing better than the Clifford shadows for
this system size.

As an additional comparison we compare ShadowQPT with both an ancilla based
scheme and a two sided scheme, shown in Fig. 4. On the left, we show
simulations of both Pauli and $k=n$ Clifford measurements for a single and
multiple repetitions. The simulations use 512 unitaries and 1(50) repetitions
for single(multiple) repetitions. In the case of single repetitions, we find
nearly identical exponential scaling but with Clifford measurements with a
smaller trace distance. With the addition of multiple repetitions however, the
ancilla schemes obtain a smaller trace distance than their two sided
counterparts. As each repetition effectively changes both the left and right
unitary for the ancilla scheme but only changes the right unitary for the two
sided version, this result is unsurprising. We provide more details on the
equivalence of the schemes in Appendix B.

Then on the right of Fig. 4, we compare two examples of Pauli and Clifford
measurements and the effect of post processing methods. For the two sided
scheme, we use 512 Clifford unitaries at 50 repetitions each run on the IonQ
device, and for the ancilla scheme we randomly resample our IonQ data to
match. Note that our ancilla measurements are with randomized $k=2$ Clifford
unitaries. Pauli measurements are done with 25600 random measured Pauli
strings. We find that for both Pauli and Clifford measurements the ancilla
based scheme has a lower normalized trace distance without post-processing and
under purification, and a larger trace distance for Clifford
$\mathcal{CP}$-projection.

###  V.2 Non-unitary reduced process

We further study two examples of a non-unitary reduced process on a subset of
the qubits. In Figs. 5a and 5b are shown the average over all 1 and 2 qubit
processes. Analogous to the previous section we show a reduced dataset in
solid lines, and the fully post-processed data, here
$\mathcal{CP}$-projection, in dot-dashed lines. In general, we expect the full
$2n$-Clifford measurements, simulation shown in green, to grow exponentially
with system size. As we have fixed the size of the process, we see Pauli
measurements do not scale with respect to system size, and there is a weak
scaling for the 2-qubit Clifford measurement scheme.

For all system sizes $n$, a classical shadow routine produces comparable or
better trace distance compared with MLE, with an application of
$\mathcal{CP}$-projection after evolution. In addition, despite having limited
separability compared to the Pauli matrices, the performance of the Clifford
shadows are competitive with the Pauli shadows.

(a)

(b)

(c)

Figure 6:  (a) Trace circuit measurement of the overlap
$\textup{tr}[\Lambda^{\prime O}(\rho^{in\,T}_{i}\otimes\sigma_{i})]$ where
$\sigma=U(\theta)^{\dagger}|0\rangle\langle 0|U(\theta)$. We measure this
circuit on IonQ to compare with a prediction from ShadowQPT. (b) Comparison of
the overlap
$w_{i}^{O}=\textup{tr}[(\rho^{in\,T}_{i}\otimes\sigma_{i})\Lambda^{O}]$ for
Pauli and Clifford data on systems of size $n=2,3,4$ for pairs of density
matrices $[\rho^{in},\sigma]$ formed from the state
$[O_{\rho}^{in}\ket{0},O_{\sigma}\ket{0}]$ for operators
$[I,R_{y}(\theta)],[I,R_{x}(\theta)],$
$[\otimes_{j}R_{x}(\phi_{j}),R_{y}(\theta)],[\otimes_{j}R_{x}(\phi_{j}),R_{y}(\theta)]$
(each column respectively) over 50 different angles. For comparison we include
trace circuit measurements performed on the IonQ using 1000 repetitions per
point; error bars are generated by using 10 batches of data. (c) Overlap
predictions as in (b) but purifying $\Lambda^{O}$.

###  V.3 Predicting Overlaps

We also can compute overlaps using the shadow reconstructions formalism of
Thm. II.2. For the choice of $\sigma_{i}$, we use circuits parameterized by
$R_{x}(\theta)$ or $R_{y}(\theta)$ as input to a GHZ circuit; see Appendix for
more details on the choices of states. We compare to both the underlying
unitary process and overlaps computed on the IonQ by constructing the trace
circuit shown in Fig. 6a; each circuit is measured with 1000 repetitions. Note
that this latter approach requires additional quantum measurements for each
target overlap whereas the shadow tomography uses the same ShadowQPT data for
the overlap of any output state.

In Fig. 6b we show the overlap prediction
$w_{i}^{O}=\textup{tr}[(\rho^{in\,T}_{i}\otimes\sigma_{i})\Lambda^{O}]$ to the
shadow reconstruction data $\Lambda^{O}$ without post-processing. For $n=2,3$,
we are able to reasonably reconstruct the correct overlap, but for $n=4$ there
is not enough data to obtain the correct pure state behavior. Note that in
each case the correct qualitative behavior is evident, despite predicting much
smaller overlap values.

Then in Fig. 6c we use the the most efficient post-processing approach to
purify the Choi matrix. Purified Pauli and Clifford overlap predictions are
now nearly identical with the expected noise-free values, even for the case of
$n=4$.

(a)

(b)

Figure 7:  (a) Hamiltonian learning simulation results for a 1D transverse
field Ising model with $n$ sites and random couplings between $[-1,1]$. We
average over 10 disorder realizations and use $N=100000$ random Pauli
measurements with no additional post processing. The average error is given by
average absolute error $\langle|\tilde{c}_{i}-c_{i}|\rangle$ to the original
Hamiltonian coupling $c_{i}$. (b) Dependence on number of Pauli measurements
$N$ vs. average error of Hamiltonian learning both for fixed $t$ and the
optimal $t$ (shown in purple). Notice at fixed $t$, as the error decreases it
approaches the minimum error at that $t$, shown by the vertical dot-dashed
line, coming from the systematic error caused by the linear approximation to
the time evolution operator.

##  VI Numerical Simulation of ShadowQPT Hamiltonian Learning

Here we present simulation results with Hamiltonian learning. We study a 1D
transverse field Ising model $H=\sum_{i}J_{i}X_{i}X_{i+1}+h_{i}Z_{i}$ with
uniform random couplings $J_{i},h_{i}\in[-1,1)$ over 10 disorder realizations.
When applying ShadowQPT, we apply the unitary $e^{-itH}$ and sample $N$ random
Pauli measurements with no additional post-processing. For the $J_{i}$ terms
we use $p_{i}=Z_{i}$, $q_{i}=[h_{i},p_{i}]=-Y_{i}X_{i+1}$ and for the $h_{i}$
terms $p_{i}=X_{i}$, $q_{i}=[h_{i},p_{i}]=Y_{i}$.

Using the methods described in Section III, we plot the behavior of the
average error in Fig. 7. In Figure 7a, we show the average absolute error
$\langle|\tilde{c}_{i}-c_{i}|\rangle$ between the ShadowQPT learned couplings
$\tilde{c_{i}}$ and the original couplings $c_{i}$ ($c_{i}\equiv\\{J,h\\}$)
with a simulation of $N=100000$. Given a fixed $t$, the average error scales
nearly independently of system size $n$ (and should be bounded by $O(\log(n))$
scaling at large $n$). For small $t$, while the first order expansion of the
time evolution operator is a good approximation, one needs many measurements
to determine the couplings beyond statistical noise as the channel is very
close to the identity. For large $t$, the higher order terms generated by the
exponential become important and the learned couplings $\tilde{c}_{i}\approx
c_{i}^{renorm}(t)=i\mathrm{tr}(\rho_{\Lambda_{t}}(p_{i})q_{i})/t\not\approx
c_{i}$. At intermediate $t$, we find a favorable regime where there are enough
measurements to learn the random couplings to an average error of $10^{-1}$.
In Fig. 7b (see Appendix for further details) we more carefully analyze the
errors in this process, particularly as we change the number of measurements
and time. There are two sources of error in Hamiltonian learning using
ShadowQPT. A systematic error occurs due to the linear approximation of the
time evolution operator and is given by
$\epsilon_{s}(t)\equiv\langle|c_{i}-c_{i}^{renorm}(t)|\rangle$ and scales as
$O(t^{2})$. Notice that this error does not depend on the number of
measurements. There is also a statistical error coming from the stochastic
nature of the ShadowQPT process which, scales as $\epsilon\propto 1/\sqrt{N}$
(see $t=0.1$ in Fig. 7b) and empirically $\epsilon\propto 1/t$ (see Appendix
Fig. A10). For a fixed t, we can therefore make the error better by increasing
the number of measurements until we reach an error of $\epsilon_{s}(t)$. The
optimal error, found when the systematic error is approximately the same as
the statistical error, is shown in purple diamonds in Fig. 7b and scales as
$O(1/\epsilon^{3})$. Despite the increase in scaling, the number of
measurements required are overall fewer than from the $O(1/\epsilon^{2})$
results of using a fixed time. As we also note earlier in Sec. III, the
systematic error can be further reduced by higher Taylor expansion and
classical processing to achieve better overall scaling. Our study provides a
prescription for choosing the number of measurements needed for a given value
of $\epsilon$ with weak dependence of $n$.

##  VII Conclusion

In this work, we have developed classical shadows algorithms for quantum
process tomography. We discuss the power of classical ShadowQPT in Theorem.
II.1, II.2. Interestingly, ShadowQPT can be applied to low-weight inputs and
outputs at a cost in quantum measurements which scales only logarithmically
with $N$. To realize the ShadowQPT on near term quantum devices, we study both
the effects of random Pauli measurements and Clifford measurements. In
addition, we explore different post-processing techniques. We further
benchmark our methods and achieve good performance for unitary process, non-
unitary reduced process, and overlap estimation on IonQ quantum hardware up to
$n=4$ qubits. We find that our post-processing techniques, particularly
purification, result in the ability to simultaneously compute very accurate
overlaps for any state. Our method not only provides a theoretical foundation,
but also effectively applies to NISQ quantum device. Additionally, we show the
equivalence between the ancilla based ShadowQPT and a two-sided scheme, and
find both via simulations and measurements that the ancilla scheme under
multiple repetitions achieves better performance.

We additionally develop Hamiltonian learning using ShadowQPT, and discuss its
scaling in Corollary III.1. Then using numerical simulations we show that
there is a logarithmic dependence on system size, as expected, and using
intermediate time propagators can be advantageous for minimizing the total
number of samples needed for a given error threshold.

For future exploration, one can consider to integrate our methods with
recently developed Hamiltonian driven shadow methods [40, 35], which could
allow for more flexible choices for unitaries as well as applications to
different experimental platforms. We anticipate that ShadowQPT will be an
important tool for future exploration and validation of quantum devices.

###### Acknowledgements.

We acknowledge support from the NSF Quantum Leap Challenge Institute for
Hybrid Quantum Architectures and Networks (NSF Award 2016136). This work is
supported by the National Science Foundation under Cooperative Agreement
PHY-2019786 (The NSF AI Institute for Artificial Intelligence and Fundamental
Interactions, http://iaifi.org/). A portion of this work was completed during
the 2021 QHack hackathon. We gratefully acknowledge funding for quantum
computing machine-time from AWS and Xanadu. R.L. and D.L. thank our two
hackathon team members E. Chertkov and A. Khan, and acknowledge helpful
discussions from Hongye Hu, Nicholas Rubin, Juan Carrasquilla and Yizhuang
You, as well as insightful comments on the shadow schemes from Daniel K. Mark,
Minh Tran, Tianci Zhou, and Soonwon Choi. Note: During the final preparation
of this work, several relevant papers were posted on the arXiv. Both Ref. [39]
and Ref. [40] also consider a decomposition of full Clifford unitaries into
several $k$-qubit unitaries. Ref. [53] has also independently and concurrently
studied the question of using classical shadows for quantum channels.

## References

  * 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).
  * Bouwmeester  _et al._ [1997] D. Bouwmeester, J.-W. Pan, K. Mattle, M. Eibl, H. Weinfurter, and A. Zeilinger, Experimental quantum teleportation, Nature 390, 575 (1997).
  * Giovannetti  _et al._ [2011] V. Giovannetti, S. Lloyd, and L. Maccone, Advances in quantum metrology, Nature Photonics 5, 222–229 (2011).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Zhong  _et al._ [2020] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Quantum computational advantage using photons, Science 370, 1460 (2020).
  * Ebadi  _et al._ [2021] S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, and et al., Quantum phases of matter on a 256-atom programmable quantum simulator, Nature 595, 227–232 (2021).
  * 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).
  * Poyatos  _et al._ [1997] J. F. Poyatos, J. I. Cirac, and P. Zoller, Complete characterization of a quantum process: The two-bit quantum gate, Phys. Rev. Lett. 78, 390 (1997).
  * James  _et al._ [2001] D. F. V. James, P. G. Kwiat, W. J. Munro, and A. G. White, Measurement of qubits, Phys. Rev. A 64, 052312 (2001).
  * Bouchard  _et al._ [2019] F. Bouchard, F. Hufnagel, D. Koutný, A. Abbas, A. Sit, K. Heshami, R. Fickler, and E. Karimi, Quantum process tomography of a high-dimensional quantum communication channel, Quantum 3, 138 (2019).
  * Lvovsky [2004] A. I. Lvovsky, Iterative maximum-likelihood reconstruction in quantum homodyne tomography, Journal of Optics B: Quantum and Semiclassical Optics 6, S556–S559 (2004).
  * Blume-Kohout [2010a] R. Blume-Kohout, Hedged maximum likelihood quantum state estimation, Phys. Rev. Lett. 105, 200504 (2010a).
  * Smolin  _et al._ [2012a] J. A. Smolin, J. M. Gambetta, and G. Smith, Efficient method for computing the maximum-likelihood quantum state from measurements with additive gaussian noise, Phys. Rev. Lett. 108, 070502 (2012a).
  * Granade  _et al._ [2017] C. Granade, C. Ferrie, and S. T. Flammia, Practical adaptive quantum tomography, New Journal of Physics 19, 113017 (2017).
  * Christandl  _et al._ [2009] M. Christandl, R. König, and R. Renner, Postselection technique for quantum channels with applications to quantum cryptography, Phys. Rev. Lett. 102, 020504 (2009).
  * Blume-Kohout [2010b] R. Blume-Kohout, Optimal, reliable estimation of quantum states, New Journal of Physics 12, 043034 (2010b).
  * Rodionov  _et al._ [2014] A. V. Rodionov, A. Veitia, R. Barends, J. Kelly, D. Sank, J. Wenner, J. M. Martinis, R. L. Kosut, and A. N. Korotkov, Compressed sensing quantum process tomography for superconducting quantum gates, Physical Review B 90, 144504 (2014).
  * Torlai  _et al._ [2023] G. Torlai, C. J. Wood, A. Acharya, G. Carleo, J. Carrasquilla, and L. Aolita, Quantum process tomography with unsupervised learning and tensor networks, Nature Communications 14, 10.1038/s41467-023-38332-9 (2023).
  * Knee  _et al._ [2018a] G. C. Knee, E. Bolduc, J. Leach, and E. M. Gauger, Quantum process tomography via completely positive and trace-preserving projection, Physical Review A 98, 062336 (2018a).
  * Surawy-Stepney  _et al._ [2022] T. Surawy-Stepney, J. Kahn, R. Kueng, and M. Guta, Projected least-squares quantum process tomography, Quantum 6, 844 (2022).
  * Zhang  _et al._ [2021a] G. Zhang, M. Huo, and Y. Li, Quantum operation of fermionic systems and process tomography using majorana fermion gates (2021a), arXiv:2102.00620 [quant-ph] .
  * White  _et al._ [2022] G. White, F. Pollock, L. Hollenberg, K. Modi, and C. Hill, Non-markovian quantum process tomography, PRX Quantum 3, 020344 (2022).
  * Govia  _et al._ [2020] L. C. G. Govia, G. J. Ribeill, D. Ristè, M. Ware, and H. Krovi, Bootstrapping quantum process tomography via a perturbative ansatz, Nature Communications 11, 1084 (2020).
  * Xue  _et al._ [2022] S. Xue, Y. Liu, Y. Wang, P. Zhu, C. Guo, and J. Wu, Variational quantum process tomography of unitaries, Phys. Rev. A 105, 032427 (2022), arXiv:2108.02351 [quant-ph] .
  * Onorati  _et al._ [2021] E. Onorati, T. Kohler, and T. Cubitt, Fitting quantum noise models to tomography data (2021), arXiv:2103.17243 [quant-ph] .
  * Jamiołkowski [1972] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Reports on Mathematical Physics 3, 275 (1972).
  * Choi [1975] M.-D. Choi, Completely positive linear maps on complex matrices, Linear Algebra and its Applications 10, 285 (1975).
  * Hadfield [2021] C. Hadfield, Adaptive pauli shadows for energy estimation (2021), arXiv:2105.12207 [quant-ph] .
  * Chen  _et al._ [2021] S. Chen, W. Yu, P. Zeng, and S. T. Flammia, Robust shadow estimation, PRX Quantum 2, 030348 (2021), arXiv:2011.09636 [quant-ph] .
  * Koh and Grewal [2022] D. E. Koh and S. Grewal, Classical Shadows With Noise, Quantum 6, 776 (2022).
  * Hillmich  _et al._ [2021] S. Hillmich, C. Hadfield, R. Raymond, A. Mezzacapo, and R. Wille, Decision diagrams for quantum measurements with shallow circuits, in  _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_ (2021) pp. 24–34, arXiv:2105.06932 [quant-ph] .
  * Struchalin  _et al._ [2021] G. Struchalin, Y. A. Zagorovskii, E. Kovlakov, S. Straupe, and S. Kulik, Experimental estimation of quantum state properties from classical shadows, PRX Quantum 2, 010307 (2021).
  * Zhang  _et al._ [2021b] T. Zhang, J. Sun, X.-X. Fang, X.-M. Zhang, X. Yuan, and H. Lu, Experimental quantum state measurement with classical shadows, Phys. Rev. Lett. 127, 200501 (2021b).
  * Zhao  _et al._ [2021] A. Zhao, N. C. Rubin, and A. Miyake, Fermionic partial tomography via classical shadows, Phys. Rev. Lett. 127, 110504 (2021).
  * Hu and You [2022] H.-Y. Hu and Y.-Z. You, Hamiltonian-driven shadow tomography of quantum states, Phys. Rev. Res. 4, 013054 (2022), arXiv:2102.10132 [quant-ph] .
  * Acharya  _et al._ [2021] A. Acharya, S. Saha, and A. M. Sengupta, Shadow tomography based on informationally complete positive operator-valued measure, Phys. Rev. A 104, 052418 (2021), arXiv:2105.05992 [quant-ph] .
  * Rouzé and França [2021] C. Rouzé and D. S. França, Learning quantum many-body systems from a few copies (2021), arXiv:2107.03333 [quant-ph] .
  * 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 [quant-ph] .
  * Huggins  _et al._ [2022] W. J. Huggins, B. A. O’Gorman, N. C. Rubin, D. R. Reichman, R. Babbush, and J. Lee, Unbiasing fermionic quantum monte carlo with a quantum computer, Nature 603, 416 (2022), arXiv:2106.16235 [quant-ph] .
  * Hu  _et al._ [2023] H.-Y. Hu, S. Choi, and Y.-Z. You, Classical shadow tomography with locally scrambled quantum dynamics, Phys. Rev. Res. 5, 023027 (2023), arXiv:2107.04817 [quant-ph] .
  * Huang  _et al._ [2022] H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, Provably efficient machine learning for quantum many-body problems, Science 377, 10.1126/science.abk3333 (2022).
  * Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A 70, 052328 (2004).
  * Li  _et al._ [2020] Z. Li, L. Zou, and T. H. Hsieh, Hamiltonian tomography via quantum quench, Physical Review Letters 124, 160502 (2020).
  * Haah  _et al._ [2021] J. Haah, R. Kothari, and E. Tang, Optimal learning of quantum hamiltonians from high-temperature gibbs states, arXiv preprint arXiv:2108.04842 (2021).
  * Greenberger  _et al._ [1989] D. M. Greenberger, M. A. Horne, and A. Zeilinger, Going beyond bell’s theorem, in  _Bell’s theorem, quantum theory and conceptions of the universe_ (Springer, 1989) pp. 69–72.
  * Cruz  _et al._ [2018] D. Cruz, R. Fournier, F. Gremion, A. Jeannerot, K. Komagata, T. Tosic, J. Thiesbrummel, C. L. Chan, N. Macris, M. A. Dupertuis, and C. Javerzac-Galy, Efficient quantum algorithms for GHZ and W states, and implementation on the IBM quantum computer, arXiv , 1 (2018), arXiv:1807.05572 .
  * 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, Phys. Rev. Lett. 90, 193601 (2003).
  * ANIS  _et al._ [2021] M. S. ANIS _et al._ , Qiskit: An open-source framework for quantum computing (2021).
  * Bravyi and Maslov [2021] S. Bravyi and D. Maslov, Hadamard-free circuits expose the structure of the clifford group, IEEE Transactions on Information Theory 67, 4546 (2021).
  * Smolin  _et al._ [2012b] J. A. Smolin, J. M. Gambetta, and G. Smith, Efficient method for computing the maximum-likelihood quantum state from measurements with additive gaussian noise, Phys. Rev. Lett. 108, 070502 (2012b).
  * Knee  _et al._ [2018b] G. C. Knee, E. Bolduc, J. Leach, and E. M. Gauger, Quantum process tomography via completely positive and trace-preserving projection, Physical Review A 98, 062336 (2018b).
  * Wright  _et al._ [2019] K. Wright, K. Beck, S. Debnath, J. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. Pisenti, M. Chmielewski, C. Collins, _et al._ , Benchmarking an 11-qubit quantum computer, Nature communications 10, 1 (2019).
  * Kunjummen  _et al._ [2023] J. Kunjummen, M. C. Tran, D. Carney, and J. M. Taylor, Shadow process tomography of quantum channels, Phys. Rev. A 107, 042403 (2023).
  * Cincio  _et al._ [2018] L. Cincio, Y. Subaşi, A. T. Sornborger, and P. J. Coles, Learning the quantum algorithm for state overlap, New Journal of Physics 20, 1 (2018), arXiv:1803.04114 .

Appendix

Classical Shadows of Quantum Process Tomography on Near-term Quantum Computers

##  Appendix A Proofs for Shadow Process Tomography

We first review the formal version of a classical shadow quantum state
tomography theorem in Ref. [1].

###### Theorem A.1

Fix a measurement primitive $U$, a collection $\\{O_{i}\\}_{i=1,\dots,M}$ of
$2^{n}\times 2^{n}$ Hermitian matrices and accuracy parameters
$\epsilon,\delta\in(0,1)$. Set $K=2\textup{log}(2M/\delta)$ and
$N=\frac{34}{\epsilon^{2}}\textup{max}_{i}||O_{i}-\frac{\textup{tr}(O_{i})}{2}\mathds{I}||^{2}_{shadow}$,
where $||.||_{shadow}$ is the shadow norm defined with the inverse channel
$\mathcal{M}^{-1}$ induced by the measurement primitive as follows,

$||O||_{shadow}=max_{\sigma}(\mathbb{E}_{U\sim\mathcal{U}}\sum_{b\in\\{0,1\\}^{n}}\bra{b}U\sigma
U^{\dagger}\ket{b}\bra{b}U\mathcal{M}^{-1}(O)U^{\dagger}\ket{b}^{2})^{1/2}$
(8)

Then, a collection of $NK$ independent classical shadows allow for accurately
predicting all features via median of means prediction $\hat{o_{i}}$:

$|\hat{o_{i}}(N,K)-\textup{tr}(O_{i}\rho)|\leq\epsilon$ (9)

for all $1\leq i\leq M$ with probability at least $1-\delta$.

In particular, for random global Clifford measurement primitive,
$||O-\frac{\textup{tr}(O)}{2}\mathds{I}||^{2}_{shadow}\leq
3\textup{tr}(O^{2})$. For random single qubit Clifford measurement primitive,
$||O-\frac{\textup{tr}(O)}{2}\mathds{I}||^{2}_{shadow}\leq
4^{k}||O||_{\infty}^{2}$ where $k$ is the locality of the operator $O$ and
$||.||_{\infty}$ is the spectral norm. Furthermore, if $O$ is a single
$k$-local Pauli observable,
$||O-\frac{\textup{tr}(O)}{2}\mathds{I}||^{2}_{shadow}\leq 3^{k}$.

We now combine the above theorem and the Jamiołkowski process-state
isomorphism [26] to reach the following two theorems for shadow quantum
process tomography.

###### Theorem A.2

For a $n$-qubit quantum process $\rho_{\Lambda}$ and
$\epsilon,\delta\in(0,1)$, given a set of density matrice pairs
$\\{(\rho^{in}_{1},\sigma_{1}),\dots,(\rho^{in}_{M},\sigma_{M})\\}$, the
number of measurements $N$ that suffices to predict the overlaps
$\textup{tr}(\rho_{\Lambda}(\rho^{in\,T}_{i}\otimes\sigma_{i}))$ for any $i$
up to error $\epsilon$ with probability $1-\delta$ is

$N=\frac{68}{\epsilon^{2}}\textup{log}(2M/\delta)\textup{max}_{i}||O_{i}-\frac{\textup{tr}(O_{i})}{2}\mathds{I}||^{2}_{shadow}$
(10)

where $O_{i}=\rho^{in\,T}_{i}\otimes\sigma_{i}$. For random global Clifford
measurement,
$N=\frac{68}{\epsilon^{2}}\textup{log}(2M/\delta)\textup{max}_{i}\textup{tr}(O_{i}^{2})$.
If $\rho^{in}_{i}$ and $\sigma_{i}$ are all pure states, then
$\textup{tr}(O_{i}^{2})=1$. For random single qubit Clifford measurement,
$N=\frac{68}{\epsilon^{2}}\textup{log}(2M/\delta)\textup{max}_{i}4^{k_{i}}||O_{i}||_{\infty}^{2}$,
where $O_{i}$ acts nontrivially on $k_{i}$-qubits. If $\rho^{in}_{i}$ and
$\sigma_{i}$ are all pure states, then $||O_{i}||_{\infty}^{2}=1$.

  * Proof

Under the the Jamiołkowski process-state isomorphism [26],

$\textup{tr}(\rho_{\Lambda}(\rho^{in\,T}_{i}\otimes\sigma_{i}))=\textup{tr}(\rho_{\Lambda}(O_{i})),$
(11)

The result follows directly from applying Theorem. A.1 with $M$ measurements.
For random global Clifford measurement and pure states $\rho^{in}_{i}$ and
$\sigma_{i}$, $O_{i}=\rho^{in\,T}_{i}\otimes\sigma_{i}$ is also a pure state
of rank 1 so that $\textup{tr}(O_{i}^{2})=1$. It implies that
$||O_{i}-\frac{\textup{tr}(O_{i})}{2}\mathds{I}||^{2}_{shadow}\leq
3\textup{tr}(O_{i}^{2})=3$. For random single qubit Clifford measurement and
pure states $\rho^{in}_{i}$ and $\sigma_{i}$,
$O_{i}=\rho^{in\,T}_{i}\otimes\sigma_{i}$ is also a pure state so that
$||O_{i}||_{\infty}^{2}=1$.

###### Theorem A.3

For a $n$-qubit process Choi matrix $\rho$ and $\epsilon,\delta\in(0,1)$, the
following statements hold:

(i) the number of measurements $N$ that suffices to simultaneously predict any
reduced $k$-qubit process Choi matrix $\rho_{k}$ up to error $\epsilon$ in the
Frobenius norm and probability $1-\delta$ is

$N=\frac{68}{\epsilon^{2}}4^{k}\textup{log}(2(8n)^{2k}/\delta)max_{i}||O_{i}^{(2k)}-\frac{\textup{tr}(O_{i}^{(2k)})}{2}\mathds{I}||_{shadow}^{2}$
(12)

where $O_{i}^{(2k)}$ is any $2k$-qubit Pauli observable.

In particular, for random global Clifford measurement,
$N=\frac{204}{\epsilon^{2}}4^{n+k}\textup{log}(2(8n)^{2k}/\delta)$ and for
Pauli-6 POVM measurement,
$N=\frac{68}{\epsilon^{2}}36^{k}\textup{log}(2(8n)^{2k}/\delta)max_{i}||O_{i}^{(2k)}||_{\infty}^{2}$.

(ii) the number of Pauli-6 POVM measurements $N$ that suffices to
simultaneously predict any reduced $k$-qubit process Choi matrix $\rho_{k}$ up
to error $\epsilon$ in the trace norm and probability $1-\delta$ is

$N=\frac{8}{3}\frac{144^{k}}{\epsilon^{2}}\textup{log}((24n)^{2k}/\delta)$
(13)

  * Proof

(i) According to the Jamiołkowski process-state isomorphism [26], a quantum
process on a $n$-qubit system can be represented by a density matrix $\rho$ on
a $2n$-qubit system. Any reduced $k$-qubit process matrix $\rho_{k}$ could be
expressed as

$\rho_{k}=\frac{1}{4^{k}}\sum^{16^{k}}\alpha_{i}O_{i}^{(2k)}$ (14)

where $\alpha_{i}=\textup{tr}(\rho_{k}O_{i}^{(2k)})=\textup{tr}(\rho
O_{i}^{(2k)}\otimes\mathds{I}_{2n-2k})$.

Denote the estimated $k$-qubit reduced density matrix from the shadow
tomography as $\hat{\rho}_{k}$ and
$\hat{\rho}_{k}=\frac{1}{4^{k}}\sum^{16^{k}}\hat{\alpha}_{i}O_{i}^{(k)}$,
where $\hat{\alpha}_{i}$ is the shadow estimation of observable $O_{i}^{2k}$.
It follows that

$\langle\hat{\rho}_{k}-\rho_{k},\hat{\rho}_{k}-\rho_{k}\rangle_{F}=\langle\frac{1}{4^{k}}\sum^{16^{k}}(\hat{\alpha}_{j}-\alpha)O_{j}^{(2k)},\frac{1}{4^{k}}\sum^{16^{k}}(\hat{\alpha}_{i}-\alpha)O_{i}^{(2k)}\rangle_{F}=\frac{1}{4^{k}}\sum^{16^{k}}(\hat{\alpha}_{i}-\alpha_{i})^{2}$
(15)

where $\langle\cdot,\cdot\rangle_{F}$ is the Frobenius inner product.

According to Theorem. A.1, with $N$ given in Eq. 12, we have

$|\hat{\alpha}_{i}-\alpha_{i}|=|\hat{\alpha}_{i}-\textup{tr}(\rho
O_{i}^{(2k)}\otimes\mathds{I}_{2n-2k})|\leq\frac{\epsilon}{2^{k}}\quad\forall\quad
i$ (16)

It implies that
$\langle\hat{\rho}_{k}-\rho_{k},\hat{\rho}_{k}-\rho_{k}\rangle_{F}\leq\frac{16^{k}}{4^{k}}\frac{\epsilon^{2}}{4^{k}}=\epsilon^{2}$,
so that $||\hat{\rho}_{k}-\rho_{k}||_{F}\leq\epsilon$ where $||\cdot||_{F}$ is
the Frobenius norm. For random global Clifford measurement, the result follows
from $||O-\frac{\textup{tr}(O)}{2}\mathds{I}||^{2}_{shadow}\leq
3\textup{tr}(O^{2})=3\times 4^{n}$ for $O=O_{i}^{(2k)}$. For Pauli-6 POVM
measurement, the result follows from
$||O-\frac{\textup{tr}(O)}{2}\mathds{I}||^{2}_{shadow}\leq 9^{k}$ for
$O=O_{i}^{(2k)}$ [36].

(ii) For a given $\epsilon,\delta\in(0,1)$, the Pauli-6 POVM measurement of
size $N=\frac{8}{3\epsilon^{2}}12^{r}(\textup{log}(p^{r}12^{r}/\delta))$ is
sufficient to predict all reduced density matrix on subsystem size $r\leq p$
on a $p$-qubit system with trace norm error $\epsilon$ and probability at
least $1-\delta$ according to Lemma 1 in Ref. [41]. With the Jamiołkowski
process-state isomorphism [26], a $k$-qubit process Choi matrix is equivalent
to a $2k$-qubit density matrix on a $2n$-qubit system. The result follows from
choosing $r=2k$ and $p=2n$, which implies that with probability $1-\delta$,
$N=\frac{8}{3}\frac{144^{k}}{\epsilon^{2}}\textup{log}((24n)^{2k}/\delta)$
number of Pauli-6 POVM measurements is sufficient to simultaneously predict
any reduced $k$-qubit process Choi matrix $\rho_{k}$ up to error $\epsilon$ in
the trace norm, i.e. any estimator $\hat{\rho}_{k}$ from the shadow
measurement is closer to the exact $\rho_{k}$ by
$||\hat{\rho}_{k}-\rho_{k}||_{1}<\epsilon$.

##  Appendix B Equivalence of Two-sided Scheme with the Top-bottom Factorized
Ancilla-based Scheme

We would like to show that the two-sided scheme is equivalent to the top-
bottom factorized ancilla-based scheme. Precisely, consider a top-bottom
factorized ancilla-based scheme with unitaries $\\{U_{j}\\}$ acting on the top
half and unitaries $\\{U_{i}\\}$ acting on the bottom half, where $U_{j}$,
$U_{i}$ are sampled uniformly from a set $G$. Up to permutation, the
reconstruction formula for the Choi matrix is the following:

$\rho_{\Lambda}^{a}=\mathbb{E}_{U_{j}\sim G}\mathbb{E}_{U_{i}\sim
G}\mathbb{E}_{b_{j},b_{i}\sim P(i,j)}\
\mathcal{M}^{-1}_{n}(U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i})\otimes\mathcal{M}^{-1}_{n}(U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j})$
(17)

where $b_{j},b_{i}$ are measurement outcome with respect to $U_{j},U_{i}$ in
the computational basis,
$P(i,j)=\textup{tr}(\rho_{\Lambda}(U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i}\otimes
U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j}))$. $\mathcal{M}^{-1}_{n}$ is the
inverse channel defined by $\mathcal{M}^{-1}_{n}(X)=(2^{n}+1)X-\mathds{I}$ for
$n$-qubit Clifford unitaries or
$\mathcal{M}^{-1}_{n}(X)=\otimes_{i}M_{k}^{-1}(X)$ for Pauli ($k=1$) for
smaller $k$ qubit Cliffords.

Meanwhile, consider a two-sided scheme where the input state is $\ket{0}$,
followed by $\\{U_{i}^{\dagger}\\}$, process channel $\mathcal{E}$,
$\\{U_{j}\\}$ and finally measurement in the computational basis shown in Fig.
1b. $U_{j}$, $U_{i}$ are also sampled uniformly from group $G$. The
reconstruction formula for the Choi matrix is given as follows:

$\rho_{\Lambda}^{t}=\mathbb{E}_{U_{j}\sim G}\mathbb{E}_{U_{i}\sim
G}\mathbb{E}_{b_{j}\sim P(j|[U_{i}^{\dagger}\ket{0}])}\
\mathcal{M}^{-1}_{n}((U_{i}^{\dagger}\ket{0}\bra{0}U_{i})^{T})\otimes\mathcal{M}^{-1}_{n}(U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j})$
(18)

where
$P(j|[U_{i}^{\dagger}\ket{0}])=\textup{tr}(\mathcal{E}(U_{i}^{\dagger}\ket{0}\bra{0}U_{i})U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j})=2^{n}\textup{tr}(\rho_{\Lambda}((U_{i}^{\dagger}\ket{0}\bra{0}U_{i})^{T}\otimes
U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j}))$. The last line comes from the
Choi matrix identification. For any set $G$ that is right invariant with
respect to any Pauli-X matrix such that $GX=G$, we have

$\rho_{\Lambda}^{t}=\mathbb{E}_{U_{j}\sim G}\mathbb{E}_{U_{i}\sim
G}\mathbb{E}_{b_{i}\sim\frac{1}{2^{n}}}\mathbb{E}_{b_{j}\sim
P(j|[U_{i}^{\dagger}\ket{b_{i}}])}\,\mathcal{M}^{-1}_{n}((U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i})^{T})\otimes\mathcal{M}^{-1}_{n}(U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j})$
(19)

This is true because $\ket{b_{i}}=\otimes^{\\{\ell\\}}X\ket{0}$ where
$\\{\ell\\}$ are the locations where the measurement outcome is 1 and hence
for any $U_{i}^{\dagger}\ket{0}$, there exists $U^{\prime}_{i}$ from $G$ such
that $U^{\prime}_{i}\ket{b_{i}}=U_{i}\ket{0}$. Notice that this condition is
true for random global Clifford measurement, random single qubit Clifford
measurement, as well as Pauli-6 measurement. It follows that,

$\rho_{\Lambda}^{t}=\mathbb{E}_{U_{j}\sim G}\mathbb{E}_{U_{i}\sim
G}\mathbb{E}_{b_{j},b_{i}\sim P^{t}(i,j)}\
\mathcal{M}^{-1}_{n}((U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i})^{T})\otimes\mathcal{M}^{-1}_{n}(U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j})$
(20)

where
$P^{t}(i,j)=\frac{1}{2^{n}}P(j|[U_{i}^{\dagger}\ket{b_{i}}])=\textup{tr}(\rho_{\Lambda}((U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i})^{T}\otimes
U_{j}^{\dagger}\ket{b_{j}}\bra{b_{j}}U_{j}))$. For Pauli-6 POVM, we have
$(U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i})^{T}=U_{i}^{\dagger}\ket{b_{i}}\bra{b_{i}}U_{i}$,
which implies $\rho^{t}_{\Lambda}=\rho^{a}_{\Lambda}$. For Clifford group $G$
and any fixed $\ket{b}$, we have
$\\{U_{i}^{\dagger}\ket{b}\bra{b}U_{i}|U_{i}\in
G\\}=\\{(U_{i}^{\dagger}\ket{b}\bra{b}U_{i})^{T}|U_{i}\in G\\}$, which also
implies $\rho^{t}_{\Lambda}=\rho^{a}_{\Lambda}$.

We remark that the above argument holds for a single repetition measurement.
For multiple repetition measurement with respect to one $U_{i}$, the
equivalence breaks because multiple $\ket{b_{i}}$ are generated with respect
to one $U_{i}$ in the ancilla-based scheme while the two-sided scheme always
has input $\ket{0}$ fixed for one $U_{i}$.

##  Appendix C Details on Shadow Measurements

We present the number of random unitary circuits used for both Clifford and
Pauli measurements. For those with unitary entries with *, all possible
unitaries have been used.

Qubits | Type | Unitaries | Repetitions/Unitary (Total)
---|---|---|---
2 | Pauli | 81* |  $\approx 632$ (51200)
Clifford | 1024 | 50 (51200)
3 | Pauli | 729* |  $\approx 70$ (51200)
Clifford | 1024 | 50 (51200)
4 | Pauli | 1024 | 50 (51200)
Clifford | 1024 | 50 (51200)

##  Appendix D Comparison between Median-of-Means and Mean

Figure A1: Normalized trace distance $T(\Lambda,\Lambda^{O})$ between the
unitary Choi matrix $\Lambda$ and a Pauli/Clifford shadow reconstructed Choi
matrix $\Lambda^{O}$ for the $n=3$ GHZ process. The construction is either via
mean, median of means via randomizing and batching individual shadows (with
many derived from the same unitary), or median of means for each unique
unitary (which has 50/$\approx$70 repetitions each). We include the effects of
$\mathcal{CP}$ projection on the resulting Choi matrices for comparison.

In Ref. [1], the authors suggest a median-of-means procedure for the classical
shadows, or more precisely taking the median of $K$ averaged shadows. Then in
Ref. [32] they show that most of their results are unaffected by using the
direct mean over a median-of-means.

To understand the role of the procedure in ShadowQPT, we first distinguish
between two median-of-means procedures. The first a median on the ‘shadow’
level: take each classical shadow, many of which are from the same unitary,
and perform the median-of-means procedure using this data set. An alternative
procedure, is to first average the repetitions corresponding to each unitary,
then obtain the median by using sets of $K$ averaged unitaries.

In Fig. A1 is shown the results of using the mean and the two median-of-mean
procedures for $n=3$ data, with a batch size of $K=23$. While using a median-
of-means at the shadow level does show a slight improvement for both Pauli and
Clifford measurements without projection, after projection we find that there
is little difference between the mean and median-of-means results. Given the
weak dependence on the differences after post-processing and the potential
introduction of a tunable variable ($K$), we chose to utilize the mean for our
computing results of the classical shadows.

##  Appendix E 3D Choi matrix plots

(a)

(b)

Figure A2: (a) Choi matrix visualization using Pauli (left two) and Clifford
(right two) shadows, separated into real and imaginary components. (b)
Purification of matrices in (a).

In Fig. A2 we present a 3D representation of $n=2,3$ in Fig. 2. The axes are
shown enumerated in binary for the Choi matrices $4^{n}$ index values.

##  Appendix F Post-processing dependence

Figure A3: Normalized trace distance $T(\Lambda,\Lambda^{O})$ between the
unitary Choi matrix $\Lambda$ and a Pauli/Clifford shadow reconstructed Choi
matrix $\Lambda^{O}$. Included are two projections of the $\Lambda^{O}$ into
the space of positive semidefinite (PSD) matrices, the iterative maximum-
likelihood estimator (MLE) method of Ref. [11] and the eigenvalue rescaling
method of Ref. [50], as well as the corresponding purification.

(a)  (b)

Figure A4: Left (a) Normalized trace distance $T(\Lambda,\Lambda^{O})$ between
the unitary Choi matrix $\Lambda$ and various simulated reconstruction
methods. Simulated data includes a prefix of “Sim”. The vertical line
represents saturation of all Pauli strings. Right (b) Normalized trace
distance $T(\Lambda,\Lambda^{O})$ between the unitary Choi matrix $\Lambda$
and a Clifford shadow reconstruction from resampled data (Markers) on top of
simulated data (dotted lines with shading). A star marks the full IonQ
dataset; errorbars represent an average of 5 resampling trials. Resampled IonQ
data consists of equal fixed and random Clifford orderings.

(a)  (b)

Figure A5:  Normalized trace distance $T(\Lambda_{B},\Lambda^{O}_{B})$ of the
subsystem of the first qubit ($k=1$) (a) and (b) the remaining $n-1$ qubits
($k=n-1$) between the unitary Choi matrix $\Lambda_{B}$ and a Pauli/Clifford
shadow reconstructed Choi matrix $\Lambda^{O}_{B}$.

In order to show the dependence on post-processing method, Fig. A3 shows the
normalized trace distance between MLE reconstruction,
$\mathcal{CP}$-projection, and purification. Overall the results are roughly
consistent across system size $n$, in that purified shadows are competitive
with purification of (Clifford) MLE results. Just considering $\mathcal{CP}$
projection and standard MLE, Pauli measurements have the minimal trace
distance.

##  Appendix G Repetition dependence on trace distance

Next we compare the dependence on the trace distance with the number of
unitaries and classical shadows for $n=3$ in Fig. A4.

Second, we resample the Clifford measurements from the IonQ alongside
simulated data, computing the normalized trace distance in Fig. A4b. We find
that the measured data tracks the simulation very closely for a number of
chosen unitary Clifford measurements. Although we predict performance could be
increased by increasing the number of repetitions/circuit (i.e. we had not
reached instability in trace distance seen in the low unitary counts, the blue
and orange lines of Fig. A4b), the number of individual circuits and
repetitions/circuit chosen appears to be reasonable in the study of our
method. Although there is an instability in the regime where the number of
repetitions is greater than the number of unitary, the trace distance remains
improved compared to a single measurement.

##  Appendix H Distance using the Frobenius norm

We provide additional plots of Figs. 3,4, 5a, and 5b using a Frobenius norm
distance shown in Fig. A6 and A7. We find nearly the same qualitative behavior
for both distance measures. This is unsurprising as, at least for the Pauli
case, there is similar scaling bounds of $\log(n)$ for fixed $k$ (see Theorem.
II.1).

(a)

(b)  (c)

Figure A6: (a) Left: Normalized Frobenius norm
$\|\Lambda-\Lambda^{O}\|_{F}/2^{n}$ between the unitary Choi matrix $\Lambda$
and a Pauli/Clifford shadow reconstructed Choi matrix $\Lambda^{O}$. Solid
lines represent single repetition shadows with 512 unitaries on IonQ for
Pauli/Clifford measurements and in green, simulated $2n$-Clifford circuits;
dotted lines includes all data/repetitions collected; dot-dashed lines are
purified. The corresponding purified MLE results are shown in blue/orange
stars for Pauli/Clifford measurements respectively. Right: Frobenius norm
distance for various post-processing for $n=3$. The projection/post-processing
method is shown in parenthesis above the bar. (b) $k=1$ qubit and (c) $k=2$
qubits reduced process reconstruction between the unitary Choi matrix
$\Lambda_{B}$ and a Pauli/Clifford shadow reconstructed Choi matrix
$\Lambda^{O}_{B}$ using the Frobenius norm. Solid lines represent single
repetition shadows with 512 unitaries (including simulated $2n$-Clifford
circuits), dotted lines includes all data/repetitions, and dot-dashed lines
are $\mathcal{CP}$-projected after the partial trace. The corresponding MLE
results are shown in blue/orange stars for Pauli/Clifford measurements
respectively. Pauli MLE is done directly in the reduced problem space of $k$
qubit reconstruction.  Figure A7: Left: Simulated Frobenius norm
$\|\Lambda-\Lambda^{O}\|_{F}/2^{n}$ scaling for 512 unitaries with a single
repetition (top) and 50 repetitions (bottom) between the unitary Choi matrix
$\Lambda$ and a reconstruction via Pauli or Clifford ancilla based ShadowQPT
or two sided ShadowQPT. ‘Sim-Clifford/Pauli’ corresponds to single qubit
Clifford ($k=1$) for $U_{L}$ and Pauli measurements on the right, which is
nearly identical to Pauli two sided measurements. Ancilla results are nearly
identical to the two sided results with a single repetition, but with multiple
repetitions ancilla simulations (squares) have lower trace distance than their
two sided counterparts (circles). Middle: Normalized trace distance between
(measured) Pauli two-sided ShadowQPT and ancilla ShadowQPT with 512 unitaries
and 50 repetitions for a 3 qubit GHZ process. Right: Normalized Forbenius norm
between (measured) Clifford two-sided ShadowQPT and ancilla ShadowQPT with 512
unitaries and 50 repetitions for a 2 qubit GHZ process. The ancilla Cliffords
are decomposed into $k=2$ as in Fig. A6 .

##  Appendix I Details on Overlap Estimation

To illustrate Theorem. II.2, we compute
$\textup{tr}[\Lambda^{\prime}(\rho^{in\,T}\otimes\sigma(\theta))]$ for several
sets of $\rho$ and $\sigma(\theta)$. The input to the channel, $\rho^{in}$,
can be represented by an initial state of which has three categories:
$\ket{0}^{\otimes n}$, $\ket{+i}^{\otimes n}$, and
$\otimes_{j}R_{x}(\phi_{j})\ket{0}^{\otimes n}$ states222where
$R_{x}(\phi_{j})$ acts on the $j$-th qubit and
$\phi_{j}=\\{0.1717,0.1234,0.9876,0.888\\}$. The first two states are already
measured within the Choi matrix, and are effectively measuring the
reconstruction of the channel process. After running the circuit in Fig. 6a,
we measure $\ket{0}^{\otimes n}$ or $P(\ket{0}^{\otimes n})$ to obtain the
value of the overlap. We only display $\ket{0}^{\otimes n}$ and
$\otimes_{j}R_{x}(\phi_{j})\ket{0}^{\otimes n}$ states in the main work.

We compute the average overlap error in Fig. A8 compared to the trace circuit
measurements performed on the IonQ device. We use 51 pairs for each
$\rho^{in}$ for the shadow reconstructed data iterating uniformly
$\theta\in[0,2\pi]$ and $\approx 5-8$ pairs for each $\rho^{in}$. Error bars
represent the standard error over the overlap dataset. We see that our
reconstructed shadow data has similar trends to the trace circuit measurement,
with a significant range of values. With purification, we can significantly
decrease the error to the noiseless case even compared to the trace circuit,
particularly in the $n=4$ case.

Figure A8:  Average overlap error
$\langle\Delta\rangle=\langle|w_{i}^{O}-w_{i}|\rangle_{i}$ for Pauli
reconstruction (left), Clifford (middle) and Simulated Clifford data (right)
for systems of size $n=2,3,4$. We average over 3 different $\rho^{in}$ and 4
different $\sigma$ each with 51 different angles. For comparison we include
trace circuit measurements (Tr circuit) performed on the IonQ using the data
shown in Fig. 6b.

Purity of the channel and GHZ state can also be calculated. The Bell-Basis
Algorithm (BBA) swap test [54] provides an algorithm to determine the overlap
between two general quantum states. We compute the overlap of two GHZ states
$\textup{tr}[\rho_{GHZ_{n}}^{2}]$ where
$\rho_{GHZ_{n}}=\mathcal{E}(\ket{0}\bra{0}^{\otimes n})$ using the BBA
algorithm, alongside computing the shadow reconstructed
$\textup{tr}[\Lambda^{2}]/4^{n}$ in Fig. A9. When measuring the purity, we
find a much higher value than our shadow reconstructions. A noiseless quantum
computer should produce unit purity for the full GHZ process, these large
measurements further motivate our choice to use purification as a post-
processing technique. Note that purity has a strong dependence on post-
processing techniques.

Figure A9: Normalized Purity measurement $\textup{tr}[\Lambda^{2}]/4^{n}$ of
the $\mathcal{CP}$-projected Pauli/Clifford measured Choi matrices as well as
the MLE reconstructions shown as a star. We use the BBA algorithm run directly
on the IonQ with 1000 repetitions shown in diamonds to compute
$\textup{tr}[\rho_{GHZ_{n}}^{2}]$ where
$\rho_{GHZ_{n}}=\mathcal{E}(\ket{0}\bra{0}^{\otimes n})$; error bars are done
by batching the measurements into 10 sets.

##  Appendix J Hamiltonian Learning Optimal Error Fits

In Fig. A10 we show for a fixed number of Pauli measurements (shadows) $N$ the
average error vs $t$ of the unitary operator $\exp(-iHt)$. These points have
been simulated and averaged over the same 10 trials as in Fig. 7. For a given
value of $t$, because of the linear approximation to $\exp(-iHt)$, the error
of which is shown in blue, grows as $O(t^{2})$ and is the minimum achievable
error for a given $t$. ShadowQPT reconstructed couplings $\tilde{c}_{i}$ are
inherently measuring $c_{i}^{renorm}$ however, with an error as $O(1/t)$ shown
in green. Thus as these two approach, the true absolute error between
$\tilde{c}_{i}$ and $c_{i}$ is shown in orange, which mostly follows either
the linear approximation error or renormalized error except near their
crossing. The minimum error can then be found for a given $t$, shown in a
dashed grey line. We additionally fit this line for $N=1000,1000000$ which are
not shown.

Figure A10: a) Hamiltonian learning simulation results for a 1D transverse
field Ising model with $n$ sites and random couplings between $[-1,1]$. We
average over 10 disorder realizations and use $N=100,10000,$ and $100000$
random Pauli measurements respectively with no additional post processing. The
average error is given by average absolute error $\langle|b_{i}-c_{i}|\rangle$
to the original Hamiltonian coupling $c_{i}$, where $b_{i}$ is either
$c^{renorm}_{i}$ the renormalized couplings, $\tilde{c}_{i}$ the ShadowQPT
reconstructed couplings, or $\tilde{c}_{i}+c_{i}-c^{renorm}_{i}$ or the error
between ShadowQPT and the renormalized couplings. A dashed line shows the
optimal error where the linear approximation error is approximately the same
as the renormalized error.