{'fraction_non_alphanumeric': 0.03192160770636107, 'fraction_numerical': 0.0060122903172230525, 'mean_word_length': 4.302219091229306, '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': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Classical and Hybrid Shadows of Quantum States

Classical shadows are a computationally efficient approach to storing quantum states on a classical computer for the purposes of estimating expectation values of local observables, obtained by performing repeated random measurements. In this note we offer some comments on this approach. We note that the resources needed to form classical shadows with bounded relative error depend strongly on the target state. We then comment on the advantages and limitations of using classical shadows to simulate many-body dynamics. In addition, we introduce the notion of a hybrid shadow, constructed from measurements on a part of the system instead of the entirety, which provides a framework to gain more insight into the nature of shadow states as one reduces the size of the subsystem measured, and a potential alternative to compressing quantum states.


I. INTRODUCTION
An idealized quantum computing platform allows one to: i) repeatedly create a complex quantum state by applying a specified quantum circuit to a simple initial state, ii) destructively measure the state in the computational basis, possibly applying further unitary gates before doing so. Given these capabilities, it is natural to ask how to go about efficiently and accurately capturing properties of the state (e.g., entanglement and correlation functions), while requiring as few preparations/measurement iterations as possible. Can one perform a strategically choose a set of measurements, and use the outcomes to create an approximation to the quantum state which is of reasonable size, and which can be used to estimate various state properties such as expectation values of a range of operators? Any such procedure would also be of purely theoretical interest in that it would furnish a compressed description of quantum states that could perhaps be used in classical computations, much as matrix product states are used to efficiently compute the static and dynamic properties of d = 1 quantum systems with low entanglement.
A recent development along these lines goes under the moniker of shadow tomography. The term itself dates from the work of Aaronson [1] who investigated how many samples would be needed for the task of reconstructing a set of expectation values to a given accuracy. Huang et. al. [2] took inspiration from this work to define the notion of a classical shadow of a quantum state which is a set of approximations to the state constructed from snapshots in which multiple copies of the quantum state are prepared and measured (in a randomized basis). In the limit of an infinite number of snapshots, averages over the shadow equal quantum mechanical averages in the exact state, and in certain cases surprisingly few snapshots are required to accurately approximate a large set of observables, which need not be specified in advance. The body of results surrounding these ideas is the subject of a recent review [3]. We note that the simplest example of a classical shadow, which we will use below, was introduced earlier by Paini and Kalev [4] albeit without naming it as such.
In this note we offer some comments on classical shadows from the viewpoint of quantum many body theory and statistical mechanics. We are interested in the nature of the representation of the density matrix that lies at the heart of shadow technology, the utility of shadows for measuring quantities of particular physical interest, for reducing the effort involved in time evolving many body quantum systems on a classical computer and in a generalization to hybrid classical-quantum shadows that interpolates between the full quantum state and its classical shadow representation.

II. BASICS
Huang et al. [2] gave a general construction of classical shadows based on ensembles of random unitaries. In their construction, a unitary U (drawn randomly from the ensemble) is applied to the state ρ, yielding U ρU † . Then one measures each qubit in the Z basis and constructs a snapshot of the state as the operator U † |b b| U , where |b is the measurement outcome. Averaging snapshots over the unitaries and the measurement outcomes defines a linear map M(ρ) b dU U † |b b| U b|U ρU † |b = M(ρ) (1) from density matrices to density matrices (since M(ρ) is a completely positive trace preserving map). Here dU is some as yet unspecified measure on the space of manybody unitary matrices, and defines the ensemble. If the ensemble of unitaries is chosen such that the map M is invertible, then the inverse map applied to Eq. (1) provides an exact expression with all but one eigenvalues being negative. The inverted snapshots can then be used to efficiently estimate the expectation values of operators with a bounded Hilbert-Schmidt norm, but are ill suited for typical few body observables that we consider [2,5]. Further, given that global Clifford unitaries are less reliably implemented on near term quantum computers, we restrict our discussion to local unitaries for practical considerations, while generalizing our claims to global unitaries in an Appendix [5].
The special case of U being a tensor product of independent Haar random unitaries on each qubit was studied by Paini and Kalev [4] earlier in the equivalent language of picking random measurement axes. Here the inverse exists and takes the form where we see that half of the eigenvalues are negative. In fact one obtains the same inverse map when independent single site random Clifford unitaries alone are used in place of random Haar unitaries [2]. Given an operator O (assumed without loss of generality to be traceless), the classical shadow can be used to estimate the expectation value o = Tr(ρO). Each element of the shadow yields a random variableô m ≡ Tr(ρ m O), which averages to o. Theô m are identically distributed and independent for different m; we refer to a single such random variable asô. Theô m may be combined in various ways to estimate o. For example one could take the average M m=1ô m /M . Alternatively, one can take averages of subsets of {o m } M m=1 , and then take the median of those averages (median of means). This latter method turns out to preferable. For appropriately chosen size of subsets, the M required to achieve an accuracy with probability > 1 − δ is given by where C is an unimportant numerical constant [2]. It is clear that the number of samples required is controlled by the variance of the shadow random variableô.

