revtex4-2Repair the float package lemmatheorem lemma

# Shadow estimation of gate-set properties from random sequences

J. Helsen∗ QuSoft, Centrum Wiskunde & Informatica (CWI), Amsterdam, The
Netherlands  corresponding authors<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Korteweg-de Vries Institute for Mathematics,
University of Amsterdam, Amsterdam, The Netherlands  M. Ioannou  Dahlem Center
for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
J. Kitzinger  Dahlem Center for Complex Quantum Systems, Freie Universität
Berlin, 14195 Berlin, Germany  Humboldt-Universität zu Berlin, Institut für
Physik, 12489 Berlin, Germany  E. Onorati  Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, 14195 Berlin, Germany  University College
London, Department of Computer Science, London, United Kingdom  Technische
Universität München, Fakultät für Mathematik, München, Germany  A. H. Werner
Department of Mathematical Sciences, University of Copenhagen, 2100 København,
Denmark  NBIA, Niels Bohr Institute, University of Copenhagen, Blegdamsvej 17,
2100 København, Denmark  J. Eisert  Dahlem Center for Complex Quantum Systems,
Freie Universität Berlin, 14195 Berlin, Germany  Helmholtz-Zentrum Berlin für
Materialien und Energie, 14109 Berlin, Germany  Fraunhofer Heinrich Hertz
Institute, 10587 Berlin, Germany  I. Roth∗ Quantum Research Center, Technology
Innovation Institute (TII), Abu Dhabi

With quantum computing devices increasing in scale and complexity, there is a
growing need for tools that obtain precise diagnostic information about
quantum operations. However, current quantum devices are only capable of short
unstructured gate sequences followed by native measurements. We accept this
limitation and turn it into a new paradigm for characterizing quantum gate-
sets. A single experiment—random sequence estimation—solves a wealth of
estimation problems, with all complexity moved to classical post-processing.
We derive robust channel variants of shadow estimation with close-to-optimal
performance guarantees and use these as a primitive for partial, compressive
and full process tomography as well as the learning of Pauli noise. We discuss
applications to the quantum gate engineering cycle, and propose novel methods
for the optimization of quantum gates and diagnosing cross-talk.

##  I Introduction

Recent years have seen the rapid development of quantum computing devices to
unprecedented system sizes. These devices are still noisy and of limited
computational power, but go substantially beyond what was conceivable not very
long ago. In order to scale even further to larger and more accurate devices,
it is key to develop tools for efficiently characterizing quantum operations
[1, 2] at scale. Besides providing crucial actionable advice for the
practitioner, the characterization of quantum operations is also important for
developing an in-depth theoretical understanding of the actual capabilities of
quantum devices and for providing a fair comparison between different types of
devices, and with classical computing power on the same tasks [3, 4, 5]. Over
the years, many protocols for characterizing quantum operations have been
developed [6, 7, 8].

That said, while a wealth of theoretical ideas for benchmarking, verification
and tomographic recovery have been suggested, only a few of them are relevant
in practice. With present quantum devices, only relatively short gate
sequences can be implemented on qubit arrays, followed by a native measurement
at the end of the circuit that typically suffers from sizeable read-out noise.
With these limitations the most prominent protocols for characterizing digital
quantum gates fall into the class of randomized benchmarking (RB) [9, 10, 11,
12, 13, 14] (including newer protocols such as _averaged circuit eigenvalue
sampling_ [15]). RB implements suitable sequences of random quantum gates and
extracts a measure of quality as parameters describing the decay rate of the
measured signal with the sequence length. This has the advantage of yielding
_state preparation and measurement_ (SPAM) error robust error metrics. The
experimental sequences of most RB protocols are carefully designed (such as
compiled circuit inverses) to efficiently extract specific information from a
gate-set. Prominent exceptions are ‘filtered’ RB protocols such as _linear
cross-entropy benchmarking_ (XEB) [3] that directly work with random sequences
of i.i.d. drawn gates and, e.g., omit an inversion gate.

Figure 1:  The gate-set shadow estimation protocol proceeds in two stages:
First, for a fixed inital state $\rho$ and varying sequence lengths $m$ a
total of $S$ random sequences of quantum gates of length $m$ are
experimentally implemented and each followed by a measurement. We call the
observed tuples of measurement outcome and gate sequence
$(x^{j},g_{1}^{j},\dots,g_{m}^{j})$, $j=1,\dots,S$ the gate-set shadow. The
second classical post-processing stage consists itself of three steps: (i) A
given sequence correlation function is calculated for every entry of the gate
set shadow. For the UIRS protocol a sequence correlation function $f_{A}$ is
specified in terms of a probe super-operator $A$ and an irreducible
representation $\sigma$. (ii) We calculate the the sequence average
$\hat{k}_{f_{A}}(m)$ as the mean or median-of-means of the result of step (i)
over sequences of the same length $m$. (iii) Sequence averages for different
lengths $m$ are used as data points to fit a theoretical model (eq. 5) in
order to extract the generalized gate-set fidelity with respect to the super-
operator $A$ and the irreducible representation $\sigma$, denoted here by
$p(A)$. One of the most important features of this approach is that we can use
the same experimental data to accurately estimate _exponentially many_
generalized fidelities $p(A_{1}),p(A_{2}),\dots,p(A_{S})$ by evaluating
different sequence correlation functions on the same gate-set shadow. In this
way, we can self-consistently and robustly estimate many different properties
of the gate-set noise from a minimal amount of data obtained in a simple
experiment. Section II.8 to II.10 explain and derive guarantees of how the
gate-set shadow estimation protocol can be used as a primitive in other more
detailed characterization task, such as compressive channel or marginal
tomography, potentially allowing one to run the whole engineering cycle on
essentially the same type of data.

In this work, we take these observations seriously, and revert the mindset
that is commonly applied when devising new schemes for benchmarking and
characterization. We ask the question: If all we can feasibly do is
implementing unstructured random sequences followed by a native measurement,
what can we learn? At first sight this endeavour is not promising. Compared to
‘traditional’ RB and tomographic protocols we are giving up on central
ingredients. Thinking about how much information we measure in an unstructured
way, we run into the problem that typically, the probabilities of individual
measurement results are exponentially small in the number of qubits. This is
orthogonal to the careful design of efficient characterization schemes in
prior work, and does not obviously yield sample efficient estimation schemes
at all.

Our change of paradigm is analogous to the mindset of classical shadows [16,
17]. Classical state shadows allow for the sample-efficient estimation of
(exponentially) many different functions of a quantum state from the same data
by only modifying the classical post-processing. Perhaps the central surprise
value of the result of ref. [16] is rigorously guaranteeing that the fidelity
of a quantum state with respect to any pure state can be estimated from the
same experiment, using only constantly many state copies with sufficiently
randomized basis measurements. This is in stark contrast to schemes like
direct fidelity estimation [18] that given a priori knowledge of the target
state carefully optimize the measurements that are performed.

In this work, we define the observed measurement outcomes of random sequences
of quantum gates as the _classical shadow of a gate-set_ and study the sample
efficiency of SPAM-robust estimators for different linear functionals of a
gate-set from the same data. Borrowing the median-of-mean estimators used on
classical state shadows, we show that the sampling complexity of the
estimation (the number of single-shot quantum measurements) can be controlled
by a dynamic shadow norm with exponential confidence. We prove bounds on this
dynamic shadow norm—a considerably more involved object than its state
counterpart—for prominent gate-sets such as the multi-qubit Clifford group and
the local Clifford group. We find that by a suitable post-processing we can
estimate the relative average gate fidelities of the noise of a Clifford gate-
set with respect to an exponentially large number of unitary channels from
polynomially many measurement samples from the same uniformly random
experiment. More generally, we show that the dynamical shadow norm can be
controlled in terms of the unitarity of the estimated linear quantity. Using
local gate-sets, we show that one can selectively gain information about
channel marginals capturing correlations in their noisy implementation. We
promote this primitive further to design a highly scalable and efficient
tomography scheme for cross-talk effects. Furthermore, we exemplify how gate-
set shadows can be used to construct SPAM-robust objective functions for
learning noise models and for robust low-rank quantum process tomography.

The important feature of all these schemes is that we only adapt the classical
post-processing to the task at hand, not the quantum experiment. A single type
of data, namely samples from simple local measurements on uniformly random
gate sequences, is sufficient to perform a large class of diagnostic tasks of
benchmarking, verification and tomographic recovery. The mindset can be
captured as “Measure first, ask later!”. Going beyond uniformly independently
random sequences, we can generalize our approach to provide an optimal scheme
to learn Pauli noise, emulating the protocol of ref. [19] with a simpler
experimental prescription and theoretical analysis.

Related work. We build on a body of literature on randomized schemes for
quantum device characterization [8]. The potential of analyzing the output
statistics of gate-set sequences to self-consistently extract essentially all
information of a gate-set (as well as the initial state and the measurement)
has been realized by gate-set tomography [20, 21, 22, 23, 24, 25] with recent
variants only requiring random sequences (gate-set shadows) [26, 27]. In
contrast to this self-consistent tomographic estimation of all gates in the
gate-set, we here target individual linear quantities of the gate-set’s
average noise or an interleaved quantum process. Our cross-talk tomography
protocol follows the spirit of simultaneous RB [28], but goes significantly
beyond simultaneous RB in providing higher-order correlation measures and
tomographic information of noise-channel marginals, efficiently from the data
of a single randomized experiment. In ref. [29], it has been observed that
variants of interleaved multi-qubit Clifford randomized benchmarking
experiments [30] have access to relative average gate fidelities from which
unital quantum channels can be reconstructed. The protocol of ref. [29]
performs a different experiment for each fidelity yielding a sub-optimal
overall sample complexity for tomography or low-rank tomography [31, 32].
Gate-set shadow estimation solves both these short-comings.

##  II Results

We begin with explaining the general protocol. In the subsequent sections, we
then provide theoretical performance guarantees for specific gate-sets and
explain how the protocol can be used as a robust estimation primitive in more
complex characterization tasks, such as channel tomography. The gate-set
shadow estimation protocol consists of two separate stages: an experiment,
where measurement results from random circuits of different lengths are
recorded, and a classical post-processing step, where different parameters can
be estimated from the measured data. Figure 1 summarizes the complete
protocol.

###  II.1 Protocol: Experiment

We aim at characterizing the accuracy of the implementation of a target gate-
set $\mathbb{G}$. The experimental primitive is the realization of random
(gate) sequences of length $m$: After preparing an initial $\rho$ (e.g.,
$\ket{0}\\!\\!\bra{0}$) a sequence of gates $\vec{g}\in\mathbb{G}^{\times m}$
is drawn at random according to a distribution $\mu_{m}:\mathbb{G}^{\times
m}\to[0,1]$ and applied to $\rho$. This is then followed by a measurement
specified by a POVM $\\{E_{x}\\}_{x}$ with measurement outcomes in
$\mathcal{X}$ (e.g., a computational basis measurement). If $x\in\mathcal{X}$
is observed, the result of the primitive is a tuple
$(x,\vec{g})\in\mathcal{X}\times\mathbb{G}^{\times m}$.

Repeating the primitive multiple times yields a series of tuples
$\\{(x_{i},\vec{g}_{i})\\}_{i=1}^{S}$ which we refer to as a _(self-
consistent) gate-set shadow_. (Note that ref. [16] actually calls the dual
frame elements indexed by the observed output statistics of an informationally
complete POVM a state’s _shadow_. In contrast, we here directly refer to the
sampled sequence and observed measurement outcomes as a shadow.)

A complete experimental protocol further involves measuring such shadows for a
set of different sequence lengths $m$. In order to simplify the theoretical
analysis, we focus on the paradigmatic case of $\mathbb{G}$ being a finite
subgroup of $\operatorname{SU}(2^{N})$ (such as the Clifford group) and
distributions on the sequences arising from the uniform measure over these
subgroups.

The simplest example of protocols in this context are _uniform independent
random sequence (or _UIRS_) protocols_ where the gates in the sequences are
drawn from the gate-set uniformly and independently at random. This can be
seen as the paradigmatic case, although we will go beyond this later in this
work. We make shadow gate-set estimation through the UIRS protocol explicit
for several important gate-sets: namely the multi-qubit Clifford group
$\mathbb{C}_{n}$ and the independent single -qubit Clifford group
$\mathbb{C}_{1}^{\times n}$ (which we will call the _local Clifford group_).

###  II.2 Protocol: Classical post-processing

Given a gate-set shadow $\\{(x_{i},\vec{g}_{i})\\}_{i=1}^{S}$, we define an
empirical estimator in terms of a _sequence correlation function_
$f(x,\vec{g}):{\mathcal{X}}\times\mathbb{G}^{\times m}\to\mathbb{C}$. For
every such sequence correlation function, in the post-processing, we (i)
evaluate $f$ for all entries of the gate-set shadows and (ii) calculate the
empirical mean or median-of-mean estimator

$\hat{k}_{f}(m)\coloneqq\operatorname{(median-of-)means}\
\\{f(x_{i},\vec{g}_{i})\\}_{i=1}^{S}$ (1)

of the result. After repeating step (i) and (ii) for different sequence
lengths $m$, we fit in step (iii) a theoretical model $k_{f}$ to the estimates
of the _sequence means_ $\hat{k}_{f}(m)$. After giving this overview of the
post-processing protocol, let us take a closer look at the steps and explain
their roles in the UIRS protocol:

Regarding step (i): Generally speaking, sequence correlation functions can be
seen as the gate-set analog of an observable in shadow estimation. They allow
us to compute properties of noisy gate-sets (for example the average fidelity
of an average group element) from experimentally observed gate-set shadows. We
emphasize that, like state shadow estimation, the data collection step of
random sequence estimation is independent of the gate-set properties one
wishes to estimate, with this estimation step happening entirely in classical
post-processing. Importantly, this enables one to estimate many different
correlation functions from the same experimental data.

We here introduce a particular class of sequence correlation functions for
UIRS protocols: Consider an irreducible representation $\sigma$ of
$\mathbb{G}$ with representation space $V_{\sigma}$. For the multi-qubit
Clifford group, e.g., its adjoint action on traceless Hermitian matrices is of
main interest. We further specify a sequence correlation function in terms of
a matrix $A$, POVM $\\{E_{x}\\}_{x\in\mathcal{X}}$ and state $\rho$, on
$V_{\sigma}$ as

$f_{A}(x,\vec{g})=\alpha\,\operatorname{Tr}\left[E_{x}\sigma(g_{m})\prod_{i=1}^{m-1}A\sigma(g_{i})(\rho)\right]\,,$
(2)

with a suitable normalization factor $\alpha$. (Note that for $m=1$, and
perfectly implemented gates, this expression reproduces the classical state
shadows of ref. [16]. Generally, restricted to multiplicity-free, irreducible
representations, the dual frame construction of ref. [16] simply amounts to
introducing a proper normalization factor, justifying our choice of calling
the observed statistics directly the shadow.)

We refer to $A$ as a _probe (super-)operator_ as it specifies the linear
quantity of the gate-set that is encoded into the decay parameter of the
empirical estimator. Note that the expression eq. 2 is closely related to the
Born probability of measuring $x$ after applying the sequence $\vec{g}$ to
$\rho$. The main differences are that we restrict the computation to the
subspace $V_{\sigma}$ and interleave the sequence with the probe operator $A$.
Similar to classical shadows, the computation of $f_{A}$ requires, in general,
the same resources as simulating the physical evolution within a subspace. In
many situations, however, further structure renders this task efficient. This
is in particular the case when both the gate-set and the probe-operators are
chosen to be multi-qubit Clifford operations.

Note that all previously existing RB protocols only use functions that at most
depend on the product of the operations in the sequence,
$f_{\mathbb{I}}(x,\vec{g})=h(x,g_{1}g_{2}\cdots g_{m})$. In filtered RB
protocols, such as linear cross-entropy benchmarking [3], character
benchmarking [33] and Pauli-noise tomography [19], the inversion gate can in
this way be omitted and accounted for in post-processing. Using a non-trivial
$A$ goes significantly beyond existing schemes and allows one to even
efficiently ‘interleave in-post’ the same data with different probe operators.

Regarding step (ii): By taking an empirical average over the gate-set, we
expect $\hat{k}_{f}(m)$ to be a degree $m$ polynomial in the ‘average noise’
of the gate-set. One insight of standard Clifford randomized benchmarking is
that by taking an uniform average over a sufficiently large group the ‘average
noise’ is probed isotropically, effectively projecting it onto a depolarizing
channel. Similarly, UIRS will probe the ‘average noise’ of the gate-set, but
by choosing different probe operators $A$, we can alter the operator on which
the noise is projected, revealing more information. Performing the post-
processing separately for different irreducible representations $\sigma$,
ensures that the gate-set always averages sufficiently over the subspace under
consideration. We will make this intuition precise in the subsequent section.

Regarding step (iii): The projection onto isotropic noise (on each
representation space) also dramatically ‘simplifies’ the functional form of
the expected value of the sequence averages $\hat{k}_{f}(m)$. Recall that for
standard Clifford RB, one effectively witnesses a single exponential decay.
Below we show that analogously for UIRS protocols, the theoretical fitting
model is a single (matrix) exponential decay encoding linear quantities of the
noise in its decay parameter. The decay parameter(s) can be extracted using
least-square fitting algorithms (or tone-finding algorithms such as ESPRIT).
See ref. [14, Sec. VII] for a discussion on different post-processing
techniques. In the end, the UIRS gate-set shadow estimation protocol returns
the decay parameters for different choices of probe operators $A$ and
representations $\sigma$.

###  II.3 Fitting model

In order to keep the theoretical derivation and statements concise and
straight-forward to interpret, we adhere to some standard assumptions that are
commonly used in the analysis of RB protocols. First, we assume that the
quantum channel that implements a sequence $\vec{g}$ on the quantum device,
can be written as $\mathcal{E}(\vec{g})=\prod_{i=1}^{m}\phi(g_{i})$ with a map
$\phi:\mathbb{G}\to\mathcal{S}_{n}$. Here, $\mathcal{S}_{n}$ is the space of
$n$-qubit super-operators. The existence of $\mathcal{E}$ already excludes,
e.g., time-dependent effects in between different experiments, and the
factorization into a map $\phi$ further restricts to Markovian noise. Under
this assumption it can be proven that RB protocols [9, 10, 11, 12, 13, 14]
function correctly [14, 34, 35]. For non-Markovian noise much less is known,
but in the context of RB rigorous results have been obtained for quasi-static
noise [36], time-dependent noise [37] and more recently using tensor-models
[38]. We expect these results to broadly carry over to random sequence
estimation.

