{'fraction_non_alphanumeric': 0.03954155377447257, 'fraction_numerical': 0.007663443334731496, 'mean_word_length': 4.414104216534708, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Estimating gate-set properties from random sequences

With quantum devices for computing and simulation increasing in scale and complexity, there is a growing need for the development of tools that obtain precise diagnostic information about quantum operations. In this work, we show that by measuring random gate sequences, one can accurately and efficiently estimate a wealth of different properties of noisy implementations of gate sets. This simple experimental protocol is independent of the properties one intends to estimate. It generates `sequence shadows' from which gate-set properties can be extracted, through classical post-processing, in a state preparation and measurement error robust way. The proposed classical post-processing schemes include protocols to extract many average gate fidelities with respect to arbitrary unitary channels. This - as a special case - emulates (interleaved) randomized benchmarking, but is vastly more general in its applicability. We establish that the sequence estimation scheme can be used as a primitive for partial, compressive and full process tomography, and the learning of Pauli noise. This gives rise to channel variants of shadow estimation with close-to optimal performance guarantees. Finally, we discuss applications to the engineering cycle for the optimization of quantum gates, for instance as a novel method to diagnose crosstalk.

With quantum devices for computing and simulation increasing in scale and complexity, there is a growing need for the development of tools that obtain precise diagnostic information about quantum operations. In this work, we show that by measuring random gate sequences, one can accurately and efficiently estimate a wealth of different properties of noisy implementations of gate sets. This simple experimental protocol is independent of the properties one intends to estimate. It generates 'sequence shadows' from which gate-set properties can be extracted, through classical post-processing, in a state preparation and measurement error robust way. The proposed classical post-processing schemes include protocols to extract many average gate fidelities with respect to arbitrary unitary channels. This -as a special case -emulates (interleaved) randomized benchmarking, but is vastly more general in its applicability. We establish that the sequence estimation scheme can be used as a primitive for partial, compressive and full process tomography, and the learning of Pauli noise. This gives rise to channel variants of shadow estimation with close-to optimal performance guarantees. Finally, we discuss applications to the engineering cycle for the optimization of quantum gates, for instance as a novel method to diagnose crosstalk.

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. With this increased size comes increased complexity, and in order to scale even further to larger, more accurate devices, it is key to develop tools for efficiently characterizing quantum operations [1,2]. 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 providing a fair comparison with classical computing power on the same tasks [3]. Over the years, multiple protocols for characterizing quantum operations have been developed and put into practice [4,5]. The most prominent classes of protocols for characterizing digital quantum computing devices are randomized benchmarking [6][7][8][9][10][11] and gate-set tomography [12][13][14][15][16][17].
Protocols in both of these classes simultaneously characterize an entire set of quantum gates by observing the output measurement statistics of different sequences of gates applied to an initial state. The main intuition behind employing sequences is that the operations from the gate-set themselves generate non-trivial input states (and measurements) that are then used to probe other gates of the gate-set. One key advantage of such self-consistent approaches is that, in contrast to direct process tomography [18][19][20], the accuracy of the characterization of the quantum operations is not directly degraded by imperfections in state-preparation and measurement. This is often referred to as state-preparation and measurement (SPAM) error robustness. To the contrary, these protocols can typically use 'simple' measurements and initial state preparation native to the computing platform.
The characterization information obtained in these protocols is very different. While randomized benchmarking typically returns a single scalar quantity capturing an averaged property of the gate-set, gate-set tomography aims at a full tomographic reconstruction of all the quantum channels implementing the gates, the initial state and the measurement. Hence, while randomized benchmarking is inherently scalable, the diagnostic information it provides is rather limited. On the other hand, the significant surplus of information returned by gate-set tomography comes at the cost of an exponentially large number of required measurement sequences, making it impractical already for more than a few qubits. This leaves us in need of protocols for characterizing quantum gate-sets that flexibly interpolate between these two extremes and allow one to balance resource requirements and information gain.
In the context of quantum state characterization, it has been observed [21] that if one performs basis measurements in randomly chosen bases, one can estimate many linear properties of the state with perhaps surprisingly high efficiency, in particular, when the orbit of each basis vector constitutes a state 3-design. Importantly, due to the randomization, the measurement procedure itself does not depend on the observables one wants to estimate. Instead this dependence is wholly moved to classical post-processing. The measured data (on a sample-by-sample basis) randomly sketches a arXiv:2110.13178v1 [quant-ph] 25 Oct 2021 shadow of the quantum state that allows for the efficient estimation of many observables without ever writing down an accurate tomographic description of the state under investigation.
In this work, we show that measurements on random gate sequences provide efficient self-consistent shadows for the noisy implementation of entire gate-sets from which (exponentially) many properties of the gate-set can be estimated using only classical post-processing. We leverage the recent insight [11] that the inversion and filtering steps of randomized benchmarking protocols can be delegated to classical post-processing, to introduce the concept of sequence correlation functions. These correlation functions can be seen as the gate-set analog of observables for quantum states, in that they flexibly encode properties of a noisy implementation of the gate-set. In many relevant cases this encoding takes the form of an exponential decay (analogously to the average fidelity in randomized benchmarking). By fitting these exponential decays the estimation of these gate-set properties can thus be done in a way that is robust against SPAM errors. For the gate-sets of multi-qubit Clifford gates and local Clifford gates in particular, we identify classes of gate-set properties that can be efficiently estimated and provide explicit bounds on the sampling complexity.
Additionally, by using these estimates as input data for compressed sensing algorithms, we construct a practical, SPAM-robust and sample-optimal tomography scheme for coherent gate-set errors, closing a crucial gap in the literature on compressive RB tomography [22,23]. Furthermore, we show that, from sequence shadows of the local Clifford group, one can reconstruct channel marginals which potentially provide valuable information for diagnosing cross-talk between qubits. To illustrate the flexibility of random sequence protocols, we also derive a more experimentally-friendly variant, with matching sample complexity, of the Pauli-channel RB tomography protocols of ref. [24].
The striking feature of the estimation of gate-set properties based on self-consistent sequence shadows is that it uses very simple and already routinely measured experimental data: multi-qubit measurements on random sequences. Furthermore, like the state shadow estimation protocol of ref. [21], the data acquisition happens independently of the targeted properties, which only enter in classical post-processing. Figure 1 illustrates the basic scheme. This is a crucial distinction from traditional randomized benchmarking protocols and we expect that this feature makes sequence shadow estimation an ideal primitive for many characterization tasks that arise in the engineering cycle of a digital quantum computing device. To illustrate this we work out two use-cases: advanced gate-set characterization protocols using random sequences as a primitive. These should be considered as merely two examples (out of a wealth of future applications) that demonstrate the use of data from random gateset sequences and general sequence correlation functions. Be-fore providing technical statements and derivation of our results, we provide a detailed overview in the following section.

Result 1: Random sequence protocol
Our first result is the establishment of the random sequence protocol itself. In section IV, we develop the random sequence estimation protocol: a primitive for estimating properties of gate-sets. We introduce the concepts of sequence shadows (given by a sequence of randomly drawn gate-set elements, together with the outcome of a fixed POVM measurement on a state which is generated by applying the sequence to a fixed initial state), and sequence correlation functions, generalizing earlier work in randomized benchmarking and state shadow tomography. Sequence correlation functions can be seen as the gate-set analog of an observable, in that they allow us to compute, in classical post-processing, properties of noisy gate-sets (for example the average fidelity of an average group element) from experimentally observed sequence 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 postprocessing.
Using these general concepts we develop (in section IV D) the uniform independent random sequence (or UIRS) protocol where sequences are drawn from the gate-set uniformly and independently at random, and the correlation functions satisfy a factorization property (see eq. (12)). This protocol has a familiar structure and is easy to implement experimentally. For UIRS we can provide the most explicit results. The key result here is theorem 1, which shows that UIRS data follows a single-exponential decay behaviour if the gate-set is a group, from which gate-set properties can be extracted in a way that is robust against state preparation and measurement errors.

Result 2: Explicit protocols for gate-set-shadow estimation
The UIRS protocol provides the starting point for gateset-shadow estimation, which can efficiently extract exponentially many averaged properties of a gate-set using a polynomial number of measurements using UIRS shadow sequence data and median-of-means estimators. Hence, it can be seen as a unification of randomized benchmarking and state shadow estimation [21]. Similar to state shadow estimation, the classes of gate-set properties (captured by sequence correlation functions) that can be efficiently estimated depend on the gate-set under consideration.
We make shadow gate-set estimation through the UIRS protocol explicit for several important gate-sets: namely the multi-qubit Clifford group C n , the independent single qubit Clifford group C ×n 1 (which we will call the local Clifford group), and the Pauli group P n . For these gate-sets, under the In the first step shadow sequence data is obtained from the quantum device by applying random sequences and measuring. Note that both the sequence and the measurement outcome are stored. Secondly a series of correlation functions fA -encoding gate-set properties-are provided, from which the associated correlators are computed. In the third step these correlators are fitted against the sequence length m to obtain gateset property data. This data can then be used for further analysis (such as the procedures proposed in section VIII), or even used when taking steps in improving the quantum hardware, exploiting the actionable advice offered by the random sequence estimation protocol, illustrated by the arrow pointing back to the physical hardware. assumption of gate independent noise (modelled by a quantum channel Λ interspersing subsequent gates), we explicitly work out what gate-set properties can be efficiently estimated, through representation theory based calculations of sample complexity.

Result 2.a: Multi-qubit Clifford UIRS
In section V A, we show that in the UIRS protocol with the multi-qubit Clifford group we can efficiently extract observables of the form p(A † Λ), where p is the "depolarizing probability" (essentially the average fidelity) of a channel A † Λ. Here A is an arbitrary super-operator encoded in the correlation function, subject only to a bound on its unitarity u(A) = Tr(AA † )/(2 2n − 1) (theorem 4). In particular, we can efficiently estimate the depolarizing probability w.r.t. any unitary channel U (theorem 3). This means we can use the multi-qubit Clifford UIRS protocol, together with median-ofmeans estimation, to estimate exponentially many average fidelities F (U, Λ) using only polynomially many samples. This is a potentially extremely useful primitive, and in section VIII we outline a procedure for characterizing the coherent (unitary) part of the gate noise Λ through optimization of p(U † Λ) over unitaries U , that uses the multi-qubit Clifford UIRS protocol as a primitive.

Result 2.b: Local Clifford UIRS
In section V A, we show that in the UIRS protocol with the local Clifford group we can efficiently extract observables of the form p k (A † Λ) where p k (A † Λ) is the depolarizing parameter restricted to a k qubit subspace (like the addressability metric considered in ref. [25]) and where A is an arbitrary super-operator subject only to a bound on its Hilbert-Schmidt norm Tr(AA † ) (theorem 4) and a locality constraint stating that A only acts non-trivially on at most k out of n qubits and as the completely depolarizing (tracial) channel on the remaining n − k qubits (theorem 5).

Result 3: Channel reconstruction
We have described UIRS as a tool for estimating properties of noisy gate-sets. Interestingly, we can use this estimation procedure as a primitive for the robust reconstruction of noisy quantum channels Λ. In this context we can either consider Λ as due to the noisy gate-set itself (as above) or we can consider Λ to be a black-box channel to which we have query access.

Result 3.a: Robust shadow channel tomography
The multi-qubit Clifford UIRS protocol allows for the estimation of exponentially many average fidelities {F (U, Λ)} U ∈S , where S is a list of unitaries, using only polynomially many channel queries. It has been realized in RB tomography [26] that access to such relative average fidelities is a powerful primitive for the tomography of unital quantum channels and, combined with compressed sensing techniques, for unitary quantum channels [22,23]. Building upon these results, the multi-qubit Clifford UIRS protocol gives rise to a robust channel tomography protocol based on easy-toimplement random sequence measurements.
In the case where Λ is a unitary quantum channel, we obtain a reconstruction with system-size independent accuracy using O(2 4n ) samples in the sequence shadow. This makes the Clifford-UIRS protocol (in combination with compressive RB tomography) the first fully robust channel tomography scheme that provably achieves this sampling complexity. The sampling complexity matches the information-theoretic lower bound derived ref. [23]. In the case where Λ is a unital quantum channel we obtain reconstruction with system-size independent accuracy using O(2 8n ) queries to the quantum channel.

Result 3.b: Partial channel tomography
Similarly, we can use the local Clifford UIRS protocol as a primitive for partial channel tomography, i.e. the reconstruction of channel marginals Λ k , that is, channels obtained by restricting a global channel Λ to k input and output qubits. Using the local fidelities p w (A) estimated through the local Clifford UIRS protocol we can approximately reconstruct the set of all k-qubit channel marginals using O(2 αk ) samples.
Here, approximately means that we can not reconstruct the full channel marginal, but instead some partial super-operator S k that is a block diagonal approximation to Λ k . While this is not a full partial tomography scheme for channels, we do believe that it will prove useful in practice (see result 5 and section VIII).

Result 4: Learning Pauli channels
To show that it is viable and fruitful to go beyond uniformly independent random sequences, we provide in section VII a simple protocol using correlated random sequences that estimates the diagonal elements of an n-qubit quantum channel, or equivalently the probabilities of a Pauli channel, to relative precision using O(n2 n ) samples. This matches the sample complexity derived in ref. [24], but is based on a much more straightforward implementation. In section VIII, in what is more of an outlook than a presentation of rigorous results, we sketch how the UIRS protocol and the techniques established above can be used when devising protocols for the engineering cycle around the estimation and optimization of quantum gates. The techniques we propose include unitary noise optimization, aimed at differentiating between coherent and incoherent noise, and what we call crosstalk tomography, which builds upon the rigorous partial channel tomography scheme laid out above. Crosstalk tomography characterizes cross-talk in quantum gates, a concern specifically when devising schemes for fault tolerant quantum computing and in quantum error correction.

III. PRELIMINARIES
In this section, we will recall some mathematical tools and set up notation used throughout the text. We will assume basic knowledge of representation theory, and refer to appendix A for a didactic discussion of the representation theoretic concepts used in this work.

A. Liouville representation
In the remainder of this work, we will work in the Liouville or transfer matrix representation of quantum channels. We represent finite-dimensional d × d density matrices ρ as length d 2 column vectors |ρ and POVM elements E as length d 2 row vectors E|, with a corresponding traceinner product E|ρ = Tr(E † ρ). In this picture superoperators E get mapped to d 2 ×d 2 matrices E with the property E|ρ = |E(ρ) . 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 P * (normalized under the trace inner product), in this case we will also always write d = 2 n . We will denote the normalized identity by 2 −n/2 I = τ 0 and the set of normalized traceless Hermitian Pauli matrices τ as P * 0 . Finally, we will, throughout the text, use a tilde to indicate noisy implementations of POVM elements and states, soρ is a noisy implementation of the state ρ and {Ẽ x } x is a noisy implementation of the POVM {E x } x . For the specific case of the all-zero computational basis state |0 0| ⊗n we will write |0 n (with noisy version |0 n ) and for the computational basis POVM |x x| we will write x| (with noisy version x|).

B. Simultaneously estimating many observables
Key to the results in this work is the following general statistics observation, which also powers state shadow estimation [21]. Let p be a probability distribution over some (finite) set X , and let S be a set of observables, i.e., functions f : X → R. Suppose we wish to estimate the vector of means [E X (f )] f ∈S to some overall error . A surprising fact from mathematical statistics is that this is possible by is the maximal variance of the functions in S. Doing this (without making strong assumptions on the observables f ) requires the construction of socalled sub-Gaussian estimators (see refs. [27][28][29] for reviews) for the means E X (f ). A straightforward to compute example of such an estimator is the median-of-means estimator, which has been used in state shadow estimation by ref. [21]. Following their notation, it involves gathering N K samples from the distribution p, where N, K are integers. For an ob-servable f , one can then construct the estimator for the average E(f ), splitting the data into K equally sized parts of size N . It can be shown that if we set then we have with probability 1 − δ. We can substitute to obtain the direct relation in terms of the total number of samples N K. 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 δ (through the setting of K). This is unfortunate, but it turns out to be impossible [29] to drop this requirement for sub-Gaussian estimators. Much of the technical work in the remainder of the paper will consist of upper bounding maximal variances associated to estimators of observables, which translate directly into sample complexities using eq. (5).

IV. RANDOM SEQUENCES AND SEQUENCE SHADOWS
The central primitive of this work is the notion of a random sequence, an experimentally feasible and readily implementable operational primitive. Such random sequences will be denoted as g. The elements of this random sequence are taken from a gate-set G which in the present work is chosen to form a group, which is both a very common assumption and which reflects many reasonable gate-sets in practice. The key attributes of this primitive are its length (denoted by m), the gate-set from which it is sampled (denoted G) and the distribution from which it is sampled (denoted µ : G ×m → [0, 1]). An example of a protocol making use of random sequences is randomized benchmarking, where the gate-set is (in the original version of RB) the multi-qubit Clifford group and the gates in the sequence are sampled independently and uniformly at random. In fact, it is important to stress that this type of data is already routinely taken in numerous experiments based on a number of different physical architectures.
A random sequence can be implemented on a quantum computer. This implementation can be modeled by a quantum channel E(g) (possibly depending on other external parameters). Given a POVM with elements {E x } x and a quantum state ρ we can associate a measurement probability p(E x , ρ; g) = E x |E(g)|ρ (written as p(x, g)). It is useful to think of these probabilities as a function p(x, g) : The output statistics of such random sequence experiments will be of central interest here. In this work, again, we will consider only gate-sets G that also form groups. It is possible to extend at least part of our work to gate-sets that are not groups, but we will not consider this possibility here.

A. Sequence correlation functions
We can consider the probabilities p(x, g) for fixed x as functions from G ×m to the complex plane. When the gateset G is a (finite or compact) group, the vector space of such functions has a lot of structure, and is called the group algebra C[G ×m ] of G ×m . In particular it has an inner product, given by the average over the gate-set.
as well as other useful properties. This inner product leads directly to the idea of a sequence correlation function, which is a function f (x, g) : X × G ×m → [0, 1] ⊂ C that also depends on a POVM label set. By noting that f (x, g) for fixed x is in the group algebra, and extending the inner product to We will call k f (m) a correlator (associated to the correlation function f , and studying the properties of various correlators will take up the rest of this work. It is worth thinking about what form the sequence correlation functions f (x, g) for fixed x, can take. As mentioned before they are elements of the group algebra C[G ×m ], which by the Peter-Weyl theorem [30], is spanned by the matrix elements of the irreducible representations of G ×m . Moreover, the irreducible representations of G ×m are completely determined by tensor products of the irreducible representations of G. Hence functions f (x, g) can be written as where σ i are (not necessarily irreducible) representations of G and B x is an operator of a proper size. The linear structure w.r.t. the representations of G will be key to our analysis later. Note that this is a very general definition, and it will often be useful to specialize it.
B. Implementation maps, gate-independent noise and black-box channels As has been said before, we can associate a quantum channel E(g) to a sequence g that represents the implementation of this sequence on the quantum device we wish to characterize. It is useful to consider this at the level of gate-sets and consider an implementation map E : G ×m → S n where S n is the space of n-qubit super-operators. Note that the existence of such a map already implies an assumption on the behaviour of the underlying quantum device (for instance it excludes time-dependent effects). Nonetheless, this class of maps is quite general and it is useful to make further assumptions on E(g). In the literature on gate-set characterization two such assumptions are common: Markovian noise and gateindependent noise. Markovian noise posits the existence of a map φ : G → S n such that E(g) = m i=1 φ(g i ). Under this assumption it can be proven that procedures like randomized benchmarking [6][7][8][9][10][11] function correctly [11,31,32]. Gate independent noise is strictly stronger than Markovian noise; positing the existence of quantum channels Λ L , Λ R such that where ω(g)(ρ) = U g ρU g † is some ideal implementation of the gate g. Note that if G is a group then ω is a representation. We will in the remainder of this work make this assumption whenever it is needed to perform explicit calculations. We believe that like in randomized benchmarking 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. [11]) is beyond the scope of this work.
It is important to note that the channels Λ R , Λ L are fully general, in particular they could also be generated by applying some external quantum channel after every gate in the random sequence (like it is done in interleaved randomized benchmarking [33]). In the same vein one could consider the random sequence protocol in a black-box query model, where the gate-set gates g are noise-free, and interspersed with a quantum channel Λ that is accessed in a black box fashion: Note that formally this functional form for φ(g) reduces to the gate-independent noise model, even though the interpretation of Λ is very different. This means all the results we derive below for gate-independent noise also hold in the query model. We will return to this model when considering channel reconstruction in section VI.

C. Random sequence protocol
Formally, we will consider a random sequence protocol to be a set of sequence lengths M with associated probability distributions µ m over G ×m and for each sequence g ∈ G ×m an associated probability distribution p(x, g) over a POVM label set X , which are given by (1) a noisy implementation of the sequence g on a device, acting on (2) an initial state ρ measured in (3) a POVM {E x } [34]. Given all these ingredients there is a simple protocol to sample from the mixed distribution µ m (g)p(x, g) by sampling (classically) a random sequence g, and then sample from the distribution p(x, g) (through implementation on the quantum device). Such samples take the form of a tuple (x, g) and we will refer to a measured series of samples {(x i , g i )} S i=1 as a self-consistent sequence shadow [35].
Leaning on the insights from state shadow tomography and the discussion in section III B, we will argue that from O(log(|S|)) of these samples one can estimate (up to additive accuracy ) a set S of correlators k f (m) associated with sequence correlation functions f (x, g). More explicitly, imagine we have for a fixed sequence length m a list of correlation functions {f (x, g)} f ∈S . We can, for each f ∈ S define a random variable X f (m) ranging over the image of f such that where the distribution p(x, g) is obtained through the random sequence protocol. It is clear that averaging (E(X f (m)) = k f (m)) gives the associated correlator. Moreover, if we gather where is the maximal variance of the random variables X f (m).
Hence bounding this variance in terms of the sequence correlation function f (x, g) and the distribution p(x, g) gives immediate sample complexity bounds for estimating many correlators k f (m).

D. Uniformly independent random sequence (UIRS) protocols
The simplest way to formulate a random sequence protocol is by choosing every element in a sequence g independently and uniformly at random from the gate-set G. We will call this the uniformly independent random sequences (UIRS) protocol. In this context it is natural to take the sequence correlation function f as independent as well. By this we mean we consider only functions that factorize as where σ is an irreducible representation of G and A, B x are matrices supported on V σ . For the rest of the paper we will consider f A to be a real function (this will be the case in all scenarios we consider). It turns out that of the two, the operator A is the more important one, essentially defining what gate-set property is estimated. We will refer to A a probe super-operator. This probe super-operator is in principle fully general, i.e. it does not have to be a quantum channel. We will however throughout the paper assume that A is Hermiticity preserving. An example of such a sequence correlation function in the literature is given by linear cross-entropy benchmarking [3,36], where A = I, and B x ∝ |ρ E x |. This last choice of B x is generally useful [37]. Given these correlation functions and the UIRS protocol we can write down an expression for the correlator k A (m) where |Ẽ x , ρ| are a noisy POVM and initial state respectively. Fig. 1 depicts a visual explanation of how k A (m) is computed from shadow sequence data in practice.

Average
What can we learn from UIRS sequence data? Based on the structure of k A (m) one expects an exponential behaviour in m, and indeed we see that this is the case. Under the assumption of gate-independent noise, i.e., φ(g) = Λ L ω(g)Λ R we can write the following theorem.
Theorem 1 (Exponential decay in UIRS). Consider the UIRS protocol with gate-set G and let k A (m) be a correlator with factorized sequence correlation function f A . Then we have, under the assumption of gate independent noise, that where Θ, Φ are matrices induced by the representation structure of ω(g). Φ(A, Λ) depends only on the between-gates noise channel Λ := Λ R Λ L and the sequence correlation function matrix A, while Θ captures state preparation and measurement (SPAM) dependence. In particular, if ω contains n copies of the representation σ then we have where P i is the projector onto the ith copy of the representation σ inside ω.
We give a proof of this theorem in appendix B. If the ideal implementation ω is multiplicity-free, i.e., ω = λ σ λ where σ λ are all mutually inequivalent we can consider sequence correlation functions dependent on only a single subirreducible representation (i.e., σ = σ λ for some λ). In this case theorem 1 reduces to a single exponential decay as From this equation it is easy to extract the decay parameter which can be thought of as a generalized fidelity, calculating how much the channel Λ agrees (in the image of P λ ) with the probe operator A. Note that by linearity we can always divide general probe super-operators A by their support on different irreducible representations and estimate these separately with only logarithmic overhead in sample complexity. Hence the restriction to irreducible representations σ in eq. (12) has little cost. We are primarily interested in constructing estimators for p(A) given UIRS data. Constructing these estimators splits into two tasks: constructing estimators for the correlators k A (m) and constructing an estimator for p(A) from the correlator estimators for different values of m. The former task was discussed in section IV, where we have used medianof-means estimators. The latter task is essentially the fitting of exponential decays. This is a well-known statistical problem for which many solutions are available, but we will take the time to give a quick overview.

Estimating decay rates
If we consider the UIRS protocol for a fixed gate-set G and a set of correlation functions {f A } f A ∈S , we can through the use of median-of-means estimators compute estimatorŝ for all f A ∈ S and m ∈ M by gathering O(|M | log(|S|)/ 2 ) samples in total. However, in the UIRS protocol we are actually interested in the behaviour of k A (m) with respect to m. Assuming for the moment we are in the multiplicity free scenario, i.e.
our goal is to give an estimatorp(A) for p(A) given the estimators {k A (m)} m∈M . This is of course the well-studied problem of exponential decay fitting, for which many advanced techniques [38,39] are available. It is beyond the scope of this paper to give a detailed review of these techniques, but we want to briefly point out what kind of estimation accuracy can be expected in different regimes. We distinguish two types of estimation accuracy, relative and additive.
Relative accuracy: In the case where 1 − p(A) is positive but small it is known that the estimation of the decay rate p(A) can be done with relative accuracy. That is, if which means even very small deviations from unity can be detected. An example of such an estimator with rigorous bounds is given in ref. [40]. For this estimator it is important that the set M take the form of a logarithmic sweep of the interval , which is a non-trivial requirement to take into account if one wants to estimate multiple p(A) to relative accuracy.
Additive accuracy: In many cases one is only interested in additive accuracy. By this we mean that given estimatorsk A such that |k A (m) −k A (m)| ≤ for m ∈ M , we construct an estimatorp for the decay rate such that Such an estimator is good enough to for instance pursue tomographic reconstruction of quantum channels, which we consider in section VI. Note first that the relative accuracy estimator given above already gives rise to an additive estimator (this is especially relevant when 1 − p(A) is not small). However additive accuracy is much easier to achieve, for instance through the standard ratio estimator [41], or through generic least-squares fitting methods. We recommend the latter in practice, as flexible software packages [42] are available, and curve fitting places no restrictions on the form of the set M .
The decay rate p(A) can thus be efficiently estimated provided the individual averages k A (m) can be estimated efficiently. We will consider this in more detail now.

Variance
As mentioned before we can by sampling according to the UIRS protocol construct a median-of-means estimate for k A (m) for a fixed sequence length m. By the argument in section IV C this estimation is efficient if the corresponding variance V A (m) of the random variable X A (m) is controlled relative to the size of E(X A (m)) = k A (m). The goal of this section is to provide a general upper bound for this variance (for arbitrary gate independent noise) as a function of probe super-operators A. We can upper bound this variance directly by dropping the negative term: This can be rewritten as where Λ := Λ R Λ L as before. From representation theory we know that the average over σ ⊗2 ⊗ω is an orthogonal projector.
Choosing a (not necessarily orthonormal) spanning set {|v } i for its image we can write a resolution of this projector as where W is the (pseudo) inverse of the Gram matrix [ v i |v j ] i,j (in some contexts called the Weingarten matrix). We can define the matrices ⊗ Λ|v j , and in those terms the variance can be bounded as follows.
Lemma 2 (Upper bound on the variance). Let X f A (m) be defined as in eq. (9), i.e. it is the random variable induced by the UIRS protocol (of length m) on the gate-set G and correlation function f A . Let v i and W be defined as in eq. (24). Assuming only gate-independent noise, i.e. φ(g) = Λ L ω(g)Λ R with Λ R , Λ L arbitrary quantum channels, the variance of this random variable can be upper bounded by where Note that this upper bound depends on both the gate-set and the probe-super-operator A. To further investigate this, and see which sequence correlation functions can be efficiently estimated, we need properties of the gate-set G (in particular, knowledge of the set |v i ). Hence, we will in the next section consider the UIRS protocol for, namely the multi-qubit Clifford group, the local Clifford group and the Pauli group.

V. CONCRETE UIRS PROTOCOLS
We will now make the above ideas concrete by considering explicit protocols for certain well motivated gate-sets such as the multi-qubit Clifford (C n ) group, the local Clifford group (C ×n 1 ) and the Pauli group P n . This section will be fairly technical, focusing on the functional behaviour of the correlators k A (m) and the sample complexity of median-of-means estimators for these correlators. For applications that use these concrete UIRS protocols as a primitive, see sections VI and VIII.

A. Multi-qubit Clifford sequences
In this section, we will specialize the analysis for UIRS data to sequences drawn from the multi-qubit Clifford group C n . This is a much used gate-set, which moreover has a wellunderstood representation structure, allowing us to explicitly calculate the sequence mean k A (m) as well as give bounds on the variance V A (m). This variance bound will depend on the probe super-operator A (taking a form analogous to the shadow norm introduced in ref. [21]).

Average
We begin by noting that the standard adjoint representation of the multi-qubit Clifford group ω(g) decomposes into two inequivalent irreducible representations: σ tr supported by the normalized identity matrix |τ 0 and σ ad supported on the space of traceless matrices. We will restrict our discussion to sequence correlation functions with support on σ ad only, i.e.e A = P ad AP ad and consider an all-zero n-qubit initial state |0 n and a computational basis measurement POVM ({ x|} x∈{0,1} n . We will also set B x = α|ρ E x | with α a normalization factor (to be determined later). With these choices, we see from eq. (16) that Noting that |P ad | = 2 2n − 1, we see that k A (m) depends exponentially on the parameter This is a familiar quantity: for A = P ad it for instance corresponds to the depolarizing probability (essentially the average fidelity) of the channel Λ. Hence as a very special case the Clifford UIRS protocol emulates standard Clifford randomized benchmarking (without ever performing an inversion). However, this is much more general, we could for instance choose A = U a unitary channel. Then p(U ; Λ) measures the average fidelity of Λ w.r.t. the unitary U . If we choose U to be Clifford then the corresponding sequence correlation function can even be made classically tractable. Hence, we can estimate exponentially many fidelities from the decay data k A (m). Even more strongly we can consider A that do not correspond to quantum channels such as rank-one superoperators |α β|. Hence the UIRS protocol is an incredibly versatile tool to discover properties of the Clifford gate-set.
In section VI, we discuss the use of the multi-qubit Clifford UIRS protocol for the reconstruction of quantum channels, while in section VIII we outline a unitary noise optimization procedure that uses UIRS Clifford data as input.
We have discussed the effect of the probe super-operator A. It remains to fix the normalization factor in the SPAM term B x = α|ρ E x |. To fix α we will demand that in the limit of perfect state preparation, measurement and gates that k A (1) = 1. This is a reasonable normalization condition when estimating exponential decays. From a straightforward calculation we can see that Note that α grows exponentially with n. This means that the sequence correlation function associated to B x , A grows exponentially with the number of qubits, making scalable estimation (in n) of k A (m) a non-trivial fact.

Variance
From the above it is not clear that k A (m) can be efficiently estimated for arbitrary A. To investigate the limits of Clifford UIRS we must specialize to the Clifford group the variance equation given by eq. (25). It is worth first investigating a special case, namely when A is a restriction of a unitary channel U to the traceless subspace, i.e., A = P ad U P ad . In this case, the variance takes a particularly simple form: Theorem 3 (Variance for restrictions of unitary channels to traceless subspaces). Consider the multi-qubit Clifford UIRS protocol. Let φ(g) = Λ L ω(g)Λ R be a noisy implementation of the multi-qubit Clifford group on n qubits and let A = P ad U P ad be a probe super-operator with U a unitary. Also let0 n be a noisy implementation of the all-zero state and {x} x the noisy computational basis POVM). The variance of the random variable X U (m) is upper bounded independently of the number of qubits n and sequence length m. In particular, it holds that Theorem 3 is noteworthy for several reasons. The first is that the variance bound does not depend on the number of qubits n. This means that the estimation of k U (m) can be done efficiently even on a quantum system consisting of very many qubits. Secondly the variance bound does not depend on the sequence length m, making relative accuracy estimation (as described in section IV D 2) possible.
We will give a sketch of the proof of this theorem here and delegate a full derivation to appendix D. We note that the constant 10 is suboptimal, and can probably be improved with a more careful argument.
Key to deriving theorem 3 is finding a resolution for the third moment projector defined in eq. (24). We do this by moving from the adjoint representation back to the full ω(g) = U g · U g † representation, i.e., σ ad (g) = P ad ω(g)P ad , and then using the fact that the Clifford group is a 3-design [43,44] and hence, the third moment project has a resolution in terms of permutation operators in S 3 , i.e., where |π is the matrix permuting the three subsystems according to the permutation π, and where W π,π is the wellknown Weingarten matrix (see eq. (D6) for an explicit expression. Since both U and ω(g) commute with P ad we can write the variance as where are vectors encoding state preparation and measurement and Ω π,π = π|(U ⊗2 ⊗ Λ L Λ R ) (π ) . Because U ⊗2 ⊗ Λ R Λ L is a quantum channel it turns out that |[(ΩW ) m−1 v T SP ] π | ≤ 1 for all π ∈ S 3 . Moreover |v M | ≤ 1 and the entries of W grow as O(2 −3n ). Hence the overall variance is bounded independently of n and m; working out the explicit constants gives theorem 3.
Next we consider the more general case where the probe super-operator A is restricted to the traceless subspace. Note that we do not consider A to be a quantum channel. In this case the variance can be bounded in terms of the unitarity of A: which has some nice properties (in particular u(A) ≤ 1 if A is a quantum channel). Concretely we have the following theorem.
Theorem 4 (Variance in the multi-qubit Clifford UIRS protocol). Consider the multi-qubit Clifford UIRS protocol. Let φ(g) = Λ L ω(g)Λ R be a noisy implementation of the multiqubit Clifford group on n qubits and let A = P ad AP ad be a probe super-operator restricted to the traceless subspace. Also let0 n be a noisy implementation of the all-zero state and {x} x∈{0,1} n the noisy computational basis POVM). The variance of the random variable X A (m) is upper bounded in terms of the number of qubits n and sequence length m. In particular, it holds that with and where u(A) = Tr(AA † )/(2 2n − 1) is the unitarity of A.
The proof of this more general theorem is similar in spirit to the previous one, but significantly more involved. It can be found in appendix D. There are several things to note about the bound given in eq. (33). Firstly, choosing A to be unitary (u(A) = 1) does not recover theorem 3. The first difference is the appearance of the factor (1 + 16 2 −n/3 ) m−2 , which makes the variance bound technically exponential in the sequence length. However, the rate of growth goes to zero exponentially quickly for the number of qubits, and is thus not a real concern for even moderately sized systems. We moreover believe that it is a technical artifact of our proof technique and should be removable with a more sophisticated analysis. The second difference is the appearance of the quadratic term (m−2) 2 . This term comes from the fact that we consider very general probe super-operators A, which makes it possible that the matrix W Ω in eq. (25) is very non-normal, giving rise to polynomial transient dynamics in the variance bound which must be taken into account. For many sensible choices of A this O(m 2 ) behaviour will not show up (as is evidenced by theorem 3). In any case, this term does not impact the polynomial scalability of the protocol (although the variance might become quite large in practice for long sequence lengths).

B. Local Clifford sequences
Having studied the UIRS protocol for multi-qubit Cliffords we now turn our attention to the setting in which the sequence elements are sampled uniformly from the local Clifford group over n qubits. For this group it is well known that the standard conjugate representation ω(g) decomposes into 2 n irreducible, mutually inequivalent representations σ w with w ∈ {0, 1} n that have support on the normalized nonidentity Pauli operators (i.e., τ X , τ Y , τ Z ) on all qubits i for which w i = 1. The projectors onto these irreducible representations can be written as with

Average
Let us compute the functional form of k A (m) w.r.t. m. Recall that we can restrict to sequence correlation functions with probe super-operators A that only have support on a single irreducible representation σ w (g). Moreover, we will again choose {x} x the noisy computational basis POVM,0 n the noisy all-zero state and B x := α w |x 0 n |. Note that the normalization α w depends on the targeted representation. We have We can already see that m → k A (m) takes the form of a single exponential decay. It is also clear that the pre-factor x∈{0,1} n x ⊗ Λ * L (x)|P ⊗2 w |0 n ⊗ Λ R (0 n ) encodes SPAM. We can fix the normalization α w by noting that |P w | = 3 |w| and that Hence, in the absence of any state preparation and measurement errors we have This means we have to set α w = 2 n 3 |w| to satisfy the normalization requirement k A (1) = 1 in the limit of perfect SPAM. Note again that this normalization grows exponentially, this time with both the number of qubits n and the representation weight |w|.
The decay rate, which we will refer to as a local fidelity, is again somewhat familiar. For A = I, it corresponds to the average fidelity of the gates on the qubits in w assuming random gates are applied to all other qubits. This quantity was called the "addressability" in ref. [25], and by comparing p w (I) for different w one can obtain information about correlated errors (see ref. [25] for a more detailed explanation). In section VI and section VIII we will apply the local Clifford UIRS protocol to the task of reconstruction channel marginals, which model the local behaviour of a noise channel. However, we will first investigate the sample complexity of the local Clifford UIRS protocol.

Variance
It is again important to bound the sample complexity of a median-of-means estimator for k A (m), which again essentially reduces to a variance bound. We will see that in the context of the local Clifford group the sample complexity depends exponentially on the Hamming weight |w| where w is the bit-string labeling the representation σ w being isolated, but is independent of the total number of qubits in the system (again analogous to state shadow estimation). We have the following theorem.
Theorem 5 (Variance for the local Clifford UIRS protocol). Consider the local Clifford UIRS protocol. Let φ(g) = Λ L ω(g)Λ R be a noisy implementation of the local Clifford group on n qubits and A = P w AP w be a probe superoperator with |w| = k. Also let0 n be a noisy implementation of the all-zero state and {x} x the noisy computational basis POVM). The variance 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 Note that 3 −k Tr(AA † ) can be considered as a version of the unitarity restricted to the image of P w . In particular, if A = P w U P w for any unitary U we have 3 −k Tr(AA † ) = 1.
We will give a sketch of a proof of this theorem here (assuming perfect SPAM) and relegate a more detailed derivation (with SPAM errors) to appendix C. Without loss of generality we consider the representation σ w where w = (1, . . . , 1, 0, . . . , 0) with 1 in the first k = |w| entries. We will use the following notation for tensor products of single qubit Clifford operators g 1 , . . . , g j ∈ C 1 : ω(g [i,j] ) : j t=i ω(g t ).
In this notation we can see that the variance upper bound in eq. (22) can be written in the form where we have used the invariance of the Haar measure with respect to left and right multiplication with a group element and the fact that for all x there exists an element g [1,n] ∈ C ×n 1 such that ω(g [1,n] )|0 n = |x . At this point it appears as if we would have to compute third moments over the local Clifford group on n qubits (C ×n 1 ) which is non trivial. However, we get away with only ever computing the first and second moments. To see this, note that for arbitrary g 1 , . . . g n ∈ C 1 we have ω(g [1,n] )P k = ω(g [1,k] We can use this along with a first moment calculation over the last n − k registers in order to reduce the expression of the variance upper bound to where Λ k (Q) = Tr k+1,n (Λ(Q ⊗ 2 −(n−k) I n−k )) is a k-qubit quantum channel. Note that this expression is already independent of n. We can simplify this further to obtain the final bound of the form which is what we set out to achieve. Note in particular that this bound means that probe super-operators P w U P w where U is a unitary channel and |w| is bounded can be efficiently estimated (as 3 −k Tr(P w U P w U † ) = 1). This will prove useful in section VI.

C. Pauli sequences
Finally we discuss the UIRS protocol using the gate-set of n-qubit Pauli operators. For this group it is well known that the standard conjugate representation ω(g) decomposes into with Λ P P = 2 −n P |Λ |P the matrix entries of the superoperator in the Pauli basis (and similarly for the other matrices). Hence, we have in this case where indicates the point-wise matrix product in the Pauli basis. Note that there are no problems with scalability here, as there are no representations (in either the second or third moment projector) whose dimension scales with n. Hence as long as ρ, E x , A and B x are chosen such that k A (m) is sufficiently large, everything is efficient in n. One possibly useful choice is to set A = |τ τ | for some normalized Pauli operator τ . The correlator k A (m) then follows a single exponential with decay rate τ |Λ|τ , which is a diagonal element of the gate-set noise channel Λ. We do note that these choices are not entirely straightforward, as choosing an input state ρ that has non-negligible overlap with all Pauli operators τ (and thus that the pre-factor of the exponential decay is non-zero) is not possible. We will come back to this issue in section VII.

VI. CHANNEL RECONSTRUCTION FROM SHADOW SEQUENCES
One interesting application of the Clifford UIRS protocols is as a primitive for the robust tomographic reconstruction of a quantum channel Λ. The quantum channel is here again either the (in-between) noise of a gate, or was interleaved by hand via black-box queries, see discussion in section IV B. Note, however, that in the black-box query model is not straightforward to define a notion of robustness as the correct implementation of the gates-set is already assumed.

A. Multi-qubit Clifford UIRS
Kimmel et al. [26] proposed the idea to combine the output of O(d 4 ) different interleaved RB experiments in order to get a robust tomographic estimate of a unital quantum channel Λ. By explicitly exploiting the a low Kraus-rank, compressive RB tomography [22,23] can reconstruct a unitary approximation to the quantum channel from (up-to-log-factors) O(d 2 ) randomly selected different experimental setups. Using multi-qubit Clifford UIRS we can extract the same type of information, 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. In other word, we can efficiently interleave 'in post'.
Considering the multi-qubit Clifford UIRS protocol we recall that the decay rate is given as Hence, if we assume that A = P ad U P ad for a unitary channel U we see that p(U ) = (2 n F (U, Λ) − 1)/(2 n − 1), where F (U, Λ) is the average fidelity between U and Λ. By theorem 3 and theorem 4, 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 classicalpost processing, is time and space efficient in the number of qubits.
Note that the characterizing of a quantum channels in terms of different relative average gate fidelities with unitaries can provide valuable diagnostic in itself. Beyond this, building on the results of Ref. [23,45], having access to relative average fidelities is an extremely powerful primitive for the tomographic reconstruction of channels, which we will now consider in more detail.

Unitary channel reconstruction
The arguably most relevant tomographic task is to reconstruct low-rank approximation to a quantum channel. After all a precisely diagnosed coherent error might be correctable via experimental control.
Ref. [23] establishes that given a list of estimates [F (C, Λ)] C∈S of relative average gate fidelities with respect to randomly chosen subset S of Clifford unitaries, a constraint least-squares fit can reconstruct Λ provided that |S| ≥ cd 2 log(d). More precisely, the error of the channel estimatê Λ in Hilbert-Schmidt norm of the Choi-states fulfills where F (F ) is the vector of (estimates of) average fidelities of length |S| and the norm is the l 2 vector norm. Furthermore, the reconstruction is stable against Λ deviating from the low-rank assumption (model-mismatch) and can be formulated in different p-norms on both side, we refer to the supplemental material of Ref. [23] for details.
Ref. [23] however did not analyse the overall sampling complexity of the resulting RB tomography scheme when combined with a robust way to acquire the relative average fidelities.
We can fill in this blank using the UIRS protocol. After decay fitting, theorem 3, the median-of-means guarantees and (21), give an estimateF for the vector of fidelities F with error guarantee with success probability 1 − δ using N K samples, i.e. the size of the sequence shadow. Using the standard relations between l ∞ and l 2 vector norms this implies we can obtain an -accurate reconstruction of Λ provided with a suitable constant C. Dropping polynomial factors in n and 1/ , we find that the total number of sequence 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. [23] for the case that the average gate fidelities are measured independently. Besides the favorable scaling, the UIRS protocol has the benefit compared to, e.g. the interleaved protocol of Ref. [26] that the same measurement data is used for estimating all the average fidelities.

Unital channel reconstruction
Going beyond the compressive reconstruction of unitary quantum channels, we can use Clifford UIRS as a primitive for the robust reconstruction of arbitrary unitary quantum channels in the spirit of ref. [26]. In particular if Λ is a unital quantum channel then it is known [23, Theorem 38] (see also ref. [45]) that it can be expressed as 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 Λ by calculatinĝ where the estimatesF (C, Λ) are again provided by the multiqubit 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 since J(C) 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 C = 1, such as the diamond norm.

B. Partial channel tomography
Thus far we have focused on channel tomography using the multi-qubit Clifford UIRS protocol. Moving to the local Clifford UIRS protocol leads to an interesting new notion we call partial channel tomography, in analogy with partial state tomography [46]. The goal in partial channel tomography is to reconstruct the channel marginals Λ w of a quantum channel Λ, where b is a bit string of length n. The marginal Λ b [47] is defined as the channel obtained by feeding a maximally mixed state into every qubit for which b i = 1 and then tracing out those qubits at the channel output. This gives an |b| → |b| qubit quantum channel. Such marginals have not seen much study so far, but we believe that they ought to be very useful in the characterization of multi-qubit quantum circuit noise. We give a potential example of such a use, which we call crosstalk tomography, in section VIII.
The local Clifford UIRS protocol does not quite allow us to perform partial channel tomography, as we have no way to access elements (even indirectly) elements τ |Λ |τ where the normalized Pauli's τ and τ have different weights. This is akin to the restriction to unital channels in the previous section. However, we can partially fulfill the goal of reconstruction. Recall that using local Clifford UIRS we can efficiently estimate the quantity 3 −|w| Tr(ΛP w AP w ) where Λ is a quantum channel and P w is the projector onto their reducible representation of C ×n 1 labeled by the bit string w, provided |w| and 3 −k Tr(P w AP w (P w AP w ) † ) are bounded. Note that in particular we have 3 −k Tr(P w U P w (P w U P w ) † ) for any unitary U . Now consider w.l.o.g. the marginal Λ k of Λ acting on the first k (out of n) qubits. Note that for any w ∈ {0, 1} k × {0} n−k we have which only depends on the marginal Λ k . Now consider the k-qubit super-operator which we will refer to as the partial super-operator associated with the marginal Λ k . Note that this super-operator is not necessarily a quantum channel (although it is trace preserving). We can reconstruct this super-operator using the local Clifford UIRS protocol. To see this, consider the group of kqubit Clifford operators C k . From ref. [23,Theorem 38], we again know that using that the Clifford group is a 2-design (on k qubits). Using the definition of S k we see that From theorem 5 we know that we can estimate the quantities 3 −|w| Tr(Λ k P w CP w ) to accuracy using N K = O(k2 (2+2 log 2 (3))k / 2 ) runs of the local Clifford UIRS protocol. Hence we can reconstruct S k to error in diamond norm using N K = O(k2 (2+4 log 2 (3))k / 2 ) runs. Moreover, since the procedure we described above is independent of which set of k qubits is considered, it follows immediately that one can reconstruct all n k partial super-operators associated to each set of k qubits to a global error in diamond norm using N K = O(nh(k/n)k2 (2+4 log 2 (3))k / 2 ) samples (where h(k/n) is the binary entropy).
Even with the restriction to partial super-operators (as opposed to full channel marginals) we believe that the efficiency and versatility of the above procedure will make it a useful characterization procedure for quantum processes. In section VIII we sketch a potential application, which we call crosstalk tomography, based on the reconstruction protocol described above. Finally note that this protocol, as with the ones given above, can easily be made robust against SPAM errors by considering local Clifford UIRS runs with multiple sequence lengths.
Finally, we would like to note that one can consider a generalization of the local Clifford UIRS protocol where the probe super-operator A is not restricted to a single representation σ w , but instead maps between σ w and σ w for w = w . For m > 2 this would render the correlator k A (m) trivial but it will be nonzero for m = 2. Using correlation functions of this form one can extend the scheme given here to the reconstruction of full marginals. However, as one would lose the SPAM robustness of the protocol, we do not go into it further here.

VII. CORRELATED RANDOM SEQUENCES: BEYOND THE UIRS PROTOCOL
Thus far we have mostly focused on what one can learn from uniformly independently sampled random sequences (UIRS protocols). However, it is possible to go beyond this by considering more general probability distributions µ on the set of sequences of a given length. Here we give an example of this by constructing a simple protocol that estimates the diagonal elements of a black box n-qubit channel Λ using only O(n2 n ) samples. This matches the asymptotic bound given for this task in ref. [24] but our procedure is much simpler to write down and analyze (it can also be used to provide additive estimates for products of off-diagonal elements of the channel Λ, but we will not consider this in detail). Concretely we will consider random sequences of the form g = (c −1 , p m , . . . , p 1 , c) where p 1 , . . . , p m are chosen independently uniformly at random from the Pauli group P n and c is chosen uniformly at random from the Clifford group C n . Note the inverse c −1 at the end of the sequence. In a black-box fashion we will intersperse channels Λ in between the random Pauli elements. For convenience we will assume perfect measurement in the computational basis and set the starting state to be exactly |0 n (both of these assumptions can be easily loosened). Similar to eq. (12), we will consider factoring sequence correlation functions with a specific choice of probe super-operator A τ := |τ τ | where τ is a normalized traceless Pauli operator and α a normalization factor. From the discussion of the Pauli UIRS protocol (section V C) one can deduce that the corresponding cor-relator must be of the form where Λ τ,τ = τ |Λ|τ is a diagonal element of the channel Λ. To fix the normalization α we consider Now noting that the Clifford group acts transitively on the traceless Pauli operators (of which there are 2 2n − 1), and that there are precisely 2 n − 1 traceless Pauli operators with τ 2 x,x = 2 −n > 0 we get as a normalization factor ensuring that k τ (1) = 1. With this we can calculate the variance associated with estimating k τ (m). To do this first note that Hence the variance associated to the estimation can be upper bounded by where we have used that Ep∈P ω(p) = |τ 0 τ 0 | and the trace preservation of Λ. Noting that ω(c) acts trivially on τ 0 and transversally on the traceless Pauli operators, we see that which becomes for an arbitrary A τ . Note also that there are 4 n − 1 possible choices for A τ characterizing all diagonal elements of the quantum channel Λ. Hence, by using median-of-means estimators we can estimate k τ (m) for all τ to uniform additive precision using O(n2 n ) samples (independently of m). By the analysis in ref. [40] for the estimation of single exponential decays, and the fact that the decay rates Λ τ,τ are strongly clustered ( [48,Lemma 4]) this leads to a relative precision estimation of the associated decay rates Λ τ,τ , matching the performance given in ref. [24].

VIII. DISCUSSION
In the preceding sections, we have introduced the concept of sequence shadows and have shown rigorously how they could be used to efficiently achieve useful estimation tasks for noisy gate-set and for process tomography. In this final section we want to take a broader view and show how the random sequence protocol can be used as the building block for a fullscale engineering cycle for the estimation and optimization of quantum gates. This section will by necessity be less rigorous than the preceding ones, and our goal is rather to provide potential applications for our work in experimental practice.

A. Application 1: Unitary noise optimization
When characterizing noisy quantum gates one differentiates between coherent noise (due to imperfect specification of the gate) and decoherent noise (due to interactions with the environment). These two types of noise have different consequences for, e.g., error correction [1,49] and are engineered away in different ways. Hence being able to distinguish between these two types of noise is extremely useful. This inspired the creation of special purpose protocols such as unitarity benchmarking [50] and speckle purity benchmarking [3], both of which measure the amount of coherence present in the noise of a gate (or gate-set), but give no more detailed information about the actual unitary noise. Within the random sequence framework we can actually go significantly beyond this. Imagine running the multi-qubit Clifford UIRS protocol. From the sequence shadows obtained we can reconstruct average fidelities F (U, Λ) where U is a unitary and Λ is the gate noise (which might be due to some interleaving gate under investigation). If we consider a family of unitaries parametrized by some (vector) real parameter θ we can classically optimize to obtain some unitary U (θ max ) which gives a (depending on the ansatz) good indication of what the unitary part of the noise Λ is.
There are a few things (good and bad!) to consider here. The first is that this protocol requires no special actions on the part of the quantum device (apart from gathering enough data to reconstruct sufficient fidelities); everything interesting is happening in classical post-processing. The second is that the quality of the reconstruction will depend on the parametrized unitary chosen. For a small number of qubits one could conceivably optimize over the whole unitary group, but this becomes rapidly infeasible in higher dimensions. However, often experimentalists have a good idea of what the causes of unitary noise are, which can (at least potentially) be put into a parametrized form. Since the ansatz exists as a purely classical object, trying out different ansatzes is also reasonably low cost. Third is the (classical) computational cost of computing the fidelities F (U, Λ). Computing the correlation func-tions f (x, g) for a general unitary will typically be exponentially costly. However, in practice we will often be interested in families of unitaries that are close to the identity or to a Clifford gate. In this case, the computational cost of computing the correlation functions can be strongly reduced by using matrix-product-operator expansions [51] or approximate stabilizer-rank simulation [52]. In short, due to its versatility and ease of (quantum) implementation, we expect the above optimization technique to be a practical method for uncovering properties of coherent noise in quantum computing devices.

B. Application 2: Crosstalk tomography
A key problem in achieving fault-tolerance is the possibility of correlated error sources, or crosstalk. Commonly established noise thresholds for fault tolerant quantum computing require the noise to be on-site and allow for little correlations [1]. The most used error model involves i.i.d. on-site Pauli noise. Correlated errors are significantly more difficult to correct, in particular when the cross-talk has not been fully characterized. For this reason, and a significant effort has gone into characterizing [25,53] crosstalk errors specifically. In this section, we add to this effort by proposing crosstalk tomography, an efficient, robust, and detailed crosstalk characterization procedure, based on the local Clifford UIRS protocol and the partial tomography procedure (section VI B).
Note that the Clifford UIRS protocol gives us the ability to reconstruct super-operators Λ w = P w ΛP w [54] with w ∈ {0, 1} n where Λ is the noise channel in between successive applications of local Cliffords (either due to the device itself or applied in a black box fashion) and where P w is the projector on the space of Pauli operators with non-identity tensor factors whenever w i = 1. By comparing Λ w for different bit strings w we can obtain information about the correlations present in Λ.
We will sketch the protocol for a 2-qubit example for clarity only, with a straightforward extension to higher numbers of qubits. We start by using the local Clifford UIRS protocol to reconstruct the partial super-operators Λ 10 , Λ 01 and Λ 11 . Next we compute the tensor product Λ 10 ⊗ Λ 01 . It is straightforward to see that if the channel Λ is a tensor product of single qubit quantum channels featuring no correlations [55] (i.e., there is no crosstalk) then Λ 10 ⊗ Λ 01 = Λ 11 . Hence, both the difference Λ 10 ⊗ Λ 01 − Λ 11 and the product Λ 11 (Λ 10 ⊗ Λ 01 ) −1 provide meaningful characterizations of crosstalk present between qubits 1 and 2. The difference measure can be considered as a generalization of the commonly used addressability metric proposed in ref. [25]. But going beyond a mere metric, we expect that the channel marginals not only detects the presence of crosstalk, but also provide more detailed diagnostic information.
As with the previous application, there are a few caveats that deserve future study. The first is that the partial superoperators Λ w do not fully characterize the channel marginals (we have faced the same issue when considering partial chan-nel tomography). Hence, crosstalk tomography is insensitive to certain types of crosstalk. In particular, correlated nonunital processes are not detected by crosstalk tomography. Furthermore, while it is clear how to compare 1 and 2 qubit partial super-operators (through the tensor product) it is less clear how to deal with multi-qubit correlations, where we are potentially given multiple overlapping partial super-operators. Reconstructing global super-operators from this local information is related to the recently introduced channel marginal problem [47]. Finally, the two matrix-valued crosstalk measures we introduced are not the only possible ones, or even the most natural ones, given the non-commutative nature of quantum channels. One could also consider mixed products of the form (Λ 10 ⊗ Λ 01 ) −1/2 Λ 11 (Λ 10 ⊗ Λ 01 ) −1/2 or more sophisticated ways of interleaving that more closely correspond to the "order" in which local and non-local processes happen. We leave a more detailed study of such metrics and their interpretation to future work.

IX. CONCLUSION
In this work we introduced the random sequence protocol, a simple experimental procedure with many applications. For the specific case of uniformly sampled sequences (the UIRS protocol) we gave rigorous characterizations of what is being measured and (for specific gate-sets) the associated sampling complexity. With these characterizations in hand we developed new protocols for existing tomographic problems and proposed new characterization procedures such as crosstalk tomography. However, we believe we have only scratched the surface of what is possible with random sequences. Here we list several topics we believe are fruitful directions of future research.
• UIRS beyond the Clifford group. 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 [56,57], the CNOT-dihedral group and gate-sets that do not form groups [58,59]. These nongroup gate-sets will require a more advanced framework than the one we currently provide.
• Correlated sequences. We have mostly focused (with a single exception) on uniformly and independently sampled sequences, however, the random sequence framework allows for much more sophisticated sequence sampling schemes. We believe this would be a useful perspective to attack long standing problems such as the characterization of non-Markovian and timevarying noise processes in an experimentally friendly and scalable way.
• Gate-dependent noise and gate-set tomography.
Here, we have considered the tractable (and well motivated [11]) case of gate independent noise. However, one could also consider gate dependent noise (as modelled by an implementation map φ) directly, and attempt to estimate "probe implementation maps" A(g) through random sequences. This could lead to a fully-fledged shadow gate-set-tomography protocol, where one efficiently estimates quantities of the form E g Tr(A(g)φ(g)), directly probing the gate dependence of the implementation map φ. Such a procedure, as a scalable complement to gate-set tomography [60], would potentially be of great practical use.
• Implications for classical machine learning. Ref.
[61] discusses ideas of classical machine learning algorithms designed to efficiently compute ground state properties of gapped Hamiltonians, after learning from data obtained by measuring other Hamiltonians in the same phase of matter. The argument presented is based on notions of a classical state shadow. This work can also be seen as an invitation to further explore the potential for using sequence shadows of quantum gates and sequence correlation functions as primitives in rigorous classical machine learning schemes that can make predictions based on robust estimation techniques. The present work should be seen as an invitation to further pursue such further research on rigorous classical machine learning techniques in quantum physics, offering rigorous predictions on previously unseen data.
Beyond these concrete suggestions, our work should be seen as providing guidance on what properties can be reliably and robustly estimated in quantum devices. While the bulk of this work has been formulated in terms of notions of near-term quantum computing, it should be clear that the random sequence protocol equally applies beyond that, in particular to notions of quantum simulation. Depending on the underlying physical architecture, random sequences of the same or a similar type are readily implementable [62][63][64]. Only equipped with such tools for characterization of its components, one can hope quantum simulators to have meaningful predictive power. It is the hope that the present work contributes substantially to our understanding of feasible and versatile methods for quantum system identification based on simple operational quantum primitives, but making use of sophisticated classical post-processing techniques. This endeavor should also contribute to the question what one can reliably learn about quantum devices in the first place.

ACKNOWLEDGMENTS
During the final stages of drafting this manuscript, we became aware of refs. [65,66], which generalize state shadow estimation to quantum processes using the Choi-Jamiolkowski isomorphism, but without considering selfconsistent sequences of gate sets. See also remarks in ref. [67] in this context. The authors would like to thank Thomas Monz, Martin Kliesch  We will make use of sums and products of representations. Given representations ω, ω , the maps are again representations. They are, however, generally not irreducible (even if ω and ω are). However, Maschke's Lemma ensures that every representation ω of a group can be uniquely written as a direct sum of irreducible representations, that is where the index set S labels a subset of the irreducible representations of G and n λ is an integer denoting the number of copies (or multiplicity) of σ λ present in ω.

c. 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. [68] 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): where P inv is the projector onto the subspace left invariant under the action of ω(g), i.e., all vectors v s.
Second is a useful statement about the invariant subspaces of two-fold tensor powers of representations.
Lemma 7. Let σ(g), σ be real, irreducible, inequivalent, and non-trivial representations of a finite group G. Then the representation σ ⊗ σ has no invariant subspace, while the representation σ ⊗2 leaves the vector v(P σ ) invariant, where v(P σ ) is the vectorised projector onto the image of σ.

Representation theory of the Clifford group
Here we give some basic facts on 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 8. The Liouville representation of the n-qubit Clifford group C n decomposes into two irreducible representations, in particular we have for all g ∈ C n : where ω triv (g) has support on Span{τ 0 } and ω ad (g) has support on the space of traceless matrices spanned by all traceless Hermitian Pauli operators τ ∈ P * 0 .
This is a direct consequence of the 2-design property of the Clifford group. An early proof can be found in ref. [43]. A direct consequence is the following.

Lemma 9.
Let ω(g) be the Liouville representation of the n-qubit Clifford group. Then we have: We have similar statements for the local Clifford group: Lemma 10. The Liouville representation of the local Clifford group C ×n 1 on n qubits decomposes into 2 n mutually inequivalent irreducible representations where σ w (g) has support on Span{P * w } with This is a direct result of the previous lemmas, applied to each of the n-qubits individually. We also have the following statement.
Lemma 11. Let ω(g) be the Liouville representation of the local Clifford group on n qubits. Then we have where again Appendix B: The UIRS protocol: technical details In this section, we will go into the details of the theorems stated in section IV D.

Average
As we have argued in the main text, a useful class of sequence correlation functions is given by where A is some fixed probe super-operator, B x is the prepare-and-measure probe super-operator and σ(g), φ(g) are representations of the gate-set group G. As in the main text we set B x = |ρ E x | given by the initial state and final POVM of the UIRS protocol. We begin by restating the main theorem on the correlator k A (m) in the UIRS protocol.
Theorem 12 (Restatement of theorem 1). Let k A (m) be an independent sequence average with factorized sequence correlation function, over a gate-set G. Then we have, under the assumption of gate independent noise, where Θ, Φ are matrices induced by the representation structure of ω(g). Φ(A, Λ) depends only on the between-gates noise channel Λ : 7 = Λ R Λ L and the sequence correlation function matrix A, while Θ captures state preparation and measurement (SPAM) dependence. In particular, if ω contains n σ copies of the representation σ then we have where P i is the projector onto the ith copy of the representation σ inside ω.
Proof. Recall that φ(g) = Λ L ω(g)Λ R . Hence where we have used that the representation average is a projector (and thus equal to its square). Now note that we can write ω(g) = σ nσ (g) ⊕ ω (g) where ω is a representation that contains no copies of σ. From this and lemmas 6 and 7 given above we can see that where P i is the projector on the i'th copy of σ in ω. Using the fact that v(P )|A ⊗ B|v(P ) = Tr(A T P BP ) and defining the matrices Θ, Φ appropriately, we obtain the theorem statement.

Variance bound
In order to bound the sampling complexity of the estimation of UIRS correlators 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. We have stated in section IV D that the general expression for a bound on the variance of the distribution induced by the UIRS protocol is given by the following: Lemma 13 (Restatement of lemma 2). Let X f A (m) be defined as in eq. (9), i.e. it is the random variable induced by the UIRS protocol (of length m) on the gate-set G and correlation function f A . Let v i and W be defined as in eq. (24). Assuming only gate-independent noise, i.e. φ(g) = Λ L ω(g)Λ R with Λ R , Λ L arbitrary quantum channels, the variance of this random variable can be upper bounded by where The proof is elementary but we will go through it for the sake of completeness. Generally the variance of a discrete random variable X assuming values x ∈ X with probability p(x) is given by with µ the expected value of X. We can therefore obtain an upper bound on the variance by simply considering Thus, from eq. (13) we conclude that Using the identities Tr(A ⊗ B) = Tr(A) Tr(B) and AB ⊗ AB = A ⊗2 B ⊗2 we obtain From representation theory (lemma 6) we know that the average over σ ⊗2 ⊗ ω is a projector. Choosing a (not necessarily orthonormal) spanning set {|v } i for its image we can write a resolution of this projector as where W is the (pseudo) inverse of the Gram matrix [ v i |v j ] i,j (in some cases called the Weingarten matrix). Now defining matrices Θ and Ω appropriately concludes the proof.
Appendix C: UIRS with local Cliffords: variance bound In this section, we consider the UIRS protocol with the local Clifford group C ×n 1 . We will model the noisy implementation of any given Clifford by Λ L ω(g)Λ R and we will denote Λ R Λ L =: Λ for brevity. In the main text we stated the following theorem: Theorem 14 (Restatement of theorem 5). Consider the local Clifford UIRS protocol. Let φ(g) = Λ L ω(g)Λ 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 let0 n be a noisy implementation of the all-zero state and {x} x the noisy computational basis POVM). The variance 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 Proof. We begin from the general expression of the variance eq. (22) which can be written as [1,n] ω(g [1,n] ) ⊗3 (A ⊗2 ⊗ Λ) E g [1,n] ω(g [1,n] [1,n] ,...,g (m) [1,n] x∈{0,1} n Λω(g (i) [1,n] ) Λ R |0 n where { x|} x and |0 n 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 ∈ {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. As can be seen from eq. (35) the projector P w acts as |τ 0 τ 0 | on these last n − k qubits. Since we see that in x ⊗2 |ω(g (m) n 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., [1,n] ,...,g (m) [1,n] x∈{0,1} n Λω(g (i) [1,k] )ω(g [1,k] ,...,g (m) [1,k] x [1,k] Λω(g (i) [1,k] ) |Tr k+1,n (Λ R (0 n )) . (C6) Obviously |ρ k := |Tr k+1,n (Λ R (0 n )) is a k-qubit state and moreover we have [1,k] ,...,g (m) [1,k] x [1,k] where Λ k is the k-qubit marginal of Λ. At this point, we see that we have a bound on the variance which is independent 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 C ×k 1 . However, for the sake of obtaining an upper bound we simply note that since Λ k is a quantum channel. We therefore can simplify the bound to (using the invariance of the Haar measure): Again using the fact that A is taken to only have overlap with a single irreducible representation, lemma 11 and the fact that 0|τ i = 1/ √ 2 iff τ i = τ 0 or τ Z (and zero otherwise) we have which is what we set out to prove. In this section, we will go into the details of the variance bound calculations for the multi-qubit Clifford group UIRS protocol. Concretely we prove the following theorem.
Theorem 15 (Restatement of theorem 4). Consider the multi-qubit Clifford UIRS protocol. Let φ(g) = Λ L ω(g)Λ R be a noisy implementation of the multi-qubit Clifford group on n qubits and let A = P ad AP ad be a probe super-operator restricted to the traceless subspace. Also let0 n be a noisy implementation of the all-zero state and {x} x the noisy computational basis POVM. The variance of the random variable X A (m) is upper bounded in terms of the number of qubits n and sequence length m. In particular, it holds that and where u(A) = Tr(AA † )/(2 2n − 1) is the unitarity of A. .

Proof.
Recall that the variance can be bounded as (eq. (23)): where Λ := Λ R Λ L is the noise in-between subsequent gates. We can provide a concrete resolution for the third moment by noting that C n is a 3-design [44], and hence its third moment follows that of the unitary group U (2 n ), which is fully determined (for n ≥ 2) by Schur-Weyl duality. In particular we have W π,π (P ⊗2 ad ⊗ I)|π π |(P ⊗2 ad ⊗ I) where the matrices π permute copies of the base Hilbert space, i.e., π |i 1 , i 2 , i 3 = |i π(1) , i π(2) , i π(3) .
which takes care of the "dynamic" part of the variance. To bound the SPAM contribution we can observe Of these only x∈{0,1} n Θ x HS has not been considered. From a straightforward calculation (using that Λ R (0 n ) is a state and {Λ * L (x)} x a POVM) one sees that x∈{0,1} n Θ x = 2 n (2 n + 1) 2 v 1 v Here, again we write Λ := Λ R Λ L . Note also that P 2 ad = P ad and that P ad commutes with both U and φ(g). Hence, we can write V U (m) ≤ (2 n + 1) 2 Furthermore Eg∈C n φ(g) ⊗3 is a projector, and thus where we have used the resolution of the third-moment projector as in eq. (D6). Now defining the vectorŝ v π = x ⊗2 ⊗ Λ * L (x)|(P ⊗2 ad ⊗ I)|π (D54) we can express the variance bound as V(m) ≤ (2 n + 1) 2 2 n vW w T (m).
Finally we provide a proof of lemma 17, adapted from a very similar statement in ref. [70,Lemma 8.5]. 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 where we have used that m k ≤ m d−1 , Hölder's inequality, and the monotonicity of the exponential function. Now note that Combining this with D ∞ = s(D) = s(A) we obtain the lemma statement.