How Hard Is It to Verify a Classical Shadow?

This work initiates the study of the natural question:

Given as input a “classical shadow” $S$, what is the complexity of verifying that $S$ actually “predicts” the measurement statistics of some $\rho$ against $P$?

As stated, this question is ill-posed, in the sense that we are not aware of a formal definition of a “classical shadow” in the literature. Thus, to remedy this, we first provide a general formal definition:

This definition says nothing about prediction accuracy; it simply formalizes the idea that a “classical shadow” is a multi-set of strings $S$, in principle obtained via some set of efficient measurements on copies of a physical state $\rho$, coupled with a set of target observables $O$ and an efficient recovery procedure $A$ for “extracting predictions”. An alternate possible definition might be not to give shadow $S$ as a fixed sequence of strings, but rather to generate $S$ on-the-fly by sampling from some unknown distribution (thus capturing the idea of measurement bases $𝒰$ as in HKP). In the full version [23], we formalize this sampled-shadow variant and show the complexity of verifying “classical shadows” versus “sampled classical shadows” is equivalent under randomized reductions. For simplicity, we thus work with Definition 1.1, as its input model is the standard one used in (e.g.) BQP and QMA.

Moving on, the task of checking the validity of a shadow, i.e., that the outputs of $A$ correctly predict measurement statistics, is formalized as:

The theme of this work is to characterize the complexity of this problem and its variants, including for the HKP protocol with local Clifford measurements, “dequantization” results for global Clifford measurements, and the case of exponentially many observables.

Before proceeding, the reader familiar with quantum complexity theory may notice that, at least in the setting of polynomially many observables $O_i$, CSV is eerily similar to the QMA-complete CONSISTENCY problem of Liu [27]. In the latter, the input is a set of $k$-local reduced states ${\rho }_i$ acting on a subset $S_i$ of $k\in O(1)$ out of $n$ qubits each, and the question is whether there exists an $n$-qubit state $\rho$ such that for all $i$, ${\mathrm{Tr}}_{[n]\setminus S_i}(\rho )\approx {\rho }_i$? Indeed, as our definition of classical shadows is intentionally very general, it includes as a special case the CONSISTENCY problem. From this, one immediately obtains that CSV is at least QMA-hard (Corollary 3.7). This is not the point of this paper!

The point is that classical shadow protocols used in practice typically do not produce local density operators as in CONSISTENCY, but rather highly non-local snapshots (e.g. $n$-local operators which are the tensor product of $n$ non-trivial single qubit states)! Our goal is thus to characterize the complexity of CSV for precisely these experimentally relevant snapshots, to which the QMA-hardness of CONSISTENCY does not obviously apply. Indeed, as will be discussed shortly, a reduction from CONSISTENCY to CSV will have to overcome the well-known challenging problem of how to construct a global quantum snapshot from local overlapping reduced density operators (as in CONSISTENCY).

(1) As near-term experimental devices remain noisy, verifying that a device actually outputs the state intended remains a major challenge. Well-known examples include verification of quantum advantage experiments such as Random Circuit Sampling [6] or Boson Sampling [2, 20]. In the same vein, it is arguably important to verify the validity of snapshots output by classical shadow experiments; this is true even if the experimenter fully trusts that the device has not been tampered with. More generally, in the distributed cloud setting where the user does not trust the device, CSV becomes yet more crucial.

(2) The study of $\mathrm{𝖢𝖲𝖵}$ is important to the study of classes $\mathrm{𝖰𝖬𝖠}$ versus $\mathrm{𝖰𝖢𝖬𝖠}$ (i.e. $\mathrm{𝖰𝖬𝖠}$ with a classical proof [5]), as it underpins the central open question of whether quantum witnesses are fundamentally more powerful than classical ones. Specifically, if a QMA verifier’s measurement falls into a class of observables $O$ whose output statistics could be efficiently predicted by poly-size classical shadows, and if CSV for said shadows could be solved by a (uniformly generated) poly-time quantum circuit, then $\mathrm{𝖰𝖬𝖠}=\mathrm{𝖰𝖢𝖬𝖠}$, which would be a breakthrough.