Second, we assume gate-independent noise, positing the existence of quantum
channels $\Lambda_{L},\Lambda_{R}$ such that

$\phi(g)=\Lambda_{L}\omega(g)\Lambda_{R}$ (3)

where $\omega(g)(\rho)=U_{g}\rho U_{g}{}^{\dagger}$ is some ideal
implementation of the gate $g$. We argue in section II.11 that our results
also apply (up to a negligible error) in the more general Markovian error
model, but rigorously proving this (along the lines of ref. [14]) is beyond
the scope of this work.

Instead of $\Lambda_{R},\Lambda_{L}$ describing the noise of the gate-set
implementation, one can also take the perspective of actively interleaving a
channel of interest between a fairly ideal implementation of a gate-set (as is
done in interleaved randomized benchmarking [30]). While different in protocol
and data interpretation, in the analysis, this _black-box query model_

$\phi(g)=\Lambda\omega(g)$ (4)

is simply a special case of the gate-independent noise model and results carry
over.

The main analytical result of this work is to establish rigorous performance
guarantees for the estimation from gate-set shadows. The obvious first
question being: what do we actually estimate? As a first result, we establish
the ‘simple’ model that we should be fitting to the data. We show that for a
probe operator $A$ the empirical estimator of the protocol converges in
probability with the number of samples $S$ in the shadow to a matrix-
exponential decay

$\hat{k}_{f_{A}}(m)\quad\xrightarrow{S\to\infty}\quad
k_{f_{A}}(m)=\operatorname{Tr}[\Theta\Phi^{m-1}]\,.$ (5)

Here, the matrix $\Phi$ depends only on the ‘between-gates noise channel’
$\Lambda:=\Lambda_{R}\Lambda_{L}$ and the probe super-operator $A$, while
$\Theta$ captures SPAM dependence. In particular, if $\omega$ contains $t$
copies of the representation $\sigma$ then we have

$\Phi_{i,j}=\frac{1}{|P_{j}|}\operatorname{Tr}(P_{i}AP_{j}\Lambda)$ (6)

where $P_{i}$ is the projector onto the $i$th copy of the representation
$\sigma$ inside $\omega$. Note that here the trace is taken on the space of
super-operators. We give the derivation of this result in the Supplementary
Note 4.

Equation 5 indicates that we should fit a linear combination of (up-to) $t$
exponential decays to the sequence average $\hat{k}_{f_{A}}(m)$. The resulting
decay parameters are the eigenvalues of the matrix $\Phi$, which encode
information about the overlap of $\Lambda$ and $A$ in the representation
space.

A particularly simple fitting model with easily interpretable decay
parameters, arises when the representation $\sigma$ appears in the
decomposition of $\omega$ without multiplicities (i.e., there is no other
representation in $\omega$ related to $\sigma$ by a change of basis). If
$\sigma$ is multiplicity-free, then $k_{f_{A}}(m)$ describes a single scalar
exponential decay

$k_{f_{A}}(m)\propto p_{\sigma,A}(\Lambda)^{m-1},$ (7)

with decay parameter

$p_{\sigma,A}(\Lambda)=\frac{1}{d_{\sigma}}\operatorname{Tr}[A_{\sigma}\Lambda]\,$
(8)

and $A_{\sigma}=P_{\sigma}AP_{\sigma}$ the probe operator restricted to the
representation $\sigma$ of dimension $d_{\sigma}$. Note that the
proportionality now hides the SPAM-dependent pre-factor.

Thus, by fitting a single exponential decay to the empirically observed
sequence averages $\hat{k}_{f_{A}}$, we can estimate $p_{\sigma,A}(\Lambda)$,
the trace-overlap of $\Lambda$ with $A$ on $\sigma$. The decay parameter can
be thought of as a _generalized fidelity_ or effective depolarization
parameter, indicating how much the noise channel $\Lambda$ agrees on average
with the probe operator $A$ on the representation space of $\sigma$.

###  II.4 Sample complexity

Against the background of the extensively explored variants of RB protocols,
the above decay model is not entirely unexpected. A priori less obvious,
however, is the sample efficiency of gate-set shadow protocols. The sequence
correlation functions $f(x,\vec{g})$ involve normalization factors that
typically scale with the dimension of the irreducible representation under
consideration. As a consequence their range can become exponentially large in
the number of qubits, causing a simple empirical mean estimator to be
susceptible to outliers in the measurement statistics, as well as making a
suitably bounded variance a priori nontrivial. Going significantly beyond the
established statistical guarantees in RB, we establish general variance bounds
for the UIRS protocol. We do this by introducing a sequence analogue to the
shadow norm introduced in ref. [16] defined on probe super-operator $A$ as
opposed to observables. Emphasizing its explicit dependence on the sequence
length $m$ we call this norm (really a family of norms indexed by $m$) the
_dynamic shadow norm_ $\left\|A\right\|_{\mathrm{dyn},m}$. This norm, formally
defined in Supplementary Equation (25), depends on the underlying gate-set
$\mathbb{G}$ as well as the ideal input POVM $\\{E_{x}\\}$ and state $\rho$.
Given these parameters it quantifies the sample complexity of estimating the
mean $k_{f_{A}}(m)$ for arbitrary gate-independent noise. Because of its
dependence on the sequence length, the dynamic shadow norm is a more intricate
object than its state counterpart. Evaluating it for specific gate-sets
accounts for the bulk of the technical innovation in this paper. In terms of
the dynamic shadow norm we have the following upper bound on the variance of
the UIRS protocol.

######  Theorem 1 (Upper bound on the variance).

Consider an UIRS protocol (at sequence length $m$) with gate-set $\mathbb{G}$
and a correlation function $f_{A}$ with probe operator $A$. The variance of
the associated mean $k_{f_{A}}(m)$ is bounded as

$\mathbb{V}_{A}(m)\leq\left\|A\right\|_{{\rm dyn},m}\,.$ (9)

An extended statement and the proof is given in the Supplementary Note 4. The
bound on the variance $\mathbb{V}_{A}(m)$ directly implies a non-asymptotic
bound on the sample complexity for the estimator $\hat{k}_{f_{A}}(m)$ with
exponential confidence through the use of median-of-means estimation. The
exponential confidence in particular allows us to estimate ‘many’ quantities
simultaneously from the same shadow data with only logarithmic overhead in the
number of quantities. See Supplementary Note 3 for details. More precisely, we
get the following guarantee: Run the UIRS protocol (at sequence length $m$)
and measure a gate-set shadow of $S$ many samples. Choose a set $\mathcal{A}$
of probe operators, an $\epsilon>0$ and ensure that for all $A\in\mathcal{A}$

$S\geq C\left\|A\right\|_{{\rm
dyn,m}}\frac{\log(|\mathcal{A}|)}{\epsilon^{2}}\,$ (10)

for a suitable constant $C$. Then, in the post-processing, we obtain
$\epsilon$-additive estimates, i.e., $|{k}_{A}(m)-\hat{k}_{A}(m)|\leq\epsilon$
for all $A\in\mathcal{A}$.

Hence, bounding the dynamic shadow norm for all $A\in\mathcal{A}$ and
different sequence lengths $m$ gives simultaneous guarantees for many
estimators $\hat{k}_{A}(m)$ with an overall sampling complexity being the sum
of the bounds Equation 10 for all $m$. As explained above,
$m\mapsto\hat{k}_{A}(m)$ is then fitted using a theoretical signal model. For
example, in the scenario of multiplicity-free representations giving rise to a
single exponential decay eq. 7, we thereby obtain an estimator for
$p_{\sigma,A}(\Lambda)$ for all $A\in\mathcal{A}$. The exponential fitting
itself is a well-studied problem, for which many advanced techniques [39, 40],
flexible software packages [41], and rigorous bounds [42] can be readily
applied.

###  II.5 Example: Multi-qubit Clifford UIRS

We now provide two particularly practically relevant examples of UIRS
protocols, derive their signal model and a dynamical shadow norm bound
guaranteeing their efficiency.

The first example is the multi-qubit Clifford group $\mathbb{C}_{n}$ that
already takes a prominent role in quantum characterization and quantum
computation more generally [43]. We consider an UIRS experiment for
$\mathbb{C}_{n}$: i.e., sequences of i.i.d. Clifford gates uniformly drawn at
random, acting on the initial state $\ket{0}\\!\\!\bra{0}$ and ending in a
computational basis measurement. This is a common gate-set with a well-
understood representation structure, allowing us to explicitly calculate the
sequence mean $k_{A}(m)$ and give bounds on the dynamic shadow norm
$\left\|A\right\|_{{\rm dyn},m}$ which controls the sample complexity of
sequence estimation.

#### Signal model.

The adjoint representation of the multi-qubit Clifford group $\omega(g)$
decomposes into two inequivalent irreducible representations [44]:
$\sigma_{tr}$ supported on the normalized identity matrix and $\sigma_{\rm
ad}$ supported on the space of traceless matrices, spanned by the generalized
Pauli matrices. See Supplementary Note 2 for details. We focus on sequence
correlation functions with support on $\sigma_{\rm ad}$ only, i.e., $A=P_{\rm
ad}AP_{\rm ad}$. Then, $k_{f_{A}}(m)$ describes a single exponential decay eq.
7 with

$p_{{\rm ad},A}(\Lambda)=\frac{1}{2^{2n}-1}\operatorname{Tr}(P_{\rm ad}AP_{\rm
ad}\Lambda)\,.$ (11)

This is a familiar quantity: For $A=P_{\rm ad}$, it corresponds to the
depolarizing probability (essentially the average fidelity) of the channel
$\Lambda$. As a very special case the Clifford UIRS protocol in this way
emulates standard Clifford randomized benchmarking without performing an
inversion. However, gate-set shadows are considerably more flexible. For
instance, by choosing $A=U$ a unitary channel, $p_{{\rm ad},U}(\Lambda)$
measures the relative average fidelity of $\Lambda$ w.r.t. the unitary $U$
(i.e., the average fidelity of $U^{\dagger}\circ\Lambda$). In particular, for
$U$ a Clifford channel, the corresponding sequence correlation function can be
evaluated efficiently. Relative average gate fidelities are also estimated in
interleaved RB. Compared to existing interleaved RB protocols such as the
scheme of ref. [29], gate-set shadows have the crucial advantage that the
experimental protocol itself is independent of $U$.

Since we do not have to implement $A$ on a quantum device, we can also
consider $A$ that do not correspond to quantum channels such as rank-one
super-operators of the form $X\operatorname{Tr}(Y\,\cdot\,)$for operators
$X,Y$. Hence, the gate-set shadows are a versatile tool to estimate properties
of the implementation of a Clifford gate-set.

#### Dynamical shadow norm.

The versatility of Clifford UIRS in practice of course crucially depends on
the sample efficiency of the estimation. From the above it is not clear that
$k_{A}(m)$ can be efficiently estimated for arbitrary $A$. Demanding that
$k_{A}(1)=1$ in the limit of perfect state preparation, measurement and gates,
the normalization factor $\alpha$ in eq. 2 is $\alpha=2^{n}+1$, leading to a
single-shot estimator taking values exponentially large in $n$. Building upon
the machinery of the dynamic shadow norm and theorem 1, we can still provide
guarantees for efficiently estimatable probe operators and investigate the
limits of Clifford UIRS. As a first step, we assume $A$ to be a restriction of
a unitary channel $U$ to the traceless subspace, i.e., $A=P_{\rm ad}UP_{\rm
ad}$. In this case, the dynamic shadow norm can in fact be bounded by a small
constant independent of the sequence length.

######  Theorem 2 (Clifford UIRS unitary norm bound).

For the $n$-qubit Clifford UIRS protocol, $U$ a unitary channel, and $A=P_{\rm
ad}UP_{\rm ad}$, it holds that

$\left\|A\right\|_{{\rm dyn},m}\leq 10\,.$ (12)

Theorem 2 is noteworthy for several reasons. First, it does not depend on the
number of qubits $n$. Therefore, the estimation of $k_{U}(m)$ is efficient
even on a quantum system consisting of many qubits. Second, the shadow-norm
bound does not depend on the sequence length $m$, enabling relative accuracy
estimation of the decay rate in certain regimes. We note that the constant
$10$ is probably sub-optimal. The derivation of this theorem can be found in
the Supplementary Note 6.

As the main consequence of theorem 2 together with eq. 10, we find that it is
possible to sample-efficiently estimate exponentially many relative fidelities
with respect to unitary channels to additive precision from the same gate-set
shadows obtained by multi-qubit Clifford UIRS.

Next, we consider a general probe super-operator $A$ restricted to the
traceless subspace. Note that $A$ does not need to be a quantum channel. In
the following, we show that the dynamical shadow norm can be controlled in
terms of the unitarity [45] of $A$,

$u(A)=\operatorname{Tr}(AA{}^{\dagger})(2^{2n}-1)^{-1}\,.$ (13)

For instance, $u(A)\leq 1$ if $A$ is a quantum channel with equality if $A$ is
indeed unitary. We prove the following theorem.

######  Theorem 3 (Clifford UIRS general norm bound).

Consider the $n$-qubit Clifford UIRS protocol and let $A=P_{\rm ad}AP_{\rm
ad}$ be a probe super-operator restricted to the traceless subspace. The
dynamic shadow norm for $m>2$ is upper bounded by

$\left\|A\right\|_{{\rm dyn},m}\leq C\,m^{2}r(A)^{m-1}\max\\{r(A),1\\},$ (14)

with $r(A)=(1+2^{4-n/3})u(A)$ and suitable constant $C$.

The proof of this theorem, given in the Supplementary Note 6, is similar in
spirit to theorem 2, but significantly more involved. Choosing $A$ to be
unitary $(u(A)=1)$ does not recover theorem 2, due to the appearance of the
quadratic scaling in $m$. This term arises because we consider general probe
super-operators $A$, giving rise to polynomial transient dynamics in the
dynamic shadow norm (due to the non-normality of the underlying operators [46,
Chapter $6$]). For many sensible choices of $A$, the polynomial scaling in $m$
does not appear as is evidenced by theorem 2. Also, the bound does not quite
scale with unitarity $u(A)$, but rather with the parameter $r(A)$ which
differs from $u(A)$ by an exponentially small factor. We believe this to be an
artifact of the proof technique.

This theorem leads us to the remarkable conclusion that the multi-qubit
Clifford UIRS protocol allows us to estimate overlaps $p(A\Lambda)$ for a very
large class of super-operators. In particular, $A$ can be any trace non-
increasing map, allowing us, e.g., to characterize the overlap between the
noise channel $\Lambda$ and sets of Kraus operators, making the Clifford UIRS
protocol an all-purpose tool for noise map exploration.

###  II.6 Example: Local Clifford UIRS

A particularly scalable and interesting protocol arises when performing a UIRS
protocol with the local Clifford group $\mathbb{C}_{1}^{\times n}$ over $n$
qubits. In this case, the experiment consists of performing sequences of
i.i.d. random single-qubit gates simultaneously on all qubits, initially
prepared in $\ket{0}\\!\\!\bra{0}$ ending with a computational basis
measurement.

For $\mathbb{C}_{1}^{\times n}$ the conjugate representation
$\omega(g)=U_{g}\cdot U_{g}{}^{\dagger}$ with
$U_{g}=U_{(g_{1},\ldots,g_{n})}=U_{g_{1}}\otimes\ldots\otimes U_{g_{n}}$
decomposes into $2^{n}$ irreducible, mutually inequivalent representations
$\sigma_{w}$ with $w\in\\{0,1\\}^{n}$ that have support on the normalized non-
identity Pauli operators on all qubits $i$ for which $w_{i}=1$. We denote the
projectors onto these irreducible sub-representations as $P_{w}$ (see
Supplementary Note 2 for more details).

#### Signal model.

We consider sequence correlation functions with probe operators $A$ that only
have support on a single irreducible representation $\sigma_{w}(g)$ and set
$\alpha=2^{n}3^{|w|}$. Then, the mean $k_{f_{A}}(m)$ again describes a single
exponential decay eq. 7 with

$p_{w,A}(\Lambda)=\operatorname{Tr}(P_{w}\Lambda P_{w}A)3^{-|w|}\,.$ (15)

We will refer to this quantity as a _local fidelity w.r.t. $A$_. The local
fidelity is again somewhat familiar. The special case $p_{w,\mathbb{I}}$ has
been called the ‘addressability’ in ref. [28], where it was used to gain
information about the strength of correlated errors. Using gate-set shadows of
simultaneously applied local gate sequences, we can collect even more
information about correlated errors, giving rise to an efficient _cross-talk
tomography protocol_ introduced in section II.9. We can again equip the UIRS
protocol with sampling complexity guarantees by bounding the shadow norm.

#### Dynamic shadow norm.

We derive a bound on the dynamic shadow norm of the local Clifford group that
depends exponentially on the Hamming weight $|w|$ of the bit-string $w$
labeling the representation being addressed but is independent of the total
number of qubits in the system.

######  Theorem 4 (Local Clifford UIRS norm bound).

For the local Clifford UIRS protocol on $n$ qubits, $w\in\\{0,1\\}^{n}$, and
$A=P_{w}AP_{w}$ a probe operator, it holds that

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$ $\displaystyle\leq
2^{|w|}3^{2|w|}\big{[}3^{-|w|}\operatorname{Tr}(AA{}^{\dagger})\big{]}^{m-1}\,.$
(16)

The proof is given in the Supplementary Note 5. Note that the term inside the
square bracket in eq. 16 can be considered as a variant of the unitarity
restricted to the image of $P_{w}$. In particular, if $A=P_{w}UP_{w}$ for any
unitary channel $U$ we have $3^{-|w|}\operatorname{Tr}(AA{}^{\dagger})=1$.
Thus, for restrictions of unitary probe operators the bound becomes
independent of the sequence length and in consequence the protocol is sample-
efficient for bounded $|w|$.

###  II.7 Example beyond UIRS: Pauli-noise estimation