III. COMMENTS
We now offer some comments on the formalism described above. Note that for simplicity we restrict our discussions considering O to be a Pauli string, and avoid the more general problem of simultaneously estimating the error for a number of different O [2,6], for which the qualitative nature of our arguments would not be different.

A. Random and non-random measurements
Let us specialize to the case where the operator O is a k-body Pauli string. It is possible to calculate the variance in Eq. (5) exactly for the Clifford ensemble [2], and the result is Therefore the shadow recipe above requires × log(2/δ) samples in order to guarantee that the absolute error in our estimate of O is less than . However suppose we happen to know in advance that O is a k-body string of Pauli Z operators alone. Can we do better? The answer is yes, of course. In this case just estimate O in the usual way: always measure the state in the computational (Z) basis. For M experimental runs, this generates a list of outcomes {ô m } M m=1 , each of which takes values in {−1, 1}. Once again we may estimate o by taking the average outcome across experimental runs (using median of means method). The M required to achieve an accuracy with probability > 1 − δ is given by formula Eq. (5) withô →ô . This makes a dramatic change, as it is easy to show that var(ô ) = 1 − ρ(O) 2 (cf. Eq. (6)). Therefore M ≥ C 2 (1 − ρ(O) 2 ) × log(2/δ) measurements suffice when we know in advance that O is a string of Pauli Z operators. Crucially, in this latter case the measurements required do not increase exponentially with k.
While we considered a z string, clearly we will get the same bound for any specified Pauli string as we can simply measure along the appropriate axis on each site. But this strategy fails when we wish to estimate multiple and arbitrary Pauli strings on k sites. Indeed we may estimate that in order to have any chance accurately estimating O for any such k-body Pauli string, we will need to have measured each of the k sites along each of the 3 axes multiple times leading to O(3 k ) measurements consistent with the factor of 3 k in the shadow bound. We note that the superiority of the traditional method for measuring the expectation value of fixed operators has been discussed in Ref. [6] under the terminology of "derandomization" wherein you assume that random measurements are the place to begin.
In the case when one has access to two copies of the unknown state, denoted by ρ ⊗ ρ, along with the ability to perform Bell measurements across the two copies, the absolute expectation value of O, |o| = |Tr[ρO]| can be estimated using M ≥ C 4 × log(2/δ) measurements for any Pauli string O, owing to the fact that Bell states are eigenstates of any such O ⊗ O [7,8]. While this approach has the advantages that O need not be known beforehand, and that the number of measurements does not scale with the weight of the Pauli string, the disadvantages are that it is limited to O being a Pauli string, and that the scaling with the accuracy is worse than both classical shadows and de-randomized measurements (1/ 2 ). Moreover, to find the sign of the expectation value, additional measurements in the basis of O may be needed (requiring prior knowledge of O) [7].