(3) We further motivate the study of $\mathrm{𝖢𝖲𝖵}$ by framing it as a natural quantum analogue of the classical Sparse Representation problem ($\mathrm{𝖲𝖱}$) under the lens of classical shadow protocols. In $\mathrm{𝖲𝖱}$, one has to decide if a sparse vector, consistent with a given measurement sketch, exists. While $\mathrm{𝖲𝖱}$ is $\mathrm{𝖭𝖯}$-hard in the general case [12], it becomes efficiently solvable (via convex relaxation) when the measurement matrix satisfies the Restricted Isometry Property (RIP) [9]. In the quantum setting an analogous compressed sensing phenomenon is known: under a low-rank promise on the state and suitable measurements, convex programs can efficiently reconstruct the state [17]. Our work studies the quantum SR question arising in the classical shadow framework, [1, 21].

We organize our discussion⁵⁵5We remark that although we gave a fully general formal definition of classical shadows (Definition 1.1), most of our results are actually independent of the specific recovery algorithm $A$ employed therein; thus, behind the scenes we often work with a simpler restatement of CSV, denoted Observable Consistency ($\mathrm{𝖮𝖻𝗌𝖢𝗈𝗇}$, Definition 3.1). Hence, while we informally state our results in terms of CSV here, our formal statements are often in terms of $\mathrm{𝖮𝖻𝗌𝖢𝗈𝗇}$. in terms of (1) polynomially many observables, (2) exponentially many observables, and (3) further variants of $\mathrm{𝖢𝖲𝖵}$ with connections to $\mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})$. For clarity, our main results involve (1) and (2). All hardness results are under poly-time many-one reductions.

1. Polynomially many observables: Hardness and dequantization. As previously stated, it is not difficult to see that $\mathrm{𝖢𝖲𝖵}$ in its most general form is QMA-complete (Corollary 3.7). Here, we focus on the more challenging case of the HKP protocol [21] (instantiated with either local or global Clifford measurements), as well as a high-dimensional generalization thereof due to Mao, Yi and Zhu (MYZ) for odd-prime local dimension $d$ [29].

To begin, we define ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖧𝖪𝖯}}$ as CSV for the HKP protocol instantiated with local Clifford measurements (Definition 4.2); roughly, the elements of $S$ are $n$-bit strings, conjugated by Pauli strings in ${\{X,Y,Z\}}^n$, and the observables are $k$-local Pauli strings for $k\in O(1)$. We show the following statement.

In words, deciding if a given HKP classical shadow based on local Clifford measurements is valid is intractable, even when the observables are $6$-local and essentially arranged on a line (formally on a spatially sparse hypergraph (in the sense of Ref. [31]; Definition 2.1)). Specifically, the hardness construction may be viewed as 1D nearest-neighbor on qudits of dimension $8$. Each qudit is then decomposed into $3$ qubits, and neighboring pairs of qudits $(q_i,q_{i+1})$ have a $6$-local observable acting jointly on their constituent qubits.

Defining ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖬𝖸𝖹}}$ (Definition 4.9) analogously for MYZ on odd prime local dimensions $d$, we next show:

Here, since we are allowed to work with larger $d$, we cleanly obtain hardness with all observables acting on pairs of nearest neighbor qudits $(q_i,q_{i+1})$.

Finally, we study CSV for the HKP protocol instantiated with global Clifford measurements, denoted ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖦𝖢}}$ (Definition 4.12). We show a “dequantization” result as follows, for Frobenius norm ${\Vert A\Vert }_F=\sqrt{\mathrm{Tr}(A^{†}A)}$:

First, while the Frobenius norm bound above may a priori seem strong, this setting captures natural tasks such as (e.g.) fidelity estimation against pure and low rank states [21]. Moreover, the global Clifford HKP protocol itself is efficient precisely in this regime, i.e. when ${\Vert O_i\Vert }_F\le \text{poly}(n)$, coinciding with the regime in which Theorem 1.5 dequantizes ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖦𝖢}}$. By a similar argument, this “dequantization” result extends to the MYZ protocol with global Clifford measurements, under the same assumptions (Theorem 4.21). Second, we dub this a “dequantization” result, in that conditions (a) and (b) are those in previous dequantization works, e.g., Tang [32] and Chia, Gilyén, Li, Lin, Tang and Wang [10], allowing randomized linear algebra techniques to be employed.

2. Exponentially many observables. We next consider CSV with exponentially many observables. Although a priori this setting may seem unrealistic, King, Gosset, Kothari and Babbush gave [24] an explicit polynomial-sample complexity shadow protocol for the set of all $4^n$ Pauli string observables, ${\{I,X,Y,Z\}}^n$. (Note the time complexity is still exponential, but in our setting, we do not produce the shadow, but receive it as input; thus, this overhead is not relevant.) What is also relevant is that Ref. [24] gives a poly-time recovery algorithm for the observable expectations, assuming one only demands constant additive error. We show the following statement.