Thus far we have focused on uniformly independently sampled random sequences
(UIRS protocols). It is also fruitful to consider more general probability
distributions on the set of sequences of a given length. We give an example
for this by constructing a simple protocol that estimates the diagonal
elements of an $n$-qubit channel $\Lambda$ using only $O(n2^{n})$ samples.
This sampling complexity matches the asymptotic bound given for this task in
ref. [19]. Using gate-set shadows, however, gives a simpler experimental
description and analysis. To this end, consider random sequences of the form
$\vec{g}=(c^{-1},p_{m},\ldots,p_{1},c)$ where $p_{1},\ldots,p_{m}$ are chosen
independently uniformly at random from the Pauli group $\mathbb{P}_{n}$ and
$c$ is chosen uniformly at random from the Clifford group $\mathbb{C}_{n}$.
Note the inverse $c^{-1}$ here at the end of the sequence. In a black-box
fashion, we additionally intersperse the channel $\Lambda$ in between
executing the random Pauli elements in the experiment. The measurement is
again a computational basis measurement and the initial state
$\rho=\ket{0}\\!\\!\bra{0}$. Choose $\tau$ to be a Hilbert-Schmidt normalized
traceless Pauli operator. As the associated correlation function we define

$f_{\tau}(x,\vec{g})\coloneqq\alpha\operatorname{Tr}[E_{x}\omega(c)\omega(p_{m})A_{\tau}\ldots
A_{\tau}\omega(p_{1})\omega(c)\rho]\,$ (17)

with $A_{\tau}\coloneqq\tau\operatorname{Tr}(\tau\,\cdot)$ and
$\alpha=2^{n}(2^{n}+1)$. For convenience, we ignore the SPAM in deriving and
stating the following results. Both of these assumptions can be easily
relaxed. As we show in the Supplementary Note 7, the corresponding sequence
mean is the power of the diagonal matrix entry of $\Lambda$ corresponding to
$\tau$, i.e.,

$k_{\tau}(m)=\operatorname{Tr}[\tau\Lambda(\tau)]^{m-1}.$ (18)

We further show that the variance of the associated estimator can be bounded
as

$\mathbb{V}_{\tau}(m)\leq\frac{2^{3n}(2^{n}+1)^{3}}{2^{3n}(2^{2n}-1)}=O(2^{n}),$
(19)

for all choices of $\tau$. Note that there are $4^{n}-1$ such choices,
characterizing all diagonal elements of the quantum channel $\Lambda$. Hence,
by using median-of-means estimators, we can estimate $k_{\tau}(m)$ for all
$\tau$ to uniform additive precision using $O(n2^{n})$ samples (independently
of $m$). By the analysis in ref. [42] for the estimation of single exponential
decays, and the fact that the decay rates $\Lambda_{\tau,\tau}$ are strongly
clustered ([33, Lemma 4]) this leads to a relative precision estimation of the
associated Pauli fidelities, matching the performance given in ref. [19].

###  II.8 Application: Learning unitary noise models

In the previous section we have shown how to efficiently estimate the overlap
of certain probe-operators with the noise of a gate-set. This data, e.g., the
average gate fidelity of the noise with a specific gate, is already of
interest. The most intriguing feature, however, is that we can estimate many
different probe-operators from the same data. In this way, we can use
estimates from gate-set shadows as a subroutine in a complex post-processing
pipeline that extracts more information about the noise. This opens up the way
to perform many different characterization tasks that arise in a full-scale
engineering cycle of building a quantum computer from the same simple data.
Importantly, the resulting protocols automatically inherit the SPAM robustness
of the estimation protocol. We illustrate these possibilities with three
concrete examples.

Figure 2:  Numerical simulations of two potential applications, unitary noise
optimization (sec. II.8) and cross-talk tomography (sec. II.9). Panels a) and
b) show simulation results of the multi-qubit Clifford UIRS protocol for two
qubits and 1000 random sequences per sequence length. Between every Clifford
gate $\mathcal{C}$, two independent $Z$-rotations $R_{Z}(\theta)$ with
rotation angles $\theta_{1}=0.07$ and $\theta_{2}=0.13$ have been applied (see
circuit diagram c)). Panel b) shows average fidelities $F(U(\theta),\Lambda)$
reconstructed from the gate-set shadows using the ansatz
$U(\theta_{1},\theta_{2})=R_{Z}(\theta_{1})\otimes R_{Z}(\theta_{2})$. Example
decays of the sequence averages $k(m)$ are shown in panel a) with bootstrapped
95% confidence intervals around the decay points. Panels e) to g) display
simulation results for cross-talk tomography from two-qubit local Clifford
UIRS data with 15.000 random sequences per sequence length. After every layer
of local Cliffords, an entangling cross-talk noise process $\mathcal{N}_{c}$
has been applied (see the circuit diagram d)). Panel e) shows the _Pauli
transfer matrix_ (PTM) of the reconstructed pinched marginal $S$ Supplementary
Equation (107), for cross-talk of the form $\mathcal{N}_{c}=XX(\theta)$, with
dashed boxes indicating the unital marginals $\Lambda_{0,1}$, $\Lambda_{1,0}$,
and $\Lambda_{1,1}$. Panels f) and g) show the PTMs of the difference between
the unital marginal $\Lambda_{1,1}$ and the tensor product
$\Lambda_{1,0}\otimes\Lambda_{0,1}$ as a characterization of the cross-talk
between the two qubits, for cross-talk $\mathcal{N}_{c}=XX(\theta=0.4)$ in f)
and $\mathcal{N}_{c}=ZZ(\theta=0.4)$ in f). Simulations have been performed
using Qiskit [47] with single-qubit depolarizing noise of $p_{1}=0.002$ for
single-qubit gates and two qubit depolarizing noise $p_{2}=0.01$ for two-qubit
gates (on top of the custom noise processes after each Clifford layer). For
the PTM plots, modified functions from the Forest Benchmarking package [48]
have been used.

When characterizing noisy quantum gates one differentiates between coherent
noise (due to imperfect specification of the gate) and incoherent noise (due
to interactions with the environment). These two types of noise have different
consequences for, e.g., error correction [49, 1] and are engineered away in
different ways. At the same time, coherent errors can be corrected by
experimental design and control if one has a concrete description. Given a
model for a unitary channel $\theta\mapsto U(\theta)$, we can learn the model
parameters $\theta$ approximating the noise channel $\Lambda$ by maximizing
$F(U(\theta),\Lambda)$. During the optimization the objective function, its
gradient, etc. can be estimated from the same classical gate-set shadow. For
the multi-qubit Clifford UIRS every estimation requires a polynomial size
shadow in the number of qubits and only a logarithmic overhead in the number
of evaluations $F(U(\theta),\Lambda)$. A numerical simulation of a simple
learning example is given in fig. 2.

###  II.9 Application: Cross-talk tomography

A key source of error in today’s quantum computing devices is correlated
noise, or cross-talk. For this reason, a significant effort has gone into
characterizing cross-talk errors specifically [28, 50, 51]. Using the
flexibility of extracting manifold information from gate-set shadows in the
post-processing, we here propose _cross-talk tomography_ as an efficient,
robust, and detailed cross-talk characterization procedure, based on the local
Clifford UIRS protocol.

The protocol gains tomographic information about, what we call, the _unital
marginals_ $\Lambda_{w}=P_{w}\Lambda P_{w}$, $w\in\\{0,1\\}^{n}$, of the noise
channel $\Lambda$. (Here, $P_{w}$ is again the projector onto the irreducible
representations of the local Clifford group.) These unital marginals arise as
restrictions of channel marginals $\Lambda_{\bar{A}}$, where one evaluates
$\Lambda$ on a maximally mixed input on a system $A$ and traces out the
resulting state on $A$ [52].

Now $\Lambda_{w}$ can be reconstructed via simple linear inversion (see ref.
[32, Lemma 37]) from the local fidelities
$p_{w,\mathcal{C}}(\Lambda)=3^{-|w|}\operatorname{Tr}(\Lambda
P_{w}\mathcal{C}P_{w})$ with respect to the probe-operators given by the local
Clifford channel $\mathcal{C}$ according to

$\Lambda_{w}=\frac{1}{|\mathbb{C}_{w}|}\sum_{\mathcal{C}\in\mathbb{C}_{w}}3^{2|w|}p_{w,\mathcal{C}}(\Lambda)\mathcal{C}^{\dagger}P_{w}\,,$
(20)

where the sum is restricted to local Clifford channels with unitaries from the
subgroup $\mathbb{C}_{w}$ of $\mathbb{C}_{n}$ acting non-trivially on only the
qubits in the support of $w$. In fact, it is sufficient to consider all local
Clifford channels $\mathcal{C}$ that act non-trivially on the support of the
bit-string $w$. Not restricting the non-trivial support of $\mathcal{C}$,
however, allows us to simultaneously reconstruct $\Lambda_{w}$ for multiple
values of $w$.

This constitutes the basis of cross-talk tomography for $k$-local
interactions. Let $H_{k}\subset\\{0,1\\}^{n}$ be the subset of bit strings
with Hamming weight $k$. i) Perform the UIRS experiment for the local Clifford
group over $n$ qubits. ii) Estimate $p_{w}(\mathcal{C})$ for all $w\in H_{k}$
and for all $\mathcal{C}$ acting non-trivially on the support of $w$. iii)
Reconstruct all $\Lambda_{w}$ for $w\in H_{k}$.

By comparing $\Lambda_{w}$ for different bit strings, one obtains information
about the correlations present in $\Lambda$. Building upon the guarantees for
UIRS, we show that cross-talk tomography is $\epsilon$-accurate in diamond
norm for all $\Lambda_{w}$ using $O(k^{2}\,2^{9k}/\epsilon^{2})$ shadow
samples (up-to log-factors). Thus, for small $k$, cross-talk tomography is
highly scalable to large numbers of qubits. In the light of theorem 4, this
efficiency stems from using local unitary probe operators. The derivation and
even tighter guarantees are given in Supplementary Note 8.

As an illustration we study the protocol with a $2$-qubit example. We start by
using the local Clifford UIRS protocol to reconstruct the $2$-qubit unital
marginals $\Lambda_{1,0},\Lambda_{0,1}$ and $\Lambda_{1,1}$. Next we compute
the tensor product $\Lambda_{1,0}\otimes\Lambda_{01}$. It is straightforward
to see that if the channel $\Lambda$ is a tensor product of single-qubit
quantum channels featuring no correlations (i.e., there is no cross-talk) then
$\Lambda_{1,0}\otimes\Lambda_{0,1}=\Lambda_{1,1}$. Hence, both the difference
$\Lambda_{1,0}\otimes\Lambda_{0,1}-\Lambda_{1,1}$ and the product
$\Lambda_{1,1}(\Lambda_{1,0}\otimes\Lambda_{0,1})^{-1}$ provide meaningful
characterizations of cross-talk present between qubits $1$ and $2$. The
difference measure can be considered as a generalization of the commonly used
addressability metric proposed in ref. [28]. But going beyond a mere metric,
we expect that the channel marginals not only detect the presence of cross-
talk, but also provide more detailed diagnostic information. As a proof of
principle we have numerically simulated the above protocol to diagnose cross-
talk in a two-qubit system. The results of a numerical simulation of the
protocol are presented in fig. 2.

###  II.10 Application: SPAM-robust channel reconstruction

Kimmel et al. [29] have proposed the idea to combine the output of $O(2^{4n})$
different interleaved RB experiments in order to get a robust tomographic
estimate of a unital quantum channel $\Lambda$. By explicitly exploiting the
low Kraus-rank, _compressive RB tomography_ [31, 32] can reconstruct a unitary
approximation to the quantum channel from (up-to-log-factors) $O(2^{2n})$
randomly selected different relative average-gate fidelities with respect to
Clifford unitaries. The previous references, however, left the problem open of
providing a SPAM-robust RB protocol that achieves the information-
theoretically optimal sampling complexity of $O(2^{4n})$ [32] for
reconstructing a unitary channel.

We fill in this blank using the data from a multi-qubit Clifford UIRS
protocol. Using a set of randomly selected Clifford unitaries as probe-
operators, we can provide the input data to the reconstruction algorithm of
ref. [32]. We show in Supplementary Note 9 that the number of gate-set shadows
to guarantee an accurate reconstruction (in Hilbert-Schmidt norm of the Choi-
states) indeed matches the lower-bound of $O(2^{4n})$. Note that the number of
channel invocations is bounded by the maximal sequence length times the number
of sequences. Besides the favorable scaling, the UIRS protocol has the crucial
advantage compared to, e.g., the interleaved protocol of ref. [29] that the
same measurement data is used for estimating all the average fidelities.

Going beyond the compressive reconstruction of unitary quantum channels, we
can use Clifford UIRS as a primitive for the robust reconstruction of
arbitrary unital quantum channels in the spirit of ref. [29], see also ref.
[32, theorem 38] and ref. [53]. The required size of the gate-set shadow is
$O(2^{8n})$ for an accurate reconstruction in any norm in which unitary
channels are normalized.

###  II.11 Gate-dependent noise

The presentation so far assumed gate-independent noise. This assumption can be
substantially relaxed, at the cost of introducing a more complex description
of the noise. We will focus on the UIRS protocol, which is particularly robust
against gate-dependent fluctuations. We give a fairly comprehensive argument,
but leave a rigorous proof of the robustness to future work. Our argument
follows that of the robustness against gate-dependent errors for RB [34, 14].
For gate-dependent noise, the data form in expectation can be generally
written as

$k_{A}(m)=\operatorname{Tr}\left[\Xi\,(A\otimes\mathbb{I})(\mathcal{F}(\phi)[\sigma])^{m-1}\right],$
(21)

where $\Xi$ depends on the state and measurement and the operator
$\mathcal{F}(\phi)[\sigma]\coloneqq\mathbb{E}_{g\in\mathbb{G}}\
\sigma(g)\otimes\phi(g)$ is known as the (non-commutative) Fourier transform
of $\phi$, evaluated at the irreducible representation $\sigma$; see the
derivation of Theorem 7 in the Supplementary Information.

A key fact about this Fourier transform (see, e.g., ref. [54] for a proof) is
that if $\phi$ is a representation $\omega$ (i.e., a perfectly implemented
gate-set), then $\mathcal{F}(\phi)[\sigma]$ is an orthogonal projector with
rank equal to the number of copies of $\sigma$ present in $\omega$. For
simplicity, let $\omega$ be multiplicity-free. Then,
$\mathcal{F}(\phi)[\sigma]$ is a rank-one projector. This implies that
$(A\otimes\mathbb{I})\mathcal{F}(\phi)[\sigma]$ is also a rank-one projector.
When $\phi$ is a sufficiently ‘good’ implementation of $\omega$, the
difference between $\mathcal{F}(\phi)[\sigma]$ and
$\mathcal{F}(\omega)[\sigma]$ is small (in some suitable norm) and can be
regarded as a perturbation of $\mathcal{F}(\omega)[\sigma]$. (See ref. [14]
for a discussion of norms on this space.) Applying the perturbation theory of
non-normal matrices, we conclude that
$(A\otimes\mathbb{I})\mathcal{F}(\phi)[\sigma]$ is as well approximately rank-
one, and in particular that there exist super-operators
$\Lambda_{L},\Lambda_{R}$ such that

$\big{(}(A\otimes\mathbb{I})\mathcal{F}(\phi)[\sigma]\big{)}^{m}=\left(A\Lambda_{R}P_{\sigma}\operatorname{Tr}[P_{\sigma}\Lambda_{L}\,\cdot\,]\right)^{m}+E^{m}$
(22)

where $E$ is a matrix of small norm and $P_{\sigma}$ is the projector onto
$\sigma$ (in the image of $\omega$). This means that the decay rate $k_{A}(m)$
has the general functional form

$k_{A}(m)=B_{1}p(A)^{m-1}+B_{2}\delta(E)^{m-1}$ (23)

where $B_{1},B_{2}$ are real numbers encoding SPAM, $\delta(E)$ is small, and
$p(A)$, the dominant eigenvalue of
$(A\otimes\mathbb{I})\mathcal{F}(\phi)[\sigma]$, is given by

$p(A)={|P_{\sigma}|^{-1}}\operatorname{Tr}(\Lambda_{L}P_{\sigma}AP_{\sigma}\Lambda_{R})\,.$
(24)

Up to a small and exponentially decreasing error, we thus recover the
functional form of eq. 5 also in the presence of gate-dependent noise. It is
important to note however, that in this general case $\Lambda_{L}$ and
$\Lambda_{R}$ (and their product) need not be CPTP. This complicates the
interpretation of $p(A)$ as describing an aspect of a physical noise process.

##  III Discussion

It has long been known that classical randomness can facilitate the
construction of informative characterization protocols for quantum devices.
Randomized benchmarking [9, 10, 11, 12, 13, 14] and classical shadow
estimation [16, 17] are examples of this mindset. In our work, we follow this
paradigm even more stringently for diagnosing noise in gate-set
implementations. Instead of engineering sophisticated and specific
experimental protocols for a specific task, we turn the approach upside down:
we focus on the ‘simplest’ randomized protocol that can be implemented with
current and near-term quantum architectures: Random gate-sequences followed by
native measurements. Accepting this restriction, we then ask how detailed
diagnostic information can be extracted from the resulting data and most
importantly how many samples are required.

It turns out that the resulting prescription—a single experiment that can and
has been implemented experimentally already—allows for solving many
benchmarking, certification and identification problems with (near-)optimal
efficiency. All the technicalities that come along with different tasks are
shifted to the classical post-processing phase. Most importantly, multiple
diagnostic tasks can be performed from the same measurements, allowing us to
base an entire engineering cycle on a single experiment.

The ideas advocated here constitute the beginning rather than the conclusion
of a program. We regard our theoretical results as a strong motivation to
experimentally realize and make use of the concrete applications, such as
robust learning of unitary noise and cross-talk tomography. In addition,
several further extensions seem exciting. A logical first extension of our
work is UIRS with other groups and non-uniform measures over said groups. As
with state shadow tomography and randomized benchmarking, we believe the UIRS
protocol can be furnished with rigorous guarantees for several other useful
gate-sets such as the matchgates [55, 56], the Heisenberg-Weyl group, the
${\rm CNOT}$-dihedral group and even gate-sets that do not constitute a group
[57, 58].