B. State dependence of absolute and relative error
Classical shadows provides an efficient approach to measure expectation value of an operator O because of the independence of the bound on absolute error with the state ρ and the system size L (Eq.5). But often the relative error ( var(Tr[ρ s O])/Tr[ρO]) can be important as well, and estimates using classical shadows have a strong state dependence. Consider O to be a Pauli string of weight k, and a single site Clifford/Haar random unitary ensemble. Using our formula Eq. 6, the squared relative error is Therefore, the number of samples M required to achieve the same accuracy and confidence interval δ is given by  , with the standard deviation being roughly constant (blue circles), as the system size L varies. The standard deviation ofô is computed using 10 4 samples {ôm} generated from as many snapshots, for each L. Since the exact expectation value decreases exponentially in L, we see a roughly exponential increase in the relative error (with the dashed line as exponential guide). In the inset, the relative error is plotted for O = Zi, with the state given by The state dependence of the relative error is numerically examined in Figure 1, where we compare the relative error in the expectation value of O = Z i for the classical shadow of a typical Haar random state. The relative error increases with L, while the variance remains approximately constant. We also consider the relative error in Z acting only on the first qubit for the Here the expectation value Tr[ρZ 1 ] = 1 − 2/L increases with L sufficiently quickly that the relative error decreases with system size (in contrast with the Haar random case).
To summarize, the number of measurements required to achieve a certain accuracy in the relative error of the estimate of an expectation value depends on the state (Eq. 8), even when using other methods like de-randomized measurements (where M ≥ 1/(Tr[ρO] 2 2 ) log(2/δ)) [6] or Bell measurements on two copies of the state (where M ≥ 1/(Tr[ρO] 4 4 ) log(2/δ)) [7]. This is consistent with the general expectation in quantum simulation that the relative error arising from imperfect simulation is much larger than the absolute error [9]. C. Can we use shadows for time evolution?
As the classical shadow is a considerably more compact description of a given quantum state, it is interesting to ask if it can be time evolved to obtain a useful description of the quantum state at a later time. Colloquially, how well does the time evolved shadow approximate the shadow of the time evolved state?
Consider the time evolution of a state ρ with a time varying unitary V (t), generated from some underlying local dynamics through a Hamiltonian or a quantum circuit, which leads to the time evolved expectation value Thus depending on whether the dynamics are chaotic or many body localized or non interacting, the variance in the estimate of the expectation value grows exponen- In contrast the expectation value estimated by the classical shadow of the exact ρ(t) will be bounded by a "fixed" variance ∼ 4 k(0) . Of course as we noted earlier, the absolute error does have a weak state and, therefore, time dependence and the relative error will have a potentially much stronger time dependence. Nevertheless our analysis here indicates that time evolved shadows do not provide very good estimates of time dependent expectation values except in the case of non-interacting systems where they are not needed anyway. Bell measurements on two copies of the state can be used to estimate the absolute expectation value of an observable O in a time evolved state, such that |Tr[ is still a Pauli string, or equivalently, V (t) is a Clifford unitary. For such an evolution, var(|ô(t)|) ≤ 1, and the number of measurements required (M ≥ 1 4 log(2/δ)) does not depend on t, unlike Eq. 9. However, for generic/non-Clifford time evolution, O(t) does not remain a Pauli string and the estimation procedure of Ref. [7] ceases to be applicable.

D. Over-completeness
The representation of the density matrix in (2) has the form of an expansion of the density matrix in a basis of operators. In (2) the coefficients in the expansion are Born rule probabilities for measurement outcome b after the application of unitary U . However we now note that as an expansion (2) is not unique as the operator basis is overcomplete.
Let us spell this out in the simplest case, that of a single qubit state and the Haar random unitary ensemble. In this case (2) takes the explicit 2 × 2 matrix form This may be re-expressed as where p ± (n) ≡ p(1, n) ± p(−1, n). For a fixed ρ, there are many functions p ± (n) which satisfying this equation. Indeed, it is easy to show that Eq. 11 fixes only the l = 0 spherical harmonic of p + and the l = 1 spherical harmonic of p − ; all other harmonics are can be freely tuned while respecting Eq. 10. This lack of uniqueness of the expansion coefficients in Eq. 10 is not restricted to Haar random unitaries, but is applicable even when Clifford unitaries are used.

IV. HYBRID SHADOWS
We now consider a theoretical generalization of the notion of the classical shadow to a hybrid classical-quantum shadow: We measure some of the qubits but not all and keep an entangled quantum state on the remaining qubits ( Figure 2). The hybrid shadow can require fewer measurement rounds to achieve accurate estimates for certain observables (to be specified). On the other hand, the resulting hybrid shadow is comprised of a collection of states which will tend to have less entanglement (and require less memory to store) than the initial quantum state. Hybrid shadows may therefore provide a useful method for compressing a quantum state on a classical computer.
To form a hybrid shadow from initial state ρ, pick and fix a subsystem A (consisting of L A qubits), denoting its complement B. Rotate by a random unitary on A denoted by U A , and then measure A in the computational basis. The resulting snapshot is U † A |a a| U A ⊗ ρ B (a), where |a is the state (on subsystem A) after measurement in the computational basis, and ρ B (a) is the resulting unnormalized collapsed state on the remainder of the qubits which are not measured (not the reduced density matrix). The distribution of such collapsed states for many body chaotic systems is studied in [14]. The probability of measuring |a is given by quantum channel on the density matrix where the channel M is a superoperator acting only on subsystem A, and it may be invertible depending on the unitary ensemble. When it is invertible, a hybrid classical shadow is comprised of inverted snapshotŝ For unitaries which are acting on each site and are either Clifford/Haar random unitaries, the inverse map is simply implying that the corresponding part of the hybrid shadow in Eq. 13 can be efficiently stored and reconstructed on a classical computer. Similar to the classical shadow, Tr[ρ] = 1, however,ρ is not positive semidefinite.
With this inverse map, the bound on the variance of a Pauli string observable O with weight k can be shown to . We calculate the variance for a typical random product state (red triangles), a typical Haar state (green squares), and a GHZ state (blue dots) with L = 6, as LA is varied. Subsystem A is measured and is always taken to be the first LA qubits and i = 5, j = 6. The solid lines of the corresponding color represent the bound on the variance in Eq. 15, and is consistent with the computed variance for these states.
be [5] var with k(O A ) being the weight of the part of O on subsystem A. When k(O A ) = 0, even if k(O) is large, the variance is minimal and is given by 1 − ρ(O) 2 , and is demonstrated in Figure 3. On the other hand, note that the variance in Eq. 15 is at worst exponential in L A ; in contrast, the variance in the original shadow procedure (Eq. 6) could be exponential in total system size for long Pauli strings O. This means that hybrid shadows can lead to a reduction in the error in estimates for expectation values according to Eq. 5, when L A is smaller than L. Alternatively, if one knows the support of Pauli string O beforehand, hybrid shadows can lead to significantly reduced error by choosing A such that k(O A ) is minimal. Note that the improvement in variance by reducing L A , or increasing L − L A , comes at the cost of exponentially larger classical memory required to store the collapsed states on B.

A. Averaging over random choices of A
If information about O is not available beforehand, an optimal choice of A cannot be pre-determined. Therefore, for such general cases A can be randomly chosen as well. Picking L A qubits of A at random with a probability p(A), the map M(ρ) can be written as where by linearity of quantum channels, the term on the right is also a quantum channel. The variance of the estimate for the expectation value of a Pauli string observable with weight k can be obtained from Eq. 15 [5], and depends on the relation between k and L A . When L A k, var(ô) ≤ 3 k − ρ(O) 2 , as expected for example when all qubits are measured, on the other hand, when k L A , the upper bound on variance is only dependent on L A , as when A is fixed, given by 3 L A − ρ(O) 2 . For intermediate cases the bound can also be non-exponential, for example when

B. Time evolution and state dependence
The dependence of the variance in Eq. 15 prompts us to ask as an extension of the question about time evolution in section III C -how well does the time evolved hybrid shadow approximate the initial state when compared to the classical shadow. To that end, note again that the estimate of expectation value of O evolves according to how the operator spreads in time, since  2 , and starts to increase exponentially only after that, until again when the operator has fully spread in A, after which the bound on the variance saturates as ∼ 4 L A . This is in contrast to time evolving classical shadows, which after saturation according to Eq. 9 will accumulate exponential error in the full system size L. When the choice of A is random, we expect a similar saturation with L A , however the initial growth in the bound would start right away, as per the discussion in the previous section.
While the bounds on absolute error are only weakly dependent on the state, actual errors in the estimates of observables can provide more insight into the nature of hybrid shadows. To that end, we show in Figure 4, the dependence of the variance of the estimate of expectation value of X i for the ground state of transverse field Ising model, with the Hamiltonian H = − Z i Z i+1 − g X i , for L = 8 as the transverse field g is varied, for different L A (A chosen randomly), for a fixed number of samples (≈ 10 5 ). The variance is lower in the paramagnetic regime for all L A , and the change is most distinct when L A = L, due to E U,|a ô 2 being independent of state, and the only dependence with g comes from (E U,|a ô) 2 , where E U,|a denotes the average over measurements, unitaries and choice of A (a similar argument for O = Z would mean an increase in error with g). As L A is decreased the variance reduces as well (see discussion below Eq. 15), which makes sense since the shadow state becomes closer to the true state as L A is reduced to 0. The dependence of the variance with with g also becomes weaker. The maximum value of 3 when L A = L is also consistent with the bound in Eq.6. Together, they illustrate that the error in shadow estimates is sensitive to the phase of the ground state, and the number of qubits measured L A .

C. State approximation/compression
Hybrid shadows with randomly selected L A qubits can serve as a potential state approximation tool. While a general quantum state on L qubits requires a memory scaling as 2 L , hybrid shadows could in certain circumstances compactly approximate the quantum state. Storing a collection of M snapshots of the system Eq. The hybrid shadow becomes a better approximation to the original state as the number of samples in the shadow M increases. As before, the convergence with M is controlled by the snapshot-to-snapshot variance in the shadow estimate of the observable in question Eq. (15). It follows that the error in a Pauli observable O can be made small with probability ≥ 1 − δ by insisting that The ratio of total classical memory required to store the shadow states and the classical memory required to store the entire state is approximately given by M (L A + d B )/2 L , and when the expectation values of Pauli strings of weight k(O A ) on A are desired up to an accuracy with probability 1 − δ, the ratio scales as 3 k(O A ) (L A +d B ) 2 L log(2/δ)/ 2 in the large L limit. For small L A , d B ∼ 2 L , and low errors in the estimate of expectation values, the ratio can be quite large in practice. When k is small compared to L A the hybrid shadow approximation appears to be more memory efficient than storing the full state. On the other hand, when compared to the fully classical shadow (L A = L, d B = 0) more classical memory is required for storing a state using hybrid shadows, since the ratio of the memory required to classically store a hybrid shadow and a classical shadow is given by . For arbitrary O, the ratio is (L A + d B )/L and will generally be larger than one, but can be improved either by using approximation techniques for low entanglement states (such as a matrix product states) or by using standard compression techniques for arbitrary states [15,16]. Note that when a limited capacity quantum memory is available, the collapsed state on B can be stored optimally in a hybrid classical quantum memory, which can be another potential application of hybrid shadows.
Indeed, it is interesting to ask if there are classes of quantum states for which this thinning out of the quantum degrees of freedom stored in full, preserves greater accuracy than for other classes for which it does not. As a first test we have examined the ground states of the transverse field Ising model as the quantum fluctuations are varied. As is well known, the entanglement in the ground states peaks at the critical point. Somewhat surprisingly, in contrast to traditional state approximation methods like the matrix product states, there is remarkably little dependence on the entanglement of the state. This is supported in the inset of Fig.4, by computing the L 1 norm ||ρ −ρ s || for the estimated stateρ s using hybrid shadows for the transverse field Ising model, keeping the number of inverted snapshots M = 10 5 for all g. The norm appears largely independent of g, especially for larger L A , whereas for a matrix product state it is larger near the critical regime for fixed bond dimensions. However, analogous to Eq. 15 when generalized to global operators, reducing L A leads to an exponential reduction in the norm for a fixed number of snapshots.

V. DISCUSSION
We have commented on certain aspects of classical shadows from the viewpoint of many body physics. Unlike absolute errors in estimates of expectation values, relative errors can have a strong state dependence. Further, time evolution performed using classical shadows leads to an exponential buildup of errors in a generic many body system. Along the way, we also pointed out the freedom in writing down the expansion of a state using classical shadows. Finally, we introduced the idea of forming a hybrid quantum-classical shadow from measurements performed over some of the qubits instead of all, which can more accurately predict expectation values at the expense of requiring more quantum memory. These hybrid shadows could provide a way of thinking about the manner in which correlations of the state are captured, as more and more number of experiments are used to compute the shadow, and how it contrasts with traditional ways in which states are approximated. Such states could also potentially enhance the capabilities of near term quantum computers with limited number of qubits.

VI. ACKNOWLEDGEMENTS Appendix A: Hybrid shadows
Here we derive the results for hybrid shadows in greater detail. Consider starting with a state ρ defined on L qubits, and partitioning the system into subsystems A and B with number of qubits L A and L B . ρ is rotated using a random unitary U A acting on A such that the new state is U A ⊗ I B ρ U † A ⊗ I B , where I B is the identity on B. A measurement is then performed on A in the computational basis, resulting in the collapsed state |a . The un-normalized collapsed state on B is then given by The normalized state on the full system can then be written as |a a| ⊗ ρ B (a)/Tr B [ρ B (a)]. A snapshot of ρ is the state obtained after rotating back the subsystem A : U † A |a a| U A ⊗ ρ B (a). Note that the collapsed state on B is unchanged in this step. When averaged over the unitary ensemble and the measurement outcomes |a , M(ρ) defines a map acting on ρ via such that the probability of measuring |a cancels the normalization and the map only depends explicitly on the un-normalized state ρ B (a). In general, finding an inverse of the map M to reconstruct the state ρ is a difficult task, however, whenever the the unitaries are constructed that the classical shadow can be formed (or when all the qubits are measured), we can show that a hybrid shadow can be written down aŝ Noting that no operation is performed on the collapsed state on B. To see thatρ m reproduces ρ in expectation, expand ρ = r c r ρ r A ⊗ ρ r B , so that upon averaging the classical shadow on A reproduces ρ r A , and by linearity ρ is reproduced. For the case when U A is a product of on site Haar random unitaries U i , which we have specialized to in the main text, the hybrid shadow has the form (A6)

Variance of expectation values
First, let's consider the case when a fixed subsystem A is measured, and the Pauli string O has a decomposition O = O A ⊗ O B , and the expectation ρ(O) in state ρ. Denoting the estimate for the expectation value asô ≡ Tr(ρO), and the exact value as ρ(O), the variance can be written down as Where in the third line we have used the assumption of Pauli string O so that ρ(O) ≤ 1, whereas the last line can be derived either by assuming Haar random unitaries acting on each qubit and the explicit form for M −1 , or for general unitaries using the "shadow norm" defined in [2].
is obtained by solving the combinatorially equivalent problem of distributing L A distinct objects into 2 boxes of size k and L − k without replacement. The function f (k, L A , L) which is the first term on the right in the second equation is plotted for L = 20 and different k and L A . For L A = 1, it goes as 1 + 2k/L − ρ(O) 2 , for k = 1 as 1 + Here we provide generalizations of our results when global Clifford or Haar random unitaries U are applied on an unknown state ρ before performing measurements, followed by forming inverted snapshots. As noted in the main text, the inverted snapshot when all of the qubits are measured is given by  (1)) can be efficiently estimated using M ≥ C var(ô) 2 log(2/δ) samples with an accuracy and probability 1 − δ, independent of L. However, when estimating the expectation value of a Pauli string O, the variance scales with the system size L, independent of the weight of the Pauli string (ie. the number of qubits where the operator is not identity), such that var(ô m ) = 2 L + 1 − ρ(O) 2 , obtained from Eq. B3. This makes using this approach highly inefficient when compared to using local unitaries to form the shadow, where the variance only depends on the weight k of the Pauli string (Eq. 6). Based on this observation, we can arrive at the following conclusion about state dependence and time evolution : a. State dependence of absolute and relative error : Limiting ourselves to the case of O being a Pauli string, the relative error for the estimate of the expectation value of O has a dependence on the state given by Thus, even though the error does not change much with time, it scales exponentially in the system size L at all times. c. Hybrid shadows : Hybrid shadows obtained by applying a unitary U A on subsystem A comprising of L A qubits out of a total L qubits can be readily generalized from Sec IV when U A acting on A is a Clifford or Haar random unitary. When the measurement outcome on A is |a , the hybrid shadow in Eq. A4 can be simplified tô