Let us discuss strengths and weaknesses: The strengths are that (1) the result holds even if one need only recover constant precision approximations of observable predictions, and (2) Theorem 1.6 yields the first natural complete problem for a quantum generalization of (a level of) the polynomial hierarchy (PH). Specifically, $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$ (Definition 2.8) is a quantum generalization of ${\mathrm{\Sigma }}_2^p$, the second level of PH, in which the first proof is a mixed quantum state, the second a classical string, and the verifier is quantum. We remark this is the first work studying $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$, though other variants of quantum PH have been studied in previous works [13, 14, 16, 3]. The weakness is that, unlike Theorem 1.3, we do not prove the result for the specific observable set of Ref. [24], i.e., for ${\{I,X,Y,Z\}}^n$.

3. Further variants of $\mathrm{𝖢𝖲𝖵}$ and connections to $\mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})$. For completeness, we also show the following for variants of $\mathrm{𝖢𝖲𝖵}$:

1. 1.

   CSV where the consistent state must be product, i.e., $\rho ={\rho }_A\otimes {\rho }_B$, is $\mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})$-complete⁶⁶6$\mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})$ is QMA, but where the proof is promised to be in tensor product [26]. for polynomially many observables, and $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}(\mathrm{𝟤})$-complete (Definition 2.9) for exponentially many observables. As an intermediate step, the proof shows that $\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}{(\mathrm{𝟤})}_{\text{poly}}=\mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})$, where $\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}{(\mathrm{𝟤})}_{\text{poly}}$ is a product state generalization of ${\mathrm{𝖰𝖬𝖠}}^{+}$ from Ref. [4].

2. 2.

   Verifying if a set of classical shadows, each possibly with different observables, all correspond to the same state $\rho$ is QMA-complete and $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$-complete for polynomially many and exponentially many observables, respectively.

For these results see the full version of the paper [23].

We focus on QMA-completeness of ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖧𝖪𝖯}}$ (Theorem 1.3) and completeness for $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$ of CSV with exponentially many observables (Theorem 1.6).

QMA-completeness of ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖧𝖪𝖯}}$. Ideally, we wish to reduce the QMA-complete CONSISTENCY problem on $k$-local reduced density operators ${\rho }_i$ to ${\mathrm{𝖢𝖲𝖵}}_{\mathrm{𝖧𝖪𝖯}}$. The challenge? Each ${\rho }_i$ acts on only $k$-qubits. HKP classical shadows with local Clifford measurements, on the other hand, have shadow elements $s_i$ which are highly non-local – each $s_i$ is an $n$-qubit tensor product of eigenvectors of single-qubit Pauli matrices. And “stitching” together local information, i.e., the ${\rho }_i$, to obtain globally consistent information, i.e., the $s_i$, is a difficult task, reminiscent of the quantum marginal problem.

To overcome this requires a series of steps. First, we start with the 1D CONSISTENCY problem on qudits, so that it suffices to stitch together nearest neighbor reduced states $({\rho }_{i,i+1},{\rho }_{i+1,i+2})$ on the line. To this end, we first show⁷⁷7One could alternatively use the 1D CONSISTENCY QMA-hardness result of Liu [28], but this would only yield hardness under Turing reductions, not many-one reductions. QMA-completeness of 1D CONSISTENCY with local dimension $d=8$ via many-one reduction by combining the locally simulatable technique of Broadbent and Grilo [8] with the QMA-complete result for the 1D Local Hamiltonian problem with $d=8$ of Hallgren, Nagaj, and Narayanaswami [19]. Then, we take the local nearest-neighbor reduced states ${\rho }_i$ on qu-$8$-its from 1D CONSISTENCY, decompose each qudit $q_i$ into a triple of qubits $T_i$, and consider all possible $6$-local HKP shadows on pairs $(T_i,T_{i+1})$. Crucially, we know under the HKP protocol that any valid local shadow’s expectation should exactly recover the corresponding state ${\rho }_i$. Using this fact and our 1D setup, we derive a linear program (LP) which captures “how much weight/probability” to put onto each local shadow, so that the “local probabilities” are consistent with some global HKP shadow if and only if the 1D CONSISTENCY instance we started with is a YES instance.