We also illustrated the potential of using correlated sequences where the
gates are not drawn independently. We believe that using simple correlated
sequences gives a fruitful perspective on long-standing problems such as the
characterization of non-Markovian and time-varying noise processes in an
experimentally friendly and scalable way. Furthermore, while not demonstrated
here, akin to their state analog, gate-set shadows can also be used for
estimating non-linear quantities.

While the bulk of this work discusses diagnostic tools for developing near-
term quantum computing devices, random sequence protocols apply beyond that.
We expect that gate-set shadows will for instance find application as a
primitive in quantum machine learning [59], in particular in dynamic settings
such as time-series estimation. Also in this context, the possibility to
‘measure first and ask later’ increases the flexibility in devising hybrid
quantum-classical schemes with experimentally feasible quantum computations.

##  IV Data availability

The simulated data used for creating the plots in fig. 2 have been deposited
on Figshare and are publicly available [60].

##  V Code availability

The code used to simulate the protocol and create the plots in fig. 2 is
available upon request.

Supplemental material

##  VI Notation

Throughout this work, we are operating in the _Liouville_ or _transfer matrix
representation_ of quantum channels. We represent finite-dimensional $d\times
d$ density matrices $\rho$ as length $d^{2}$ column vectors
$|{\rho}{\rangle\\!\rangle}$ and POVM elements $E$ as length $d^{2}$ row
vectors ${\langle\\!\langle}{E}|$, with a corresponding trace-inner product
${\langle\\!\langle}{E}|\rho\rangle\\!\rangle=\operatorname{Tr}(E{}^{\dagger}\rho)$.
In this picture, super-operators $\mathcal{E}$ get mapped to $d^{2}\times
d^{2}$ matrices $\mathcal{E}$ with the property
$\mathcal{E}|{\rho}{\rangle\\!\rangle}=|{\mathcal{E}(\rho)}{\rangle\\!\rangle}$.
Note that this representation is compatible with composition of super-
operators (mapping to matrix multiplication), and the taking of tensor
products. When $d$ is a power of two a good basis for the space of matrices is
the set of Hermitian Pauli operators $\mathbb{P}^{*}$ (normalized under the
trace inner product), in this case we also always write $d=2^{n}$. We denote
the normalized identity by $2^{-n/2}\mathbb{I}=\tau_{0}$ and the set of
normalized traceless Hermitian Pauli matrices $\tau$ as $\mathbb{P}^{*}_{0}$.
Finally, we use a tilde to indicate noisy implementations of POVM elements and
states, so $\tilde{\rho}$ is a noisy implementation of the state $\rho$ and
$\\{\tilde{E}_{x}\\}_{x}$ is a noisy implementation of the POVM
$\\{E_{x}\\}_{x}$. For the specific case of the all-zero computational basis
state $\ket{0}\\!\\!\bra{0}^{\otimes n}$ we write
$|{0_{n}}{\rangle\\!\rangle}$ (with noisy version
$|{\tilde{0}_{n}}{\rangle\\!\rangle}$) and for the computational basis POVM
$\ket{x}\\!\\!\bra{x}$ we write ${\langle\\!\langle}{x}|$ (with noisy version
${\langle\\!\langle}{\tilde{x}}|$).

##  VII Technical preliminaries on representation theory

In this section we recall some basic facts of representation theory (of finite
groups), and discuss generally how it applies to our work, with a particular
focus on the representation theory of the Clifford group. For a more in depth
introduction to representation theory, we recommend the standard textbook ref.
[61].

Let $\mathbb{G}$ be a finite group and consider the space $\mathcal{M}_{d}$ of
linear transformations of $\mathbb{C}^{d}$. A representation $\omega$ is a map
$\omega:\mathbb{G}\rightarrow\mathcal{M}_{d}$ that preserves the group
multiplication, i.e.,

$\omega(g)\omega(h)=\omega(gh),\;\;\;\;\;\;\forall g,h\in\mathbb{G}.$ (25)

We will require the operators $\omega(g)$ to be unitary as well (for finite
groups this can always be done).

#### Reducible and irreducible representations.

If there is a non-trivial subspace $W$ of $\mathbb{C}^{d}$ such that for all
vectors $w\in W$ we have

$\omega(g)w\in W,\;\;\;\;\;\;\forall g\in\mathbb{G},$ (26)

then the representation $\omega$ is called _reducible_. The restriction of
$\omega$ to the subspace $W$ is also a representation, which we call a _sub-
representation_ of $\omega$. If there are no non-trivial subspaces $W$ such
that eq. 26 holds the representation $\omega$ is called _irreducible_. We will
generally reserve the letter $\sigma$ to denote irreducible representations.
Two representations $\omega,\omega^{\prime}$ of a group $\mathbb{G}$ are
called _equivalent_ if there exists an invertible linear map $T$ such that

$T\omega(g)=\omega^{\prime}(g)T,\;\;\;\;\;\;\;\forall g\in\mathbb{G}.$ (27)

We will denote this by $\omega\simeq\omega^{\prime}$.

#### Sums, products, and Maschke’s Lemma.

We will make use of sums and products of representations. Given
representations $\omega,\omega^{\prime}$, the maps

$\displaystyle\omega\oplus\omega^{\prime}:\mathbb{G}\to\mathcal{M}_{d}\oplus\mathcal{M}_{d^{\prime}}:g\mapsto\omega(g)\oplus\omega^{\prime}(g),$
(28)
$\displaystyle\omega\otimes\omega^{\prime}:\mathbb{G}\to\mathcal{M}_{d}\otimes\mathcal{M}_{d^{\prime}}:g\mapsto\omega(g)\otimes\omega^{\prime}(g),$
(29)

are again representations. They are, however, generally not irreducible (even
if $\omega$ and $\omega^{\prime}$ are). However, Maschke’s Lemma ensures that
every representation $\omega$ of a group can be uniquely written as a direct
sum of irreducible representations, that is

$\omega(g)\simeq\bigoplus_{\lambda\in S}\sigma_{\lambda}(g)^{\oplus
n_{\lambda}},\;\;\;\;\;\;\forall g\in\mathbb{G},$ (30)

where the index set $S$ labels a subset of the irreducible representations of
$\mathbb{G}$ and $n_{\lambda}$ is an integer denoting the number of copies (or
multiplicity) of $\sigma_{\lambda}$ present in $\omega$.

#### Averages of representations.

Here we recall some standard results about averages over representations of
finite groups. We will present these without proof, referring again to ref.
[61] for a more detailed explanation. First is the basic statement that the
average over any representation of a finite group is a projector (precisely
onto the subspace on which the representation acts trivially):

######  Lemma .

Let $\omega$ be a representation of a group $\mathbb{G}$ then

$\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}\omega(g)=P_{\rm
inv}$ (31)

where $P_{\rm inv}$ is the projector onto the subspace left invariant under
the action of $\omega(g)$, i.e., all vectors $v$ s.t. $\omega(g)v=v$ for all
$g\in\mathbb{G}$.

Second is a useful statement about the invariant subspaces of two-fold tensor
powers of representations.

######  Lemma .

Let $\sigma,\sigma^{\prime}$ be real, irreducible, inequivalent, and non-
trivial representations of a finite group $\mathbb{G}$. Then the
representation $\sigma\otimes\sigma^{\prime}$ has no invariant subspace, while
the representation $\sigma^{\otimes 2}$ leaves the vector $v(P_{\sigma})$
invariant, where $v(P_{\sigma})$ is the vectorized projector onto the image of
$\sigma$.

#### Representation theory of the Clifford group.

Here we give some basic facts about the representation theory of the Clifford
group, which are used in the main text to derive the decay models for the
multi-qubit and local Clifford UIRS protocols.

######  Lemma .

The Liouville representation of the $n$-qubit Clifford group $\mathbb{C}_{n}$
decomposes into two irreducible representations, in particular we have for all
$g\in\mathbb{C}_{n}$:

$\omega(g)=\omega_{\rm triv}(g)\oplus\omega_{\rm ad}(g)$ (32)

where $\omega_{\rm triv}(g)$ has support on $\mathrm{Span}\\{\tau_{0}\\}$ and
$\omega_{\rm ad}(g)$ has support on the space of traceless matrices spanned by
all normalized traceless Hermitian Pauli operators $\tau\in\mathbb{P}^{*}_{0}$
.

This is a direct consequence of the $2$-design property of the Clifford group.
An early proof can be found in ref. [44]. A direct consequence is the
following.

######  Lemma .

Let $\omega$ be the Liouville representation of the $n$-qubit Clifford group.
Then we have

$\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\omega(g)^{\otimes
2}=|{\tau_{0}^{\otimes
2}}{\rangle\\!\rangle}{\langle\\!\langle}{\tau_{0}^{\otimes
2}}|+\frac{1}{2^{2n}-1}\sum_{\tau,\tau^{\prime}\in\mathbb{P}^{*}_{0}}|{\tau^{\otimes
2}}{\rangle\\!\rangle}\\!{\langle\\!\langle}{{\tau^{\prime}}^{\otimes 2}}|.$
(33)

We have similar statements for the local Clifford group.

######  Lemma .

The Liouville representation of the local Clifford group
$\mathbb{C}_{1}^{\times n}$ on $n$ qubits decomposes into $2^{n}$ mutually
inequivalent irreducible representations

$\omega(g)=\bigoplus_{w\in\\{0,1\\}^{n}}\sigma_{w}(g)$ (34)

where $\sigma_{w}(g)$ has support on $\mathrm{Span}\\{\mathbb{P}^{*}_{w}\\}$
with

$\mathbb{P}_{w}=\Big{\\{}\bigotimes_{i=1}^{n}\tau_{i}\;\;\;\|\;\;\;\tau_{i}=\tau_{0}\text{
if }\;w_{i}=0\text{ and }\tau_{i}\in\\{\tau_{X},\tau_{Y},\tau_{Z}\\}\text{ if
}\;w_{i}=1\Big{\\}}.$ (35)

This is a direct result of the previous lemmas, applied to each of the $n$
qubits individually. We also have the following statement.

######  Lemma .

Let $\omega$ be the Liouville representation of the local Clifford group on
$n$ qubits. Then we have

$\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{1}^{\times
n}}\omega(g)^{\otimes
2}=\sum_{w\in\\{0,1\\}^{n}}\frac{1}{3^{|w|}}\bigg{(}\sum_{\tau\in\mathbb{P}^{*}_{w}}|{\tau^{\otimes
2}}{\rangle\\!\rangle}\bigg{)}\bigg{(}\sum_{\tau^{\prime}\in\mathbb{P}^{*}_{w}}{\langle\\!\langle}{{\tau^{\prime}}^{\otimes
2}}|\bigg{)},$ (36)

where again

$\mathbb{P}^{*}_{w}=\Big{\\{}\bigotimes_{i=1}^{n}\tau_{i}\;\;\;\|\;\;\;\tau_{i}=\tau_{0}\text{
if }\;w_{i}=0\text{ and }\tau_{i}\in\\{\tau_{X},\tau_{Y},\tau_{Z}\\}\text{ if
}\;w_{i}=1\Big{\\}}.$ (37)

##  VIII Simultaneously estimating many observables

Key to the results in this work is the following general statistics
observation, which also powers state shadow estimation [16]. Let $p$ be a
probability distribution over some (finite) set $\mathcal{X}$, and let
$\mathcal{A}$ be a set of observables, i.e., functions
$f:\mathcal{X}\to\mathbb{R}$. Suppose we wish to estimate the vector of means
$[\mathbb{E}_{\mathcal{X}}(f_{A})]_{A\in\mathcal{A}}$ to some overall error
$\epsilon$. A surprising fact from mathematical statistics is that this is
possible by drawing only $O(\log(|\mathcal{A}|)\mathbb{V}_{\rm
max}(f_{A})/\epsilon^{2})$ samples from $p$ where $\mathbb{V}_{\rm
max}(f_{A})=\max_{A\in\mathcal{A}}\mathbb{V}_{X}(f_{A})$ is the maximal
variance of the functions in $\mathcal{A}$. Doing this (without making strong
assumptions on the observables $f_{A}$) requires the construction of so-called
sub-Gaussian estimators (see refs. [62, 63, 64] for reviews) for the means
$\mathbb{E}_{\mathcal{X}}(f_{A})$. An example of such an estimator that is
straightforward to compute is the _median-of-means estimator_ , which has been
used in state shadow estimation by ref. [16]. Following their notation, it
involves gathering $S=NK$ samples $\\{x_{i}\\}_{i=1}^{NK}$ from the
distribution $p$, where $N,K$ are integers. For an observable $f_{A}$, one can
then construct the estimator

$\hat{f}_{A}=\\!\text{Median}\bigg{\\{}\\!\frac{1}{N}\\!\\!\\!\sum_{i=I}^{I+N-1}\\!\\!\\!\\!f_{A}(x_{i})\;\|\;I\in\\{1,\\!N+1,\\!2N+1,\ldots,\\!(K-1)N+1\\}\\!\bigg{\\}}$
(38)

for the average $\mathbb{E}(f_{A})$, splitting the data into $K$ equally sized
parts of size $N$. It can be shown that if we set

$\displaystyle K$
$\displaystyle=\big{\lceil}2\log(2|\mathcal{A}|/\delta)\big{\rceil},$ (39)
$\displaystyle N$
$\displaystyle=\bigg{\lceil}\frac{34}{\epsilon^{2}}\mathbb{V}_{\rm
max}(f_{A})\bigg{\rceil},$ (40)

then we have

$\max_{A\in\mathcal{A}}|\hat{f_{A}}-\mathbb{E}(f_{A})|\leq\epsilon,$ (41)

with probability $1-\delta$. We can substitute $\epsilon$ to obtain the direct
relation

$\max_{A\in\mathcal{A}}|\hat{f_{A}}-\mathbb{E}(f_{A})|\leq\sqrt{\frac{68\mathbb{V}_{\rm
max}(f_{A})\log(2|\mathcal{A}|/\delta)}{NK}},$ (42)

in terms of the total number of samples $NK$. Hence, providing bounds on the
maximal variance of a set of observables provides a rigorous guarantee on
their estimation at any degree of confidence. Note however that the
construction of the estimator is dependent on the level of confidence $\delta$
(through the setting of $K$). This is unfortunate, but it turns out to be
impossible [64] to drop this requirement for sub-Gaussian estimators.

##  IX Guarantees for the UIRS protocol

In this section, we give the derivations of the general performance guarantees
for the UIRS protocol summarized in the main text.

###  IX.1 Fitting model

As we have argued in the main text, a useful class of sequence correlation
functions is given by

$f_{A}(x,\vec{g})=\alpha{\langle\\!\langle}{E_{x}}|\sigma(g_{m})\prod_{i=1}^{m-1}A\sigma(g_{i}))|{\rho}{\rangle\\!\rangle}\,,$
(43)

where $A$ is some fixed _probe super-operator_ , $\alpha$ is a suitable
normalization and $\sigma(g),\phi(g)$ are representations of the gate-set
group $\mathbb{G}$. We begin by deriving the main result (eq. (5) in the main
text) on the mean $k_{A}(m)$ in the UIRS protocol.

######  Theorem 5.

Let $k_{A}(m)$ be the outcome of an UIRS experiment with a correlation
function as in eq. 43, over a gate-set $\mathbb{G}$. Then we have, under the
assumption of gate-independent noise,

$k_{A}(m)=\operatorname{Tr}\big{(}\Theta(\\{E_{x}\\}_{x},\rho)[\Phi(A,\Lambda)]^{m-1}\big{)},$
(44)

where $\Theta,\Phi$ are matrices induced by the representation structure of
$\omega(g)$. $\Phi(A,\Lambda)$ depends only on the between-gates noise channel
$\Lambda:=\Lambda_{R}\Lambda_{L}$ and the probe super-operator $A$, while
$\Theta$ captures state preparation and measurement (SPAM) dependence. In
particular, if $\omega$ contains $n_{\sigma}$ copies of the representation
$\sigma$ then we have

$\Phi_{i,j}=\frac{1}{|P_{j}|}\operatorname{Tr}(P_{i}AP_{j}\Lambda),$ (45)

where $P_{i}$ is the projector onto the $i$th copy of the representation
$\sigma$ inside $\omega$.

The formulation of the result given in the main text directly follows from
theorem 5 by additionally realizing that $f_{A}(x,\mathbf{g})$ regarded as a
random variable pushing forward $p(x,\mathbf{g})$ is bounded and, thus, the
corresponding mean estimator $\hat{k}_{f_{A}}(m)$ is unbiased and consistent.
Correspondingly the median-of-mean estimator converges to the expected value
of the mean.

###### Proof.

Recall that $\phi(g)=\Lambda_{L}\omega(g)\Lambda_{R}$. Hence

$\displaystyle k_{A}(m)$
$\displaystyle=\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{\vec{g}\in\mathbb{G}^{\times
m}}\sum_{x\in\\{0,1\\}^{n}}\alpha{\langle\\!\langle}{E_{x}}|\sigma(g_{m})\prod_{i=1}^{m-1}A\sigma(g_{i}))|{\rho}{\rangle\\!\rangle}{\langle\\!\langle}{\tilde{E}_{x}}|\prod_{i=1}^{m}\Lambda_{L}\omega(g_{i})\Lambda_{R}|{\tilde{\rho}}{\rangle\\!\rangle}$
(46)
$\displaystyle=\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{\vec{g}\in\mathbb{G}^{\times
m}}\sum_{x\in\\{0,1\\}^{n}}\alpha\operatorname{Tr}\bigg{(}\big{(}|{\rho\otimes\Lambda_{R}(\tilde{\rho})}{\rangle\\!\rangle}{\langle\\!\langle}{E_{x}\otimes\Lambda_{L}^{*}(\tilde{E}_{x})}|\big{)}\sigma(g_{m})\otimes\omega(g_{m})\prod_{i=1}^{m-1}\big{(}(A\otimes\Lambda)(\sigma(g_{i})\otimes\omega(g_{i}))\big{)}\bigg{)}$
$\displaystyle=\sum_{x\in\\{0,1\\}^{n}}\alpha\operatorname{Tr}\bigg{[}\big{(}|{\rho\otimes\Lambda_{R}(\tilde{\rho})}{\rangle\\!\rangle}{\langle\\!\langle}{E_{x}\otimes\Lambda_{L}^{*}(\tilde{E}_{x})}|\big{)}\left(\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}(\sigma(g)\otimes\omega(g))(A\otimes\Lambda)\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}(\sigma(g)\otimes\omega(g))\right)^{m-1}\bigg{)}\bigg{]},$