Unfortunately, solving this LP is itself not enough, because we next need to simulate the probability of a local shadow $s_j$ occurring when measuring local Cliffords in HKP by repeating $s_j$ an appropriate integer number of times in our shadow set $S$. We must, in fact, do this exactly to ensure consistency, and so we next “round” our LP into an integer program (IP) to give us integer weights on local shadows. This raises the potential roadblock that solving integer programs is NP-hard, but here we again crucially use the fact that we are working in 1D. Specifically, we exploit the 1D structure to design an efficient dynamic program to solve the IP, obtaining the desired integer weights on local shadows. Finally, we construct a list of global shadows by repeatedly carefully stitching together strings of local shadows under appropriate permutations given by a perfect matching.

$\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$-completeness of CSV with exponentially many observables. To connect $\mathrm{𝖢𝖲𝖵}$ with $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$, we first go through the ${\mathrm{𝖰𝖬𝖠}}^{+}$ formalism of Aharonov and Regev [4]. Roughly, in the latter one is given a set of polynomially many measurements ${\mathrm{\Pi }}_i$ and targets $r_i\in ℝ$, and asked if there is a state $\rho$ such that $\mathrm{Tr}({\mathrm{\Pi }}_i\rho )\approx r_i$. While Aharonov and Regev showed ${\mathrm{𝖰𝖬𝖠}}^{+}=\mathrm{𝖰𝖬𝖠}$, here we define the analogous class with exponentially many ${\mathrm{\Pi }}_i$, denoted ${\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}}_{\text{exp}}$. We then prove CSV with exponentially many observables is ${\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}}_{\text{exp}}$-complete, and subsequently show that ${\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}}_{\text{exp}}=\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$ to complete the proof. Intuitively, the latter holds because the existential quantum proof provides the globally consistent state, and the universal classical proof allows the verifier to iterate through all exponentially many measurement checks.

We have initiated the study of the complexity of verifying classical shadows. For hardness, an important open question is whether other specific classical shadow protocols and observable sets have QMA-hard CSV problems? In the case of exponentially many observables, for example, can one give a $\mathrm{𝗊𝖼}\text{-}{\mathsf{\Sigma }}_{\mathrm{𝟤}}$-completeness proof of CSV for the protocol of King, Gosset, Kothari and Babbush [24]? The main bottleneck we faced here was that, unlike in our proof for HKP with polynomially many observables (Theorem 1.3), it is not clear how to start from an “exponential size” analogue of the QMA-complete 1D CONSISTENCY problem. A natural idea might be to start with translationally invariant 1D systems [15]. Such systems, however, act on exponentially many qudits, whereas our setting requires polynomially many qubits – the exponentiality occurs only in the number of observables for CSV. Finally, are there instances of CSV aside from our HKP, MYZ global Clifford results which can also be dequantized, or even better, solved classically without sampling assumptions?

Section 2 begins with preliminaries, including reviews of the HKP and MYZ classical shadow protocols. Section 3 studies the general CSV problem (i.e., not restricted to any particular shadow protocol), including the case of exponentially many observables. Finally, Section 4 studies the HKP and MYZ protocols, showing QMA-hardness and our dequantization result.

We use $A\le B$ and $A{\le }_{r}B$ to denote poly-time deterministic many-one and poly-time randomized reductions from $A$ to $B$, respectively.

Note our definition allows exponentially many checks, so long as each check can be efficiently generated on demand. We further remark that our definition ${\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}}_{\text{poly}}$, i.e., with $m=\text{poly}(|x|)$, coincide with ${\mathrm{𝖰𝖬𝖠}}^{+}$ from Ref. [4]. However, to the best of our knowledge, our ${\mathrm{𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠}}_{\text{exp}}$ with $m=\text{exp}(|x|)$ has not been considered elsewhere before.

In quantum mechanics, an observable is represented by a Hermitian operator $O$. Its real eigenvalues correspond to the possible outcomes of a measurement. Throughout this work, we assume without loss of generality that all observables $O_i$ are normalized such that their operator norm $\Vert O_i\Vert \le 1$.

When we say that we assume succinct access to a set ${\{A_i^{(n)}\}}_{i=1}^m$, with $n$ the natural size parameter of the instance (e.g., number of qubits for observables or precision parameter for a real value), we mean that given an index $i$, a $\text{poly}(n)$-bit description of $A_i$ can be produced in $\text{poly}(n)$-time.

Here we briefly describe a classical shadow protocol proposed by Huang, Kueng and Preskill in Ref. [21]. For an unknown $n$-qubit state $\rho$ fix an ensemble $𝒰$ of unitaries on $n$ qubits. In each round do the following: sample $U\sim 𝒰$, measure $U\rho U^{†}$ in the computational basis to get a bitstring $b_{\mathrm{\ell }}\in {\{0,1\}}^n$, and store a succinct classical description of $U_{\mathrm{\ell }}^{†}|b_{\mathrm{\ell }}⟩⟨b_{\mathrm{\ell }}|U_{\mathrm{\ell }}$. The average channel

is invertible for tomographically complete $𝒰$, so a single-shot snapshot is

For any observable $O$ we use ${\widehat{o}}_{\mathrm{\ell }}(O):=\mathrm{Tr}[O{\widehat{\rho }}_{\mathrm{\ell }}]$. Partition the $L$ rounds into $K$ blocks $B_1,\mathrm{\dots },B_K$ of (nearly) equal size, set

Since $𝔼[U_{\mathrm{\ell }}^{†}|b_{\mathrm{\ell }}⟩⟨b_{\mathrm{\ell }}|U_{\mathrm{\ell }}]=ℳ(\rho )$, linearity gives $𝔼[{\widehat{\rho }}_{\mathrm{\ell }}]=\rho$ and thus $𝔼[{\widehat{o}}_{\mathrm{\ell }}(O)]=\mathrm{Tr}(O\rho )$ (unbiased). The median of means provides robustness. We need

samples to estimate $M$ observables up to error $ϵ$.

Here $𝒰=\mathrm{Cl}{(2)}^{\otimes n}$. Per round, sample independent single-qubit Cliffords $U_{j,\mathrm{\ell }}$ (equivalently, pick Pauli bases $P_{j,\mathrm{\ell }}\in \{X,Y,Z\}$) and measure to get bits $x_{j,\mathrm{\ell }}$. Store the measurement record

The average channel factorizes as $ℳ=D_{1/3}^{\otimes n}$ with inverse $D_{1/3}^{-1}(A)=3A-\mathrm{Tr}(A)I_2$, hence the snapshot factorizes sitewise as

where $|{\psi }_{j,\mathrm{\ell }}⟩:=U_{j,\mathrm{\ell }}^{†}|x_{j,\mathrm{\ell }}⟩$ an eigenvector of $X$ or $Y$ or $Z$. To estimate $M$ $k$-local observables up to error $ϵ$, it suffices to take $L=𝒪\left(\frac{\log M}{{ϵ}^2}{\max }_i{4}^k{\Vert O_i\Vert }_{\mathrm{\infty }}^2\right)$ rounds.

Here $𝒰=\mathrm{Cl}(2^n)$. Per round, sample $U_{\mathrm{\ell }}\in \mathrm{Cl}(2^n)$ uniformly at random and measure to get $b_{\mathrm{\ell }}$. Store the measurement record as $s_{\mathrm{\ell }}=({\mathrm{𝖲𝗍𝖺𝖻}}_{\mathrm{\ell }},b_{\mathrm{\ell }})$ where $\mathrm{𝖲𝗍𝖺𝖻}$ is the efficient classical representation of the global Clifford via the stabilizer formalism and $b\in {\{0,1\}}^n$ the measurement outcome of that round. The average channel is the global depolarizing map

so the snapshot is ${\widehat{\rho }}_{\mathrm{\ell }}=(2^n+1)|{\psi }_{\mathrm{\ell }}⟩⟨{\psi }_{\mathrm{\ell }}|-I_{2^n}$. To estimate $M$ linear observables, one needs $L=𝒪\left(\frac{\log M}{{ϵ}^2}{\max }_i\mathrm{Tr}(O_i^2)\right)$ rounds.

Mao, Yi and Zhu [29] extend the HKP classical-shadow protocol to $n$ qudits of odd prime local dimension $d$. Let ${𝔽}_d$ be the finite field with $d$ elements and $\omega =e^{2\pi i/d}$ a primitive $d$-th root of unity. Fix an ensemble $ℰ$ of unitaries on $n$ qudits. In each round: sample $U\sim ℰ$, measure $U\rho U^{†}$ in the computational basis to get an outcome $b_{\mathrm{\ell }}\in {𝔽}_d^n$, and store a succinct classical description of $U_{\mathrm{\ell }}^{†}|b_{\mathrm{\ell }}⟩⟨b_{\mathrm{\ell }}|U_{\mathrm{\ell }}$. The average channel

is invertible for tomographically complete $ℰ$, so a single-shot snapshot is

For any observable $O$ we use ${\widehat{o}}_{\mathrm{\ell }}(O):=\mathrm{Tr}[O{\widehat{\rho }}_{\mathrm{\ell }}]$. Partition the $L$ rounds into $K$ blocks and take the median of block-means (rounded to $\chi$ bits) as before. Since $𝔼[U_{\mathrm{\ell }}^{†}|b_{\mathrm{\ell }}⟩⟨b_{\mathrm{\ell }}|U_{\mathrm{\ell }}]=ℳ(\rho )$, linearity gives $𝔼[{\widehat{o}}_{\mathrm{\ell }}(O)]=\mathrm{Tr}(O\rho )$ (unbiased). Again,

samples suffice to estimate $M$ observables up to error $ϵ$.

Here $ℰ=\mathrm{Cl}{(d)}^{\otimes n}$. Per round, sample independent single-qudit Cliffords $U_{j,\mathrm{\ell }}$ (equivalently, pick on each site one of the $d+1$ stabilizer bases and measure there). Store the measurement record $s_{\mathrm{\ell }}=(({\mu }_{1,\mathrm{\ell }},b_{1,\mathrm{\ell }}),\mathrm{\dots },({\mu }_{n,\mathrm{\ell }},b_{n,\mathrm{\ell }}))$, where ${\mu }_{j,\mathrm{\ell }}\in {𝔽}_d\cup \{\mathrm{\infty }\}$ labels the basis ($\mu =\mathrm{\infty }$: $Z$-eigenbasis; $\mu =t\in {𝔽}_d$: eigenbasis of $Z^{t}X$) and $b_{j,\mathrm{\ell }}\in {𝔽}_d$ is the outcome label. The average channel factorizes as $ℳ=D_{1/(d+1)}^{\otimes n}$ with inverse $D_{1/(d+1)}^{-1}(A)=(d+1)A-\mathrm{Tr}(A)I_d$, hence the snapshot factorizes sitewise:

where $|{\varphi }_{\mu ,a}⟩$ is the eigenvector in the chosen stabilizer basis. To estimate $M$ $k$-local observables up to error $ϵ$, it suffices to take $L=𝒪\left(\frac{\log M}{{ϵ}^2}{\max }_i{d}^{2k}{\Vert O_i\Vert }_{\mathrm{\infty }}^2\right)$.

Here $ℰ=\mathrm{Cl}(d^n)$. Per round, sample $U_{\mathrm{\ell }}\in \mathrm{Cl}(d^n)$ uniformly at random and measure to get $b_{\mathrm{\ell }}\in {𝔽}_d^n$. Store the measurement record: $s_{\mathrm{\ell }}=({\mathrm{𝖲𝗍𝖺𝖻}}_{\mathrm{\ell }},b_{\mathrm{\ell }})$, where $\mathrm{𝖲𝗍𝖺𝖻}$ is the efficient classical representation (via stabilizer formalism) of the global Clifford and $b$ the $d$-ary outcome string. The average channel is the global depolarizing map

so the snapshot is ${\widehat{\rho }}_{\mathrm{\ell }}=(d^n+1)|{\psi }_{\mathrm{\ell }}⟩⟨{\psi }_{\mathrm{\ell }}|-I_{d^n}$. To estimate $M$ linear observables, one needs $L=𝒪\left(\frac{\log M}{{ϵ}^2}{\max }_i[(2d-3)\mathrm{Tr}(O_i^2)+2{\Vert O_i\Vert }_{\mathrm{\infty }}^2]\right)$ rounds.

Both directions are straightforward

• $\mathrm{■}$

  $\mathrm{𝖢𝖲𝖵}\le \mathrm{𝖮𝖻𝗌𝖢𝗈𝗇}$. Keep the same observables and define $y_i:=A(S,i)$.

• $\mathrm{■}$

  $\mathrm{𝖮𝖻𝗌𝖢𝗈𝗇}\le \mathrm{𝖢𝖲𝖵}$. Keep the same observables, use a dummy shadow $S$ and a recovery algorithm $A(S,i)$ that ignores $S$ and outputs $y_i$.

$◀$ We will analyze the complexity of this problem in two regimes, distinguished by the number of observables $m$.