where we have used that the representation average is a projector (and thus
equal to its square). Now note that we can write
$\omega(g)=\sigma^{n_{\sigma}}(g)\oplus\omega^{\prime}(g)$ where
$\omega^{\prime}$ is a representation that contains no copies of $\sigma$.
From this and sections VII and VII given above we can see that

$\displaystyle k_{A}(m)$
$\displaystyle=\sum_{x\in\\{0,1\\}^{n}}\alpha\operatorname{Tr}\bigg{(}\big{(}|{\rho\otimes\Lambda_{R}(\tilde{\rho})}{\rangle\\!\rangle}{\langle\\!\langle}{E_{x}\otimes\Lambda_{L}^{*}(\tilde{E}_{x})}|\big{)}\left(\sum_{i,i^{\prime}=1}^{n_{\sigma}}\frac{1}{d_{\sigma}}|{v(P_{i})}{\rangle\\!\rangle}{\langle\\!\langle}{v(P_{i^{\prime}})}|(A\otimes\Lambda)\sum_{j,j^{\prime}=1}^{n_{\sigma}}|{v(P_{j})}{\rangle\\!\rangle}{\langle\\!\langle}{v(P_{j^{\prime}})}|\right)^{m-1}\bigg{)},$
(47)

where $P_{i}$ is the projector on the $i$’th copy of $\sigma$ in $\omega$.
Using the fact that

${\langle\\!\langle}{v(P)}|A\otimes
B|{v(P^{\prime})}{\rangle\\!\rangle}=\operatorname{Tr}(A^{T}PBP^{\prime}),$
(48)

and defining the matrices $\Theta,\Phi$ appropriately, we obtain the theorem
statement. ∎

###  IX.2 Variance bound with the dynamic shadow norm

In order to bound the sampling complexity of the estimation of UIRS means
$k_{A}(m)$ it is sufficient, through the use of median-of-means estimators, to
obtain a bound on the variance of associated probability distribution. In the
main text we did this by introducing the dynamic shadow norm. The dynamic
shadow norm is formally defined as

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\alpha^{2}\max_{\Lambda_{R},\Lambda_{L}}\bigg{|}\sum_{x\in\mathcal{X}}\\!{\langle\\!\langle}{E_{x}^{\otimes
2}\\!\otimes\\!\Lambda_{L}^{*}(\tilde{E}_{x})}|\big{(}P_{\sigma}^{(2)}(A^{\otimes
2}\\!\otimes\\!I)P_{\sigma}^{(2)}\big{)}^{m\\!-\\!1}|{\rho^{\otimes
2}\\!\otimes\\!\Lambda_{R}(\tilde{\rho})}{\rangle\\!\rangle}\bigg{|},$ (49)

with

$P_{\sigma}^{(2)}=\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}\sigma(g)^{\otimes
2}\otimes\omega(g).$ (50)

We prove the associated theorem:

######  Theorem 6 (Restatement of Theorem 1 in the main text).

Consider an UIRS protocol (at sequence length $m$) with gate-set $\mathbb{G}$.
Also consider a correlation function $f_{A}$ with probe super-operator $A$.
The (single-shot) variance of the associated mean estimator
$\hat{k}_{f_{A}}(m)$ is bounded as

$\mathbb{V}_{A}(m)\leq\left\|A\right\|_{{\rm dyn},m}.$ (51)

###### Proof.

The variance of a discrete random variable $X$ assuming values
$x\in{\mathcal{X}}$ with probability $p(x)$ is given by

$\mathbb{V}(X)=\sum_{x\in\mathcal{X}}(x-\mu)^{2}p(x),$ (52)

with $\mu$ the expected value of $X$. We can therefore obtain an upper bound
on the variance by simply considering

$\mathbb{V}(X)\leq\sum_{x\in\mathcal{X}}(x)^{2}p(x).$ (53)

Thus, we have that

$\displaystyle\mathbb{V}_{A}(m)=\mathbb{V}(X_{A}(m))\leq\alpha^{2}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{\vec{g}\in\mathbb{G}^{\times
m}}\sum_{x\in\mathcal{X}}{\langle\\!\langle}{E_{x}}|\sigma(g_{m})\prod_{i=1}^{m-1}A\sigma(g_{i}))|{\rho}{\rangle\\!\rangle}^{2}{\langle\\!\langle}{\tilde{E}_{x}}|\prod_{i=1}^{m}\phi(g_{i})|{\tilde{\rho}}{\rangle\\!\rangle}.$
(54)

Using the identities $\operatorname{Tr}(A\otimes
B)=\operatorname{Tr}(A)\operatorname{Tr}(B)$ and $AB\otimes AB=A^{\otimes
2}B^{\otimes 2}$ we obtain

$\displaystyle\mathbb{V}_{A}(m)\leq\alpha^{2}\sum_{x\in\mathcal{X}}\operatorname{Tr}\bigg{(}\big{(}|{\rho^{\otimes
2}\otimes\Lambda_{R}(\tilde{\rho})}{\rangle\\!\rangle}{\langle\\!\langle}{E_{x}^{\otimes
2}\otimes\Lambda_{L}^{*}(\tilde{E}_{x})}|\big{)}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}\sigma(g)^{\otimes
2}\otimes\omega(g)\bigg{(}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}(A\sigma(g))^{\otimes
2}\otimes(\Lambda\omega(g))\bigg{)}^{m-1}\bigg{)}.$ (55)

Maximizing over $\Lambda_{R},\Lambda_{L}$ and recalling the definition

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle:=\alpha^{2}\max_{\Lambda_{R},\Lambda_{L}}\bigg{|}\sum_{x\in\mathcal{X}}\\!{\langle\\!\langle}{E_{x}^{\otimes
2}\\!\otimes\\!\Lambda_{L}^{*}(\tilde{E}_{x})}|\big{(}P_{\sigma}^{(2)}(A^{\otimes
2}\\!\otimes\\!\Lambda)P_{\sigma}^{(2)}\big{)}^{m\\!-\\!1}|{\rho^{\otimes
2}\\!\otimes\\!\Lambda_{R}(\tilde{\rho})}{\rangle\\!\rangle}\bigg{|},$ (56)

of the shadow norm completes the argument.

∎

##  X Shadow norm bound for local Clifford UIRS

In this section, we consider the UIRS protocol with the local Clifford group
$\mathbb{C}_{1}^{\times n}$. We will model the noisy implementation of any
given Clifford by $\Lambda_{L}\omega(g)\Lambda_{R}$ and we will denote
$\Lambda_{R}\Lambda_{L}=:\Lambda$ for brevity. In the main text we stated the
following theorem:

######  Theorem 7 (Restatement of Theorem 4 in the main text).

Consider the local Clifford UIRS protocol. Let
$\phi(g)=\Lambda_{L}\omega(g)\Lambda_{R}$ be a noisy implementation of the
local Clifford group on $n$ qubits and $A=P_{w}AP_{w}$ be a probe super-
operator with $|w|=k$ for $k$ a fixed integer. Also let $\tilde{0}_{n}$ be a
noisy implementation of the all-zero state and $\\{\tilde{x}\\}_{x}$ the noisy
computational basis POVM). The shadow norm of the random variable $X_{A}(m)$
is upper bounded independently of the number of qubits $n$ and sequence length
$m$. In particular, it holds that

$\left\|A\right\|_{{\rm dyn},m}\leq
2^{k}3^{2k}\big{(}3^{-k}\operatorname{Tr}(AA{}^{\dagger})\big{)}^{m-1}.$ (57)

###### Proof.

We begin from the general expression of the shadow norm, which can be written
as

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}3^{2k}2^{2n}\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\\!\\!{\langle\\!\langle}{x^{\otimes
2}\otimes\tilde{x}}|(\mathbb{I}^{\otimes
2}\otimes\Lambda_{L})\left[\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g_{[1,n]}}\omega(g_{[1,n]})^{\otimes
3}(A^{\otimes
2}\otimes\Lambda)\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g^{\prime}_{[1,n]}}\omega(g^{\prime}_{[1,n]})^{\otimes
3}\right]^{m}\\!\\!\\!\\!(\mathbb{I}^{\otimes
2}\otimes\Lambda_{R})|{0_{n}^{\otimes
2}\otimes\tilde{0}_{n}}{\rangle\\!\rangle}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}3^{2k}2^{2n}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g^{(1)}_{[1,n]},\ldots,g^{(m)}_{[1,n]}}\sum_{x\in\\{0,1\\}^{n}}{\langle\\!\langle}{x^{\otimes
2}}|\omega(g^{(m)}_{[1,n]})^{\otimes 2}\prod_{i=1}^{m-1}\\!\big{(}A^{\otimes
2}\omega(g^{(i)}_{[1,n]})^{\otimes 2}\big{)}|{0_{n}^{\otimes
2}}{\rangle\\!\rangle}$ $\displaystyle\hskip
300.00046pt\times{\langle\\!\langle}{\tilde{x}}|\Lambda_{L}\omega(g^{(m)}_{[1,n]})\prod_{i=1}^{m-1}\\!\big{(}\Lambda\omega(g^{(i)}_{[1,n]})\big{)}\Lambda_{R}|{\tilde{0}_{n}}{\rangle\\!\rangle},$

where $\\{{\langle\\!\langle}{\tilde{x}}|\\}_{x}$ and
$|{\tilde{0}_{n}}{\rangle\\!\rangle}$ are the noisy measurement POVM and the
noisy initial state, respectively.

We now make use of the fact that $A$ is assumed to be supported on only a
single irreducible representation denoted by $k\in\\{0,1\\}^{n}$ i.e.,
$A=P_{k}AP_{k}$ where $P_{k}$ is the projector onto that irreducible
representation. Without loss of generality we will here set $k$ to be the all
$1$ bit string on the first $k$ bits and $0$ on the remaining $n-k$ bits. The
projector $P_{w}$ acts as
$|{\tau_{0}}{\rangle\\!\rangle}{\langle\\!\langle}{\tau_{0}}|$ on these last
$n-k$ qubits. Since

$\omega(g)|{\tau_{0}}{\rangle\\!\rangle}=|{\tau_{0}}{\rangle\\!\rangle},$ (58)

we see that in ${\langle\\!\langle}{x^{\otimes
2}}|\omega(g^{(m)}_{[1,n]})^{\otimes 2}\prod_{i=1}^{m-1}\big{(}A^{\otimes
2}\omega(g^{(i)}_{[1,n]})^{\otimes 2}\big{)}|{0_{n}^{\otimes
2}}{\rangle\\!\rangle}$ we can absorb the action of the local Clifford group
on the last $n-k$ qubits. Hence, the local Cliffords $g^{(i)}_{[k+1,n]}$ only
act by a single conjugation, i.e.,

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}3^{2k}2^{2n}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g^{(1)}_{[1,n]},\ldots,g^{(m)}_{[1,n]}}\sum_{x\in\\{0,1\\}^{n}}{\langle\\!\langle}{x^{\otimes
2}}|\omega(g^{(m)}_{[1,k]})^{\otimes 2}\prod_{i=1}^{m-1}\big{(}A^{\otimes
2})\omega(g^{(i)}_{[1,k]})^{\otimes 2}\big{)}|{0_{n}^{\otimes
2}}{\rangle\\!\rangle}$ $\displaystyle\hskip
100.00015pt\times{\langle\\!\langle}{\Lambda_{L}^{*}(\tilde{x})}|\omega(g^{(m)}_{[1,k]})\otimes\omega(g^{(m)}_{[k+1,n]})\prod_{i=1}^{m-1}\big{(}\Lambda\omega(g^{(i)}_{[1,k]})\omega(g^{(i)}_{[k+1,n]})\big{)}|{\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle}$
$\displaystyle\hskip 120.00018pt\times\big{[}\langle\\!\langle
x_{[k+1,n]}|{\tau_{0}}_{[k+1,n]}\rangle\\!\rangle\langle\\!\langle{\tau_{0}}_{[k+1,n]}|{0_{n}}_{[k+1,n]}\rangle\\!\rangle\big{]}^{2}.$
(59)

Now we use the fact that

$\langle\\!\langle
x_{[k+1,n]}|{\tau_{0}}_{[k+1,n]}\rangle\\!\rangle=2^{(k-n)/2},\
\;\;\;\;\;x_{[k+1,n]}\in\\{0,1\\}^{n-k},$ (60)

and

$\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g_{[k+1,n]}}\omega(g_{[k+1,n]})=|{{\tau_{0}}_{[k+1,n]}}{\rangle\\!\rangle}{\langle\\!\langle}{{\tau_{0}}_{[k+1,n]}}|,$
(61)

we end up with

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}3^{2k}2^{2k}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g^{(1)}_{[1,k]},\ldots,g^{(m)}_{[1,k]}}\sum_{x_{[1,k]}\in\\{0,1\\}^{k}}{\langle\\!\langle}{x^{\otimes
2}_{[1,k]}}|\omega(g^{(m)}_{[1,k]})^{\otimes
2}\prod_{i=1}^{m-1}\big{(}A^{\otimes 2}\omega(g^{(i)}_{[1,k]})^{\otimes
2}\big{)}|{0_{k}^{\otimes 2}}{\rangle\\!\rangle}$ (62) $\displaystyle\hskip
100.00015pt\times\\!\\!\\!\\!\\!\sum_{x_{[k+1,n]}\in\\{0,1\\}^{n-k}}\\!\\!\\!\\!\\!\\!\\!2^{k-n}{\langle\\!\langle}{\operatorname{Tr}_{k+1,n}(\Lambda_{L}^{*}(\tilde{x}))}|\omega(g^{(m)}_{[1,k]})\prod_{i=1}^{m-1}\big{(}\Lambda\omega(g^{(i)}_{[1,k]})\big{)}|{\operatorname{Tr}_{k+1,n}(\Lambda_{R}(\tilde{0}_{n}))}{\rangle\\!\rangle}.$

Obviously
$|{\tilde{\rho}_{k}}{\rangle\\!\rangle}:=|{\operatorname{Tr}_{k+1,n}(\Lambda_{R}(\tilde{0}_{n}))}{\rangle\\!\rangle}$
is a $k$-qubit state and, moreover, we have

$\displaystyle\sum_{x_{[1,k]}\in\\{0,1\\}^{k}}\tilde{E}_{x_{[1,k]}}$
$\displaystyle:=\sum_{x_{[1,k]}\in\\{0,1\\}^{k}}\bigg{(}2^{k-n}\sum_{x_{[k+1,n]}\in\\{0,1\\}^{n-k}}\operatorname{Tr}_{k+1,n}(\Lambda_{L}^{*}(\tilde{x}))\bigg{)}$
(63)
$\displaystyle=2^{k-n}\sum_{x\in\\{0,1\\}^{n}}\operatorname{Tr}_{k+1,n}(\Lambda_{L}^{*}(\tilde{x}))$
$\displaystyle=2^{k-n}\operatorname{Tr}_{k+1,n}(\Lambda_{L}^{*}(\mathbb{I}))$
$\displaystyle=2^{k-n}\operatorname{Tr}_{k+1,n}(\mathbb{I})=\mathbb{I}_{[1,k]},$

which makes $\\{\tilde{E}_{x_{[1,k]}}\\}_{{x_{[1,k]}}}$ a $k$-qubit POVM.
Hence, we have

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}3^{2k}2^{2k}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g^{(1)}_{[1,k]},\ldots,g^{(m)}_{[1,k]}}\sum_{x_{[1,k]}\in\\{0,1\\}^{k}}{\langle\\!\langle}{x^{\otimes
2}_{[1,k]}}|\omega(g^{(m)}_{[1,k]})^{\otimes
2}\prod_{i=1}^{m-1}\big{(}A^{\otimes 2}\omega(g^{(i)}_{[1,k]})^{\otimes
2}\big{)}|{0_{k}^{\otimes 2}}{\rangle\\!\rangle}$ $\displaystyle\hskip
100.00015pt\times{\langle\\!\langle}{\tilde{E}_{x_{[1,k]}}}|\omega(g^{(m)}_{[1,k]})\prod_{i=1}^{m-1}\big{(}\Lambda_{k}\omega(g^{(i)}_{[1,k]})\big{)}|{\tilde{\rho}_{k}}{\rangle\\!\rangle},$
(64)

where $\Lambda_{k}$ is the $k$-qubit marginal of $\Lambda$. At this point, we
see that the shadow norm is bounded independently of the number of qubits $n$
and only depends on the dimension of the irreducible representation which we
assume $A$ to have support on (it is a function of $k$ only). As we can see,
we are left with a third moment calculation over $\mathbb{C}_{1}^{\times k}$.
However, for the sake of obtaining an upper bound we simply note that

${\langle\\!\langle}{\tilde{E}_{x_{[1,k]}}}|\omega(g^{(m)}_{[1,k]})\prod_{i=1}^{m-1}\big{(}\Lambda_{k}\omega(g^{(i)}_{[1,k]})\big{)}|{\tilde{\rho}_{k}}{\rangle\\!\rangle}\in[0,1],$
(65)

since $\Lambda_{k}$ is a quantum channel. We, therefore, can (using the
invariance of the Haar measure) simplify the bound to

$\left\|A\right\|_{{\rm dyn},m}\leq
3^{2k}2^{3k}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g_{[1,k]}}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g^{\prime}_{[1,k]}}{\langle\\!\langle}{0_{[1,k]}^{\otimes
2}}|\left[\omega(g_{[1,k]})^{\otimes 2}A^{\otimes
2}\omega(g^{\prime}_{[1,k]})^{\otimes 2}\right]^{m-1}|{0_{[1,k]}^{\otimes
2}}{\rangle\\!\rangle}.$ (66)

Again using the fact that $A$ is taken to only have overlap with a single
irreducible representation, section VII and the fact that $\langle\\!\langle
0|\tau_{i}\rangle\\!\rangle=1/\sqrt{2}$ if and only if $\tau_{i}=\tau_{0}$ or
$\tau_{Z}$ (and zero otherwise) we have

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$ $\displaystyle\leq
3^{2k}2^{3k}\left[\frac{\operatorname{Tr}(AA^{\dagger})}{3^{k}}\right]^{m-1}\langle\\!\langle
0^{\otimes 2k}|\tau_{Z}^{\otimes 2k}\rangle\\!\rangle^{2}$ (67)
$\displaystyle=3^{2k}2^{k}\left[\frac{\operatorname{Tr}(AA^{\dagger})}{3^{k}}\right]^{m-1},$

which is what we set out to prove. ∎

##  XI Shadow norm bound for multi-qubit Clifford UIRS

In this section, we will go into the details of the shadow norm bound
calculations for the multi-qubit Clifford group UIRS protocol. Concretely, we
prove the following theorem.

######  Theorem 8 (Restatement of Theorem 3 in the main text).

Consider the $n$-qubit Clifford UIRS protocol and let $A=P_{\rm ad}AP_{\rm
ad}$ be a probe super-operator restricted to the traceless subspace. Also let
$\tilde{0}_{n}$ be a noisy implementation of the all-zero state and
$\\{\tilde{x}\\}_{x\in\\{0,1\\}^{n}}$ the noisy computational basis POVM). The
associated shadow norm is upper bounded as

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$ $\displaystyle\leq
11\,u(A)\bigg{(}r(A)^{m-2}+\big{[}2(m-2)^{2}r(A)^{m-3}\big{]}\max\big{\\{}11u(A),(11\,u(A))^{2}\big{\\}}\\!\bigg{)},$
(68)

with

$r(A)=u(A)(1+16\,2^{-n/3}),$ (69)

and where $u(A)=\operatorname{Tr}(AA{}^{\dagger})/(2^{2n}-1)$ is the unitarity
of $A$.

Restricting to $m>0$ and using that $r(A)\geq u(A)$ yields the simplified
statement in the main text.

###### Proof.

Recall that the dynamic shadow norm for the multi-qubit Clifford group is
given by

$\displaystyle\left\|A\right\|_{{\rm
dyn},m}=\max_{\Lambda_{R},\Lambda_{L}}(2^{n}+1)^{2}\\!\\!\\!\\!\\!\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\\!\\!\operatorname{Tr}\\!\bigg{[}$
$\displaystyle|{0_{n}^{\otimes
2}\otimes\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle}\\!{\langle\\!\langle}{x^{\otimes
2}\otimes\Lambda_{L}^{*}(\tilde{x})}|\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}\sigma_{\rm
ad}(g)^{\otimes
2}\otimes\omega(g)\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{G}}(A\sigma_{\rm
ad}(g))^{\otimes
2}\\!\otimes\\!(\Lambda\omega(g))\bigg{]}^{m\\!-\\!1}\bigg{]},$ (70)

where $\Lambda:=\Lambda_{R}\Lambda_{L}$ is the noise in-between subsequent
gates. We can provide a concrete resolution for the third moment by noting
that $\mathbb{C}_{n}$ is a $3$-design [65], and, hence, its third moment
follows that of the unitary group $U(2^{n})$, which is fully determined (for
$n\geq 2$) by Schur-Weyl duality. In particular, we have

$\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{c\in\mathbb{C}_{n}}\sigma_{\rm
ad}(c)^{\otimes 2}\otimes\omega(c)=P_{\rm ad}^{\otimes
2}\otimes\mathbb{I}\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{c\in\mathbb{C}_{n}}\omega(c)^{\otimes
3}\bigg{]}P_{\rm ad}^{\otimes 2}\otimes\mathbb{I}=\sum_{\pi,\pi^{\prime}\in
S_{3}}W_{\pi,\pi^{\prime}}(P_{\rm ad}^{\otimes
2}\otimes\mathbb{I})|{\pi}{\rangle\\!\rangle}{\langle\\!\langle}{\pi^{\prime}}|(P_{\rm
ad}^{\otimes 2}\otimes\mathbb{I}),$ (71)

where the matrices $\pi$ permute copies of the base Hilbert space, i.e.,

$\pi\ket{i_{1},i_{2},i_{3}}=\ket{i_{\pi(1)},i_{\pi(2)},i_{\pi(3)}}.$ (72)

The Weingarten matrix

$W=\frac{1}{2^{n}(2^{2n}-1)(2^{2n}-4)}\begin{pmatrix}2^{2n}-2&-2^{n}&-2^{n}&-2^{n}&2&2\\\
-2^{n}&2^{2n}-2&2&2&-2^{n}&-2^{n}\\\ -2^{n}&2&2^{2n}-2&2&-2^{n}&-2^{n}\\\
-2^{n}&2&2&2^{2n}-2&-2^{n}&-2^{n}\\\ 2&-2^{n}&-2^{n}&-2^{n}&2^{2n}-2&2\\\
2&-2^{n}&-2^{n}&-2^{n}&2&2^{2n}-2\\\ \end{pmatrix}$ (73)

can be explicitly written down in the basis
$\\{e,(12),(23),(13),(123),(132)\\}$. Now defining the matrices

$\Omega_{\pi^{\prime},\pi}={\langle\\!\langle}{\pi^{\prime}}|A^{\otimes
2}\otimes\Lambda|{\pi}{\rangle\\!\rangle},$ (74)

and

$[{\Theta_{x}}]_{\pi,\pi^{\prime}}=(2^{n}+1)^{2}\langle\\!\langle\pi|0_{n}^{\otimes
2}\otimes\Lambda_{R}(\tilde{0}_{n})\rangle\\!\rangle\\!\langle\\!\langle
x^{\otimes 2}\otimes\Lambda_{L}^{*}(\tilde{x})|\pi^{\prime}\rangle\\!\rangle,$
(75)

we get

$\left\|A\right\|_{{\rm
dyn},m}=\max_{\Lambda_{R},\Lambda_{L}}\sum_{x\in\\{0,1\\}^{n}}\operatorname{Tr}(\Theta_{x}(W\Omega)^{m-1}W).$
(76)

We begin by analyzing the matrix $\Omega$. Note that
$A(\mathbb{I})=A{}^{\dagger}(\mathbb{I})=0$, since $A$ is supported only on
the space of traceless matrices by construction. This means that
$\Omega_{\pi,\pi^{\prime}}$ is zero unless
$\pi,\pi^{\prime}\in\\{(12),(123),(132)\\}$. Thus we can write
$\Omega=P{}^{\dagger}\hat{\Omega}P$ with $P$ the restriction from
$\text{Span}\\{e,(12),(23),(13),(123),(132)\\}$ to
$\text{Span}\\{(12),(123),(132)\\}$ and

$\hat{\Omega}=\begin{pmatrix}2^{n}\operatorname{Tr}(AA{}^{\dagger})&\operatorname{Tr}(AA{}^{\dagger})&\operatorname{Tr}(AA{}^{\dagger})\\\
\operatorname{Tr}(J_{u}(A)^{2}\mathbb{I}\otimes\Lambda(\mathbb{I}))&\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))&\operatorname{Tr}(J_{u}(AT)^{2}J_{u}(\Lambda
T))\\\
\operatorname{Tr}(J_{u}(A)^{2}\mathbb{I}\otimes\Lambda(\mathbb{I}))&\operatorname{Tr}(J_{u}(TA)^{2}J_{u}(T\Lambda))&\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))\end{pmatrix},$
(77)

where we have used $\Lambda{}^{\dagger}(\mathbb{I})=\mathbb{I}$, $J_{u}$
denotes the unnormalized Choi-isomorphism ($J_{u}(A)=\mathbb{I}\otimes
A(\ket{v(\mathbb{I})}\bra{v(\mathbb{I})}$ with $v$ the column-stacking
vectorization map) and $T$ is the (non-CP) transposition map. This can be
derived directly from the definition of $\Omega$ and some diagram chasing.
Before we continue, we establish some facts about the entries of
$\hat{\Omega}$. We begin by noting that for the off-diagonal term
$\hat{\Omega}_{(123),(132)}$, we have

$\operatorname{Tr}(J_{u}(AT)^{2}J_{u}(\Lambda
T))=\operatorname{Tr}(J_{u}(TA)^{2}J_{u}(T\Lambda))=\operatorname{Tr}(J_{u}(A{}^{\dagger}T)^{2}J_{u}(\Lambda{}^{\dagger}T)).$
(78)

This follows from three facts: (1) $A^{\otimes 2}$ commutes with the super-
operator $L_{(12)}$ defined as left-multiplication with the matrix $(12)$, (2)
$L_{(12)}((123))=(132)$ and (3) the trace is invariant under Hermitian
conjugation. One can also see this graphically through the following series of
tensor manipulations: as

where we have used that the Liouville representation of a dual super-operator
$\Lambda{}^{\dagger}$ is given by the transpose of the Liouville
representation of $\Lambda$. For clarity we marked for clarity one of the
copies of $A$ with a dot. The rightmost side of eq. 78 is amenable to a bound
of the form

$\displaystyle|\operatorname{Tr}(J_{u}(A{}^{\dagger}T)^{2}J(\Lambda{}^{\dagger}T))|$
$\displaystyle\leq\operatorname{Tr}(J_{u}(A{}^{\dagger}T)^{2})\left\|J_{u}(\Lambda{}^{\dagger}T)\right\|_{\infty}$
(79)
$\displaystyle=\operatorname{Tr}(AA{}^{\dagger})\left\|J_{u}(\Lambda{}^{\dagger}T)\right\|_{\infty}$
$\displaystyle=\operatorname{Tr}(AA{}^{\dagger})\max_{\left\|Q\right\|_{1}=1}|\operatorname{Tr}(Q\,\mathbb{I}\otimes\Lambda{}^{\dagger}(\ket{v(\mathbb{I})}\bra{v(\mathbb{I})}^{T_{B}}))|$
$\displaystyle=\operatorname{Tr}(AA{}^{\dagger})\max_{\left\|Q\right\|_{1}=1}|\operatorname{Tr}(\mathbb{I}\otimes\Lambda(Q)(\ket{v(\mathbb{I})}\bra{v(\mathbb{I})}^{T_{B}}))|$
$\displaystyle\leq\operatorname{Tr}(AA{}^{\dagger})\left\|(\ket{v(\mathbb{I})}\bra{v(\mathbb{I})}^{T_{B}})\right\|_{\infty}$
$\displaystyle\leq\operatorname{Tr}(AA{}^{\dagger}),$

where we have used Hölders inequality twice, the fact that $A$ is Hermiticity
preserving, and the fact that $\Lambda$ is $1\to 1$-norm contractive (by grace
of being CPTP). Finally the Schatten $\infty$-norm of
$(\ket{v(\mathbb{I})}\bra{v(\mathbb{I})}^{T_{B}})$ is easily seen to be one.
Furthermore, for the diagonal elements
$\hat{\Omega}_{(123),(123)}=\hat{\Omega}_{(132),(132)}$, we have

$\displaystyle\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))$
$\displaystyle\leq\operatorname{Tr}(AA{}^{\dagger})\left\|J_{u}(\Lambda)\right\|_{\infty}\leq
2^{n}\operatorname{Tr}(AA{}^{\dagger})$ (80)

again using Hölder’s inequality and
$\left\|J_{u}(\Lambda)\right\|_{\infty}\leq 2^{n}$ (note again that $J_{u}$ is
unnormalized). Finally, we consider the other off-diagonal term
$\hat{\Omega}_{(123),(12)}=\hat{\Omega}_{(132),(12)}$. If $\Lambda$ is unital
(and thus $\Lambda(\mathbb{I})=\mathbb{I}$ ), we see that
$\hat{\Omega}_{(123),(12)}=\operatorname{Tr}(AA{}^{\dagger})$, and in general
we have

$\operatorname{Tr}(J_{u}(A)^{2}\mathbb{I}\otimes\Lambda(\mathbb{I}))\leq\operatorname{Tr}(AA{}^{\dagger})\left\|\mathbb{I}\otimes\Lambda(\mathbb{I})\right\|_{\infty}\leq
2^{n}\operatorname{Tr}(AA{}^{\dagger}).$ (81)

Note that if $\Lambda$ is unital the matrix $\hat{\Omega}$ is symmetric,
however, for general channels this is not the case.

With these expressions we can move on to calculate the dynamic shadow norm

$\left\|A\right\|_{{\rm
dyn},m}=\max_{\Lambda_{R},\Lambda_{L}}\sum_{x\in\\{0,1\\}^{n}}\operatorname{Tr}(\Theta_{x}(W\Omega)^{m-1}W)\leq\left\|\hat{\Omega}PW\big{(}\sum_{x\in\\{0,1\\}^{n}}\Theta_{x}\big{)}WP{}^{\dagger}\right\|_{\infty}\left\|\hat{\Omega}\hat{W}^{m-2}\right\|_{\infty},$
(82)

where $\hat{W}=PWP{}^{\dagger}$ and the norm is the standard operator (or
Schatten $\infty-$) norm. To bound the norm-of-power factor (the ‘dynamic’
part of the shadow norm) in the above equation we need two useful lemmas about
small non-normal matrices.

######  Lemma .

Let $A,B$ be complex $d\times d$ matrices with spectral radius $s(A),s(B)$. We
have that

$|s(A)-s(B)|\leq(\left\|A\right\|_{\infty}+\left\|B\right\|_{\infty})^{1-1/d}\left\|A-B\right\|_{\infty}^{1/d}.$
(83)

######  Lemma .

Let $A$ be a complex $d\times d$ matrix with spectral radius $s(A)$. We have
that

$\left\|A^{m}\right\|_{\infty}\leq
s(A)^{m}+(d-1)m^{d-1}\max\big{\\{}s(A)^{m-d+1},s(A)^{m-1}\big{\\}}\max\big{\\{}2\left\|A\right\|_{\infty},(2\left\|A\right\|_{\infty})^{d-1}\big{\\}}.$
(84)

Section XI is a trivial consequence of ref. [66, Thm VIII.1.1], and we will
prove section XI in at the end of this section. Next, we define matrices

$\hat{\Omega}^{0}=\begin{pmatrix}2^{n}\operatorname{Tr}(AA{}^{\dagger})&0&0\\\
\operatorname{Tr}(J_{u}(A)^{2}\mathbb{I}\otimes\Lambda(\mathbb{I}))&\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))&\operatorname{Tr}(J_{u}(AT)^{2}J_{u}(\Lambda
T))\\\
\operatorname{Tr}(J_{u}(A)^{2}\mathbb{I}\otimes\Lambda(\mathbb{I}))&\operatorname{Tr}(J_{u}(TA)^{2}J_{u}(T\Lambda))&\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))\end{pmatrix},\;\;\;\;\;\hat{D}=\frac{2^{2n}-2}{2^{n}(2^{2n}-1)(2^{2n}-4)}\mathbb{I}.$
(85)

We have

$\hat{\Omega}^{0}\hat{D}=\hat{\Omega}\hat{W}+(\hat{\Omega}^{0}-\hat{\Omega})\hat{D}+\hat{\Omega}(\hat{D}-\hat{W}).$
(86)

We can directly calculate the spectrum of $\hat{\Omega}^{0}\hat{D}$ as being

$\displaystyle\mathrm{Spec}(\hat{\Omega}^{0}\hat{D})=$
$\displaystyle\bigg{\\{}\frac{2^{n}(2^{2n}-2)\operatorname{Tr}(AA{}^{\dagger})}{2^{n}(2^{2n}-1)(2^{2n}-4)},\frac{(2^{2n}-2)}{2^{n}(2^{2n}-1)(2^{2n}-4)}\big{(}\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))+\operatorname{Tr}(J_{u}(TA)^{2}J_{u}(T\Lambda))\big{)}$
$\displaystyle\hskip
120.00018pt,\frac{(2^{2n}-2)}{2^{n}(2^{2n}-1)(2^{2n}-4)}\big{(}\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))-\operatorname{Tr}(J_{u}(TA)^{2}J_{u}(T\Lambda))\big{)}\bigg{\\}}.$
(87)

Using the definition of unitarity we see that the first eigenvalue is upper
bounded by

$\frac{2^{n}(2^{2n}-2)\operatorname{Tr}(AA{}^{\dagger})}{2^{n}(2^{2n}-1)(2^{2n}-4)}=\frac{2^{n}(2^{2n}-2)(2^{2n}-1)}{2^{n}(2^{2n}-1)(2^{2n}-4)}u(A)\leq(1+3\,2^{-2n})u(A),$
(88)

for $n\geq 2$. Note that the constant $3$ in the last inequality is somewhat
loose. Furthermore, using eqs. 80 and 79 we can also provide bounds for the
other two eigenvalues, to get

$\displaystyle\frac{(2^{2n}-2)}{2^{n}(2^{2n}-1)(2^{2n}-4)}\big{(}\operatorname{Tr}(J_{u}(A)^{2}J_{u}(\Lambda))\pm\operatorname{Tr}(J_{u}(TA)^{2}J_{u}(T\Lambda))\big{)}$
$\displaystyle\leq\frac{(2^{2n}-2)(2^{n}+1)}{2^{n}(2^{2n}-1)(2^{2n}-4)}\operatorname{Tr}(AA{}^{\dagger})$
(89) $\displaystyle=\frac{(2^{2n}-2)(2^{n}+1)}{2^{n}(2^{2n}-4)}u(A)$
$\displaystyle\leq(1+4\,2^{-n})u(A),$

where again the constant $4$ is an overestimate. Hence, the spectral radius of
$\hat{\Omega}^{0}$ is bounded by $u(A)$ up to a small multiplicative
correction, i.e.

$s(\hat{\Omega}^{0})\leq(1+4\,2^{-n})u(A).$ (90)

The plan is now to leverage section XI to bound the spectral radius of
$\hat{\Omega}\hat{W}$. To do this we first need to bound the norm (from eq.
86)

$\left\|\hat{\Omega}^{0}\hat{D}-\hat{\Omega}\hat{W}\right\|_{\infty}\leq\left\|(\hat{\Omega}-\hat{\Omega}^{0})\right\|_{\infty}\left\|\hat{D}\right\|_{\infty}+\left\|\hat{\Omega}\right\|_{\infty}\left\|(\hat{D}-\hat{W})\right\|_{\infty}.$
(91)

We can bound the terms on the RHS in a straightforward manner (using the
definition eq. 73),

$\left\|(\hat{D}-\hat{W})\right\|_{\infty}\leq\left\|(\hat{D}-\hat{W})\right\|_{HS}=\frac{\sqrt{4\,2^{2n}+8}}{2^{n}(2^{2n}-1)(2^{2n}-4)},$
(92)

and (using the definition of $\hat{\Omega}^{0}$)

$\left\|(\hat{\Omega}-\hat{\Omega}^{0})\right\|_{\infty}\leq(2^{2n}-1)u(A),$
(93)

and finally

$\displaystyle\left\|\hat{\Omega}\right\|_{\infty}$
$\displaystyle\leq\left\|\hat{\Omega}\right\|_{HS}\leq
3\,2^{n}(2^{2n}-1)u(A),$ (94) $\displaystyle\left\|\hat{D}\right\|_{\infty}$
$\displaystyle=\frac{2^{2n}-2}{2^{n}(2^{2n}-1)(2^{2n}-4)}.$ (95)

Plugging this all back in we get

$\left\|\hat{\Omega}^{0}\hat{D}-\hat{\Omega}\hat{W}\right\|_{\infty}\leq
u(A)\frac{3\,2^{n}(2^{2n}-1)\sqrt{4\,2^{2n}+8}+(2^{2n}-2)(2^{2n}-1)}{2^{n}(2^{2n}-1)(2^{2n}-4)}\leq
3\,2^{-n}u(A).$ (96)

Moreover, we have that

$\left\|\hat{\Omega}^{0}\hat{D}\right\|_{\infty}\leq\frac{9\,u(A)2^{n}(2^{2n}-1)(2^{n}-2)}{2^{n}(2^{2n}-1)(2^{2n}-4)}\leq
11\,u(A),$ (97)

for $n\geq 3$, and by the same argument

$\left\|\hat{\Omega}\hat{W}\right\|_{\infty}\leq 11\,u(A).$ (98)

Hence, through section XI, the spectral radius difference can be bounded as

$|s(\hat{\Omega}^{0}\hat{D})-s(\hat{\Omega}\hat{W})|\leq\big{(}22u(A)\big{)}^{2/3}\big{(}3\,2^{-n}u(A)\big{)}^{1/3}\leq
12\,2^{-n/3}u(A),$ (99)

and the spectral radius of $\hat{\Omega}\hat{W}$ is thus bounded by (using the
above equation and eq. 90)

$s(\hat{\Omega}\hat{W})\leq(1+4\,2^{-n}+12\,2^{-n/3})u(A).$ (100)

We can plug this into section XI to obtain

$\left\|\hat{\Omega}\hat{W}^{m-2}\right\|\leq(u(A)(1+16\,2^{-n/3}))^{m-2}+\big{[}2(m-2)^{2}(u(A)(1+16\,2^{-n/3}))^{m-3}\big{]}\max\big{\\{}11u(A),(11\,u(A))^{2}\big{\\}},$
(101)

which takes care of the ‘dynamic’ part of the dynamic shadow norm. To bound
the SPAM contribution we can observe

$\left\|\hat{\Omega}PW\big{(}\\!\\!\\!\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\Theta_{x}\big{)}WP{}^{\dagger}\right\|_{\infty}\leq\left\|\hat{\Omega}\right\|_{HS}\left\|W\right\|_{HS}^{2}\left\|\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\Theta_{x}\right\|_{HS}.$
(102)

Of these only $\|{\sum_{x\in\\{0,1\\}^{n}}\Theta_{x}}\|_{HS}$ has not been
considered. From a straightforward calculation (using that
$\Lambda_{R}(\tilde{0}_{n})$ is a state and
$\\{\Lambda_{L}^{*}(\tilde{x})\\}_{x}$ a POVM) one sees that
$\sum_{x\in\\{0,1\\}^{n}}\Theta_{x}=2^{n}(2^{n}+1)^{2}v_{1}v_{2}^{T}$ with

$\displaystyle v_{1}$
$\displaystyle:=\Big{(}1,1,\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle,\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle,\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle,\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle\Big{)},$ (103) $\displaystyle
v_{2}$ $\displaystyle:=\Big{(}1,1,\langle\\!\langle
0_{n}|\Lambda_{R}(\tilde{0}_{n})\rangle\\!\rangle,\langle\\!\langle
0_{n}|\Lambda_{R}(\tilde{0}_{n})\rangle\\!\rangle,\langle\\!\langle
0_{n}|\Lambda_{R}(\tilde{0}_{n})\rangle\\!\rangle,\langle\\!\langle
0_{n}|\Lambda_{R}(\tilde{0}_{n})\rangle\\!\rangle\Big{)}.$ (104)

We can use this to upper bound the SPAM factor as

$\displaystyle\left\|\hat{\Omega}PW\big{(}\\!\\!\\!\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\Theta_{x}\big{)}WP{}^{\dagger}\right\|_{\infty}$
$\displaystyle\leq\left\|\hat{\Omega}PW\big{(}\sum_{x\in\\{0,1\\}^{n}}\Theta_{x}\big{)}WP{}^{\dagger}\right\|_{HS}$
(105)
$\displaystyle=2^{n}(2^{n}+1)^{2}\big{[}v_{1}W{}^{\dagger}P{}^{\dagger}\hat{\Omega}{}^{\dagger}\hat{\Omega}PWv_{1}{}^{\dagger}\;v_{2}W{}^{\dagger}P{}^{\dagger}Wv_{2}{}^{\dagger}\big{]}^{1/2}$
$\displaystyle\leq
2^{n}(2^{n}+1)^{2}\bigg{[}\left\|\hat{\Omega}\hat{\Omega}{}^{\dagger}\right\|_{\infty}v_{1}W{}^{\dagger}P{}^{\dagger}PWv_{1}{}^{\dagger}\;v_{2}W{}^{\dagger}P{}^{\dagger}Wv_{2}{}^{\dagger}\bigg{]}^{1/2}$
$\displaystyle\leq\frac{2^{n}(2^{n}+1)^{2}\left\|\hat{\Omega}\right\|_{HS}}{\big{(}2^{n}(2^{2n}-4)(2^{2n}-2)\big{)}^{2}}\bigg{[}\big{[}(2^{2n}-2^{2n}-2)+\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\tilde{x}\rangle\\!\rangle(4-2\,2^{n})\big{]}^{2}$ $\displaystyle\hskip
120.00018pt+2\big{[}(2-2^{n})+\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\tilde{x}\rangle\\!\rangle(2^{2n}-2^{n})\big{]}^{2}\bigg{]}^{1/2}$
$\displaystyle\hskip
120.00018pt\times\bigg{[}\big{[}(2^{2n}-2^{2n}-2)+\langle\\!\langle
0_{n}|\tilde{0}_{n}\rangle\\!\rangle(4-2\,2^{n})\big{]}^{2}$
$\displaystyle\hskip 130.0002pt+2\big{[}(2-2^{n})+\langle\\!\langle
0_{n}|\tilde{0}_{n}\rangle\\!\rangle(2^{2n}-2^{n})\big{]}^{2}\bigg{]}^{1/2}.$

Gathering terms, throwing away some negative ones, remembering our bound for
$\left\|\hat{\Omega}\right\|_{HS}$, and using that

$\displaystyle\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle\leq 1,$ (106)

and $\langle\\!\langle 0_{n}|\Lambda_{R}(\tilde{0}_{n})\rangle\\!\rangle\leq
1$ by construction we can bound this further by

$\displaystyle\left\|\hat{\Omega}PW\big{(}\\!\\!\\!\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\Theta_{x}\big{)}WP{}^{\dagger}\right\|_{\infty}\leq\frac{3\,2^{2n}(2^{n}+1)^{2}(2^{2n}-1)}{\big{(}2^{n}(2^{2n}-4)(2^{2n}-2)\big{)}^{2}}\bigg{[}(2^{2n}-2^{n}-2)^{2}+2(2-2^{n})^{2}+(2^{2n}-2^{n})^{2}+(4-2\,2^{n})^{2}\bigg{]}.$
(107)

We would like to stress that from this expression we can already see that the
SPAM norm contribution is asymptotically independent of $n$. By basic
numerics, we can obtain

$\left\|\hat{\Omega}PW\big{(}\\!\\!\\!\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\Theta_{x}\big{)}WP{}^{\dagger}\right\|_{\infty}\leq
11\,u(A).$ (108)

We again note that this constant is sub-optimal (especially for large $n$).
Putting all of this together we obtain the stated bound. ∎

When the probe super-operator is a unitary restricted to the traceless
subspace ($A=P_{\rm ad}UP_{\rm ad}$ for some unitary $U$) then we can obtain a
substantially improved bound, which hinges critically on the fact that $U$ is
a quantum channel.

######  Theorem 9 (Restatement of Theorem 2 in the main text).

Consider the $n$-qubit Clifford UIRS protocol and let $A=P_{\rm ad}UP_{\rm
ad}$ be a probe super-operator with $U$ a unitary. Also let $\tilde{0}_{n}$ be
a noisy implementation of the all-zero state and $\\{\tilde{x}\\}_{x}$ the
noisy computational basis POVM). The dynamic shadow norm is bounded as

$\left\|A\right\|_{{\rm dyn},m}\leq 10.$ (109)

###### Proof.

We begin from the definition of the dynamic shadow norm, given by

$\left\|A\right\|_{{\rm
dyn},m}=\max_{\Lambda_{R},\Lambda_{L}}(2^{n}+1)^{2}2^{n}\sum_{x\in\\{0,1\\}^{n}}{\langle\\!\langle}{x^{\otimes
2}\otimes\tilde{x}}|\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}(P_{\rm ad}UP_{\rm ad})^{\otimes
2}\otimes\Lambda\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}\bigg{]}^{m}|{0_{n}^{\otimes 2}\otimes\tilde{0}_{n}}{\rangle\\!\rangle}.$
(110)

Here, again we write $\Lambda:=\Lambda_{R}\Lambda_{L}$. Note also that $P_{\rm
ad}^{2}=P_{\rm ad}$ and that $P_{\rm ad}$ commutes with both $U$ and
$\phi(g)$. Hence, we can write

$\left\|A\right\|_{{\rm
dyn},m}=\max_{\Lambda_{R},\Lambda_{L}}(2^{n}+1)^{2}2^{n}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}{\langle\\!\langle}{x^{\otimes
2}\otimes\Lambda_{L}^{*}(\tilde{x})}|(P_{\rm ad}^{\otimes
2}\otimes\mathbb{I})\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}(U^{\otimes
2}\otimes\Lambda)\\!\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}\bigg{]}^{m}|{0_{n}^{\otimes
2}\otimes\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle}.$ (111)

Furthermore
$\operatorname*{\text{{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}$ is a projector, and thus

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}(2^{n}+1)^{2}2^{n}\\!\\!\\!\\!\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\\!\\!\\!\\!{\langle\\!\langle}{x^{\otimes
2}\otimes\Lambda_{L}^{*}(\tilde{x})}|(P_{\rm ad}^{\otimes
2}\otimes\mathbb{I})\sum_{\pi,\pi^{\prime}}W_{\pi,\pi^{\prime}}|{\pi}{\rangle\\!\rangle}{\langle\\!\langle}{\pi^{\prime}}|$
$\displaystyle\hskip
150.00023pt\times\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}(U^{\otimes
2}\otimes\Lambda)\\!\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}\bigg{]}^{m}|{0_{n}^{\otimes
2}\otimes\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle},$ (112)

where we have used the resolution of the third-moment projector as in eq. 73.
Now defining the vectors

$\displaystyle\hat{v}_{\pi}$ $\displaystyle:={\langle\\!\langle}{x^{\otimes
2}\otimes\Lambda_{L}^{*}(\tilde{x})}|(P_{\rm ad}^{\otimes
2}\otimes\mathbb{I})|{\pi}{\rangle\\!\rangle},$ (113)
$\displaystyle\hat{w}_{\pi^{\prime}}(m)$
$\displaystyle:={\langle\\!\langle}{\pi^{\prime}}|\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}(U^{\otimes
2}\otimes\Lambda)\\!\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}\bigg{]}^{m}|{0_{n}^{\otimes
2}\otimes\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle},$ (114)

we can express the shadow norm as

$\left\|A\right\|_{{\rm
dyn},m}=\max_{\Lambda_{R},\Lambda_{L}}(2^{n}+1)^{2}2^{n}vWw^{T}(m).$ (115)

By direct calculation analogous to the calculations done in the proof of
theorem 8, this becomes

$\displaystyle\left\|A\right\|_{{\rm dyn},m}$
$\displaystyle=\max_{\Lambda_{R},\Lambda_{L}}\frac{(2^{n}+1)^{2}2^{n}}{2^{n}(2^{2n}-4)(2^{2n}-1)}\bigg{[}\big{(}(2^{2n}-2)-2\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle 2^{n}\big{)}\hat{w}_{(12)}$
$\displaystyle\hskip
50.00008pt+\big{(}2^{2n}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle-2^{n}\big{)}\hat{w}_{(123)}+\big{(}2^{2n}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle-2^{n}\big{)}\hat{w}_{(132)}\bigg{]}.$
(116)

Finally, we use that $\left\|\pi^{\prime}\right\|_{\infty}=1$ and that
$|{0_{n}^{\otimes 2}\otimes\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle}$ is
a quantum state to see that

$\displaystyle|\hat{w}_{\pi^{\prime}}(m)|$
$\displaystyle=|{\langle\\!\langle}{\pi^{\prime}}|\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}(U^{\otimes
2}\otimes\Lambda)\\!\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}\bigg{]}^{m}|{0_{n}^{\otimes
2}\otimes\Lambda_{R}(\tilde{0}_{n})}{\rangle\\!\rangle}|$ (117)
$\displaystyle\leq\left\|\bigg{[}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}(U^{\otimes
2}\otimes\Lambda)\\!\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}\bigg{]}^{m}\right\|_{1\to 1}$ $\displaystyle\leq 1,$

since $U^{\otimes 2}\otimes\Lambda$ and
$\operatorname*{\text{{$\mathbb{E}$}}}_{g\in\mathbb{C}_{n}}\phi(g)^{\otimes
3}$ are quantum channels. Together with the fact that
$|\operatorname*{\text{{$\mathbb{E}$}}}_{x\in\\{0,1\\}^{n}}\langle\\!\langle
x|\Lambda_{L}^{*}(\tilde{x})\rangle\\!\rangle|\leq 1$, we get

$\displaystyle\left\|A\right\|_{{\rm
dyn},m}\leq\frac{(2^{n}+1)^{2}2^{n}}{2^{n}(2^{2n}-4)(2^{2n}-1)}\bigg{[}(2^{2n}-2)+2\,2^{n}\big{)}+\big{(}2^{2n}+2^{n}\big{)}+\big{(}2^{2n}+2^{n}\big{)}\bigg{]}\leq
10$ (118)

for $n\geq 2$. ∎

Finally, we provide a proof of section XI, adapted from a very similar
statement in ref. [46, Lemma 8.5].

###### Proof of section XI.

We begin by bringing $A$ into Schur normal form, i.e.,

$A=U(D+N)U{}^{\dagger}$ (119)

where $D$ is diagonal (with the eigenvalues of $A$ on the diagonal), $N$ is
strictly upper triangular and $U$ is unitary. Now consider the expansion of
$(D+N)^{m}$. Since $N$ is strictly upper triangular, any term with more than
$d-1$ factors of $N$ must vanish. Hence, we have

$\displaystyle\left\|A^{m}\right\|$
$\displaystyle=\left\|U(D+N)^{m}U{}^{\dagger}\right\|$ (120)
$\displaystyle\leq\left\|\Lambda\right\|^{m}_{\infty}+\sum_{i=1}^{\min\\{d-1,m\\}}\binom{m}{k}\left\|D\right\|_{\infty}^{m-i}\left\|N\right\|_{\infty}^{i}$
$\displaystyle\leq\left\|\Lambda\right\|^{m}_{\infty}+(d-1)m^{d-1}\max\big{\\{}s(A)^{m-d+1},s(A)^{m-1}\big{\\}}\max\big{\\{}\left\|N\right\|_{\infty},(\left\|N\right\|_{\infty})^{d-1}\big{\\}},$

where we have used that $\binom{m}{k}\leq m^{d-1}$, Hölder’s inequality, and
the monotonicity of the exponential function. Now note that

$\left\|N\right\|_{\infty}\leq\left\|D\right\|_{\infty}+\left\|A\right\|_{\infty}\leq
2\left\|A\right\|_{\infty}.$ (121)

Combining this with $\left\|D\right\|_{\infty}=s(D)=s(A)$ we obtain the lemma
statement. ∎

##  XII Pauli-noise estimation

Here we analyze the Pauli-noise estimation scheme outlined in the main text.
Recall that we consider sequences of the form
$\mathbf{g}=(c^{-1},p_{m},\ldots,p_{1},c)$, where $p_{1},\ldots,p_{m}$ are
i.i.d. randomly drawn elements from the Pauli group $\mathbb{P}_{n}$ and $c$
is randomly drawn multi-qubit Clifford $\mathbb{C}_{n}$. For $\tau$ a
traceless Hilbert-Schmidt normalized multi-qubit Pauli operator and sequence
$\mathbf{g}$ we define the filter-function as

$f_{\tau}(x,\vec{g})\coloneqq\alpha{\langle\\!\langle}{x}|\omega(c)\omega(p_{m})A_{\tau}\ldots
A_{\tau}\omega(p_{1})\omega(c)|{0_{n}}{\rangle\\!\rangle},$ (122)

with $A_{\tau}=|{\tau}{\rangle\\!\rangle}\\!{\langle\\!\langle}{\tau}|$ and
$\alpha=2^{n}(1+2^{n})$. Without SPAM, the expected value of the single shot
estimator, is given by

$\displaystyle k_{\tau}(m)$
$\displaystyle=\alpha\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{c\in\mathbb{C}_{n}}\sum_{x\in\\{0,1\\}^{n}}\\!\\!\\!\\!{\langle\\!\langle}{x^{\otimes
2}}|\omega(c^{-1})^{\otimes 2}|{\tau^{\otimes
2}}{\rangle\\!\rangle}{\langle\\!\langle}{\tau^{\otimes 2}}|\omega(c^{\otimes
2})|{0_{n}^{\otimes 2}}{\rangle\\!\rangle}\,\Lambda_{\tau,\tau}^{m-1}$ (123)
$\displaystyle=\alpha\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{c\in\mathbb{C}_{n}}\sum_{x\in\\{0,1\\}^{n}}\left\langle
x\right|\omega(c)(\tau)\left|x\right\rangle^{2}\left\langle
0\right|\omega(c)(\tau)\left|0\right\rangle^{2}\,\Lambda_{\tau,\tau}^{m-1}\,.$

with
$\Lambda_{\tau,\tau}={\langle\\!\langle}{\tau}|\Lambda|{\tau}{\rangle\\!\rangle}$.
Since the Clifford group acts transitively on the traceless Pauli operators
$\mathbb{P}^{\ast}_{n}$, we can rewrite

$k_{\tau}(m)=\alpha\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{\tau^{\prime}\in
2^{n/2}\mathbb{P}^{\ast}_{n}}\sum_{x\in\\{0,1\\}^{n}}\left\langle
x\right|\tau^{\prime}\left|x\right\rangle^{2}\left\langle
0\right|\tau^{\prime}\left|0\right\rangle^{2}\,\Lambda_{\tau,\tau}^{m-1}.$
(124)

Out of the $2^{2n}-1$ traceless Pauli-operators only $2^{n}-1$ have non-
vanishing diagonal entries (those consisting only out of local $\mathbb{I}$
and $Z$). The non-vanishing diagonal entries are all identical to $2^{n/2}$.
Thus, using the definition of $\alpha$ we have

$k_{\tau}(m)=\alpha\frac{2^{n}(2^{n}-1)}{2^{2n}(2^{2n}-1)}\Lambda_{\tau,\tau}^{m-1}=\Lambda_{\tau,\tau}^{m-1}\,.$
(125)

It remains to calculate the variance associated with estimating $k_{\tau}(m)$,
as given in (19) in the main text. We intend to prove that $k_{\tau}(m)$ has
variance bound in $O(2^{n})$. To do this first, note that

$f_{\tau}(x,\vec{g})^{2}={\langle\\!\langle}{x^{\otimes
2}}|\omega(c^{-1})^{\otimes 2}|{\tau^{\otimes
2}}{\rangle\\!\rangle}{\langle\\!\langle}{\tau^{\otimes 2}}|\omega(c)^{\otimes
2}|{0_{n}^{\otimes 2}}{\rangle\\!\rangle}$ (126)

since $P^{\otimes 2}\tau^{\otimes 2}{P{}^{\dagger}}^{\otimes 2}=\tau^{\otimes
2}$. Hence, the variance associated to the estimation can be upper bounded by

$\displaystyle\mathbb{V}_{\tau}(m)$ $\displaystyle\leq
2^{2n}(2^{n}+1)^{2}\\!\\!\\!\\!\sum_{x\in\\{0,1\\}^{n}}\operatorname*{\text{\LARGE\raisebox{-3.45595pt}{$\mathbb{E}$}}}_{c\in\mathbb{C}_{n}}{\langle\\!\langle}{x^{\otimes
2}}|\omega(c^{-1})^{\otimes 2}|{\tau^{\otimes 2}}{\rangle\\!\rangle}$
$\displaystyle\hskip 60.00009pt\times{\langle\\!\langle}{\tau^{\otimes
2}}|\omega(c)^{\otimes 2}|{0_{n}^{\otimes
2}}{\rangle\\!\rangle}{\langle\\!\langle}{x}|\omega(c^{-1})|{\tau_{0}}{\rangle\\!\rangle}$
$\displaystyle\hskip
110.00017pt\times{\langle\\!\langle}{\tau_{0}}|\omega(c)|{0_{n}}{\rangle\\!\rangle},$
(127)

where we have used that $\mathbb{E}_{p\in\mathbb{P}}\
\omega(p)=|{\tau_{0}}{\rangle\\!\rangle}{\langle\\!\langle}{\tau_{0}}|$ and
the trace preservation of $\Lambda$. Noting again that $\omega(c)$ acts
trivially on $\tau_{0}$ and transversally on the traceless Pauli operators, we
see that

$\\!\\!\\!\mathbb{V}_{\tau}(m)\leq\frac{2^{3n}(2^{n}\\!+\\!1)^{2}}{2^{2n}-1}\bra{0_{n}}\\!\tau_{0}\\!\ket{0_{n}}^{2}\\!\\!\sum_{\tau^{\prime}\in\mathbb{P}^{*}_{n}}\\!\bra{0_{n}}\\!\tau^{\prime}\\!\ket{0_{n}}^{4}$
(128)

which becomes by the analogous argument as above

$\mathbb{V}_{\tau}(m)\leq\frac{2^{3n}(2^{n}+1)^{3}}{2^{3n}(2^{2n}-1)}=O(2^{n}),$
(129)

as intended.

##  XIII Marginal channel reconstructions and cross-talk tomography

We here show how to employ the local Clifford UIRS protocol to get tomographic
information of channel marginals. To this end, recall that with the local
Clifford UIRS protocol we can efficiently estimate the quantity
$3^{-|w|}\operatorname{Tr}(\Lambda P_{w}UP_{w}\Lambda)$ for any unitary
channel $U$, where $\Lambda$ is a quantum channel and $P_{w}$ is the projector
onto the irreducible representation of $\mathbb{C}_{1}^{\times n}$ labeled by
the bit string $w$, provided $|w|$ bounded. We can introduce channel marginals
$\Lambda_{k}$ of $\Lambda$ by inserting a maximally mixed state into all but
the first $k$ (out of $n$) inputs and tracing out all but the first $k$ output
qubits. Note that we can choose the order of the qubits arbitrarily, therefore
restricting to the first $k$ qubits does not cost any generality. For any
$w\in\\{0,1\\}^{k}\times\\{0\\}^{n-k}$ we have

$3^{-|w|}\operatorname{Tr}(\Lambda
P_{w}AP_{w})=3^{-|w|}\operatorname{Tr}(\Lambda_{k}P_{w}AP_{w}),$ (130)

which only depends on the marginal $\Lambda_{k}$. Now consider the $k$-qubit
super-operator

$S_{k}=\sum_{w\in\\{0,1\\}^{k}}P_{w}\Lambda_{k}P_{w},$ (131)

which we will refer to as the _pinched marginal_ associated with the marginal
$\Lambda_{k}$. Note that this super-operator is not necessarily a quantum
channel (although it is trace preserving). One can see that the pinched
marginal is composed of blocks $\Lambda_{w}=P_{w}\Lambda P_{w}$ which we refer
to as the _unital marginals_ in the main text.

We can reconstruct the pinched marginal $S_{k}$ using the local Clifford UIRS
protocol. To see this, consider the group of $k$-qubit Clifford operators
$\mathbb{C}_{k}$. Reference [32, theorem 39] implies that

$\frac{1}{\lvert\mathbb{C}_{k}\rvert}\sum_{C\in\mathbb{C}_{k}}\big{(}(2^{2k}-1)\operatorname{Tr}(S_{k}\omega(C){}^{\dagger})-(2^{2k}-2)\big{)}\omega(C)=S_{k}$
(132)

using that the Clifford group is a $2$-design (on $k$ qubits). Using the
definition of $S_{k}$ we see that

$\operatorname{Tr}(S_{k}\omega(C))=\sum_{w\in\\{0,1\\}^{k}}3^{|w|}\big{(}3^{-|w|}\operatorname{Tr}(\Lambda_{k}P_{w}CP_{w})\big{)}.$
(133)

From theorem 7 we know that we can estimate the quantities
$3^{-|w|}\operatorname{Tr}(\Lambda_{k}P_{w}CP_{w})$ to accuracy $\epsilon$
using $S=O(k2^{(2+2\log_{2}(3))k}/\epsilon^{2})$ runs of the local Clifford
UIRS protocol. Hence, we can reconstruct $S_{k}$ to $\epsilon$ error in
diamond norm using $S=O(k2^{(2+4\log_{2}(3))k}/\epsilon^{2})$ runs. In
particular, we can also construct every ‘block’ $\Lambda_{w}$ of $S_{k}$ with
additive error in diamond norm from the same number of samples. Moreover,
since the procedure we have described above is independent of which set of $k$
qubits is considered, it follows immediately that one can reconstruct all
$\binom{n}{k}$ pinched marginals associated to each set of $k$ qubits to a
global $\epsilon$ error in diamond norm using
$S=O(nh(k/n)k2^{(2+4\log_{2}(3))k}/\epsilon^{2})$ samples (where $h(k/n)$ is
the binary entropy). Using $\log\binom{n}{k}\leq k\log(\mathrm{e}n/k)$, we can
relax the statement to guarantee $\epsilon$-accurate recovery of all unital
marginals $\Lambda_{w}$ with $|w|=k$ in diamond norm from
$O(k^{2}2^{9k}/\epsilon^{2})$.

##  XIV Details on SPAM-robust channel reconstruction

Using multi-qubit Clifford UIRS we can extract the relative average-gate
fidelities that enter the tomographic reconstruction of both schemes from the
output statistics of random gate-set sequences, without the need to perform
different interleaved experiments. This gives rise to an efficient and robust
channel reconstruction protocol. In the multi-qubit Clifford UIRS protocol the
decay rate are given as

$p(A)=\frac{\operatorname{Tr}(A{}^{\dagger}\Lambda)}{2^{2n}-1}.$ (134)

Hence, if we assume that $A=P_{\rm ad}UP_{\rm ad}$ for a unitary channel $U$
we see that $p(U)=(2^{n}F(U,\Lambda)-1)/(2^{n}-1)$, where $F(U,\Lambda)$ is
the average fidelity between $U$ and $\Lambda$. By theorem 9 and theorem 8, we
can estimate using the UIRS protocol, an exponential number of average
fidelities using only a polynomial number of samples (and equivalently channel
queries). Furthermore, for $U$ a Clifford unitary calculating the sequence
correlation function, and, thus, the entire classical-post processing, is time
and space efficient in the number of qubits.

Characterizing a quantum channels in terms of different relative average gate
fidelities with unitaries can provide valuable diagnostic in itself. This can
be seen as a robust gate-set or channel variant of selective state tomography
[67]. Beyond this, building on the results of refs. [53, 29, 31, 32], having
access to relative average fidelities is an powerful primitive for the
tomographic reconstruction of channels, which we will now consider in more
detail.

The first task we consider is the reconstruction of unitary (or more generally
bounded Kraus rank) quantum channels—low-rank randomized benchmarking
tomography. This task is vital to the characterization of calibration errors.
Reference [32] establishes that given a list of estimates
$[\hat{F}(C,\Lambda)]_{C\in\mathcal{A}}$ of relative average gate fidelities
with respect to a randomly chosen subset $\mathcal{A}$ of Clifford unitaries,
a constraint least-squares fit can reconstruct $\Lambda$ provided that
$|\mathcal{A}|\geq cd^{2}\log(d)$. More precisely, the error of the channel
estimate $\hat{\Lambda}$ in Hilbert-Schmidt norm of the Choi-states fulfills

$\left\|J(\Lambda)-J(\hat{\Lambda})\right\|_{HS}\leq
2^{2n}\frac{\left\|{\hat{F}}-{F}\right\|_{2}}{\sqrt{|S|}}$ (135)

where ${F}:=[F(C,\Lambda)]_{C\in\mathcal{A}}$ is the vector of average
fidelities of length $|\mathcal{A}|$, $\hat{F}$ is an estimate of $F$ produced
through the shadow sequence protocol and the norm is the $l_{2}$ vector norm.
Furthermore, the reconstruction is stable against $\Lambda$ deviating from the
low-rank assumption (model-mismatch) and can be formulated in different
$p$-norms on both sides, we refer to the supplemental material of ref. [32]
for details. Reference [32], however, has not analyzed the overall sampling
complexity of the resulting RB tomography scheme when combined with a robust
way to acquire the relative average fidelities.

The UIRS protocol can provide the missing piece. After decay fitting, we can
give estimates ${\hat{F}}$ for the vector of fidelities ${F}$ with error
guarantee

$\left\|{\hat{F}}-F\right\|_{\infty}=O\left(\sqrt{\frac{\log(2|\mathcal{A}|/\delta)}{S}}\right)$
(136)

with success probability $1-\delta$ using $S$ samples, i.e., the size of the
gate-set shadow. Using the standard relations between $l_{\infty}$ and $l_{2}$
vector norms this implies we can obtain an $\epsilon$-accurate reconstruction
of $\Lambda$ provided

$S\geq C\,2^{4n}\frac{\log(2|\mathcal{A}|/\delta)}{\epsilon^{2}}\,$ (137)

with a suitable constant $C$. Dropping polynomial factors in $n$ and
$1/\epsilon$, we find that the total number of gate-set shadows scales as
$O(2^{4n})$. Note that the number of channel invocations is bounded by the
maximal sequence length times the number of sequences. This matches the
scaling of the information theoretic lower bound derived in ref. [32] for the
case that the average gate fidelities are measured independently. Besides the
favourable scaling, the UIRS protocol has the benefit compared to, e.g., the
interleaved protocol of ref. [29] that the same measurement data is used for
estimating all the average fidelities.

Besides the compressive, low-rank quantum channel tomography, we can use
average gate-fidelities from UIRS protocols for the tomography of a more
general class of quantum channels. If $\Lambda$ is a unital quantum channel
then it is known [32, theorem 38] (see also ref. [53]) that it can be
expressed as

$\Lambda=\frac{1}{S}\sum_{C\in S}\big{(}DF(C,\Lambda)-2^{-n}D+1)\omega(C)$
(138)

with $D=2^{n}(2^{n}+1)(2^{2n}-1)$, provided the set $S$ is a unitary
$2$-design. We can provide a direct reconstruction for the unital channel
$\Lambda$ by calculating

$\hat{\Lambda}=\frac{1}{S}\sum_{C\in
S}\big{(}D\hat{F}(C,\Lambda)-2^{-n}D+1)\omega(C)$ (139)

where the estimates $\hat{F}(C,\Lambda)$ are again provided by the multi-qubit
Clifford UIRS protocol. The accuracy of this reconstruction depends on the
metric used. If we consider the Hilbert-Schmidt of the Choi state as before,
we see that

$\displaystyle\left\|J(\Lambda)-J(\hat{\Lambda})\right\|_{HS}$
$\displaystyle=\frac{D}{|S|}\sum_{C\in S}|F(C,\Lambda)-\hat{F}(C,\Lambda)|,$
(140)

since $\left\|J(C)\right\|_{HS}=1$ for all unitaries $C$. Hence, by the same
argument as in the unitary case, the number of samples required scales as
$O(2^{8n})$. The same argument holds for all norms for which
$\left\|C\right\|=1$, such as the diamond norm.

## References

  * Campbell  _et al._ [2017] E. T. Campbell, B. M. Terhal, and C. Vuillot, Nature 549, 172 (2017).
  * Barends  _et al._ [2014] R. Barends, J. Kelly, A. Megrant, A. Veitia, Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O’Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis, Nature 508, 500 (2014).
  * Arute  _et al._ [2019] F. Arute _et al._ , Nature 574, 505 (2019).
  * Barak  _et al._ [2020] B. Barak, C.-N. Chou, and X. Gao, (2020), arXiv:2005.02421.
  * Hangleiter and Eisert [2023] D. Hangleiter and J. Eisert, Rev. Mod. Phys. 95, 035001 (2023).
  * Eisert  _et al._ [2020] J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Nature Rev. Phys. 2, 382 (2020).
  * Kliesch and Roth [2021] M. Kliesch and I. Roth, PRX Quantum 2, 010201 (2021).
  * Elben  _et al._ [2023] A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, Nature Rev. Phys. 5, 9 (2023).
  * Knill  _et al._ [2008] E. Knill, Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J., Jost, C. Langer, R. Ozeri, S. Seidelin, and J. Wineland, Phys. Rev. A 77, 012307 (2008).
  * Dankert  _et al._ [2009] C. Dankert, R. Cleve, J. Emerson, and E. Livine, Phys. Rev. A 80, 012304 (2009).
  * Emerson  _et al._ [2005] J. Emerson, R. Alicki, and K. Zyczkowski, J. Opt. B 7, S347 (2005).
  * Lévi  _et al._ [2007] B. Lévi, C. C. López, J. Emerson, and D. G. Cory, Phys. Rev. A 75, 022314 (2007).
  * Magesan  _et al._ [2012a] E. Magesan, J. M. Gambetta, and J. Emerson, Phys. Rev. Lett. 85, 042311 (2012a).
  * Helsen  _et al._ [2022a] J. Helsen, I. Roth, E. Onorati, A. H. Werner, and J. Eisert, arXiv:2010.07974 3, 020357 (2022a).
  * Flammia [2021] S. T. Flammia, arXiv:2108.05803 (2021).
  * Huang  _et al._ [2020] H.-Y. Huang, R. Kueng, and J. Preskill, Nature Phys. 16, 1050 (2020).
  * Paini and Kalev [2019] M. Paini and A. Kalev, (2019), arXiv:1910.10543.
  * Flammia and Liu [2011] S. T. Flammia and Y.-K. Liu, Phys. Rev. Lett. 106, 230501 (2011).
  * Flammia and Wallman [2020] S. T. Flammia and J. J. Wallman, ACM Trans. Quant. Comp. 1, 1 (2020).
  * Merkel  _et al._ [2013] S. T. Merkel, J. M. Gambetta, J. A. Smolin, S. Poletto, A. D. Córcoles, B. R. Johnson, C. A. Ryan, and M. Steffen, Phys. Rev. A 87, 062119 (2013).
  * Blume-Kohout  _et al._ [2013] R. Blume-Kohout, J. King Gamble, E. Nielsen, J. Mizrahi, J. D. Sterk, and P. Maunz, (2013), arXiv:1310.4492.
  * Blume-Kohout  _et al._ [2017] R. Blume-Kohout, J. K. Gamble, E. Nielsen, K. Rudinger, J. Mizrahi, K. Fortier, and P. Maunz, Nature Comm. 8, 14485 (2017).
  * Greenbaum [2015] D. Greenbaum, (2015), arXiv:1509.02921.
  * Nielsen  _et al._ [2020a] E. Nielsen, K. Rudinger, T. Proctor, A. Russo, K. Young, and R. Blume-Kohout, Quantum Sci. Technol. 5, 044002 (2020a).