# Classical shadows based on locally-entangled measurements

Matteo Ippoliti  Department of Physics, Stanford University, Stanford, CA
94305, USA

###### Abstract

We study classical shadows protocols based on randomized measurements in
$n$-qubit entangled bases, generalizing the random Pauli measurement protocol
($n=1$). We show that entangled measurements ($n\geq 2$) enable nontrivial and
potentially advantageous trade-offs in the sample complexity of learning Pauli
expectation values. This is sharply illustrated by shadows based on two-qubit
Bell measurements: the scaling of sample complexity with Pauli weight $k$
improves quadratically (from $\sim 3^{k}$ down to $\sim 3^{k/2}$) for many
operators, while others become impossible to learn. Tuning the amount of
entanglement in the measurement bases defines a family of protocols that
interpolate between Pauli and Bell shadows, retaining some of the benefits of
both. For large $n$, we show that randomized measurements in $n$-qubit GHZ
bases further improve the best scaling to $\sim(3/2)^{k}$, albeit on an
increasingly restricted set of operators. Despite their simplicity and lower
hardware requirements, these protocols can match or outperform recently-
introduced “shallow shadows” in some practically-relevant Pauli estimation
tasks.

##  1 Introduction

Classical shadows are a powerful method to learn many properties of unknown
quantum states with a relatively low number of measurements [1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]. This is an important task in light
of the advent of programmable quantum simulators capable of preparing
increasingly complex quantum states, whose experimental characterization and
classical description may be challenging [18, 19, 20, 21]. Classical shadows
are based on randomized measurements [22, 23, 2]: the unknown state of
interest is measured in a large number of different bases, randomly chosen
from a suitable ensemble, and the resulting classical data is stored and
processed to predict properties of the state.

Different choices for the ensemble of random untiary rotations yield different
flavors of classical shadows, each of which may be best suited to the
prediction of different properties [1]. Arguably the most practically-relevant
example is the random Pauli ensemble, where each qubit is measured in a
randomly-chosen $X$, $Y$ or $Z$ basis; this requires only single-qubit random
rotations on the hardware and is well suited to learning e.g. the expectation
value of $k$-local operators. Another important example is the random Clifford
ensemble, where the basis is randomized by a global Clifford operation; this
allows efficient estimation of fidelities and low-rank operators. Intermediate
schemes dubbed shallow shadows have been recently introduced [24, 25, 26, 27].
These randomize the basis by means of variable-depth circuits, thus
interpolating between random Pauli and random Clifford measurements.

In this work, we introduce a family of protocols that interpolates between
locally- and globally-random measurements in a different way, by tuning the
locality of subsystems on which entangled measurement bases are allowed. The
protocols are hardware-efficient, requiring only few-body entanglement, and
the classical post-processing is likewise simple. Nonetheless, they can
outperform random Pauli shadows and even shallow shadows in some Pauli
estimation tasks of practical interest, making them a useful addition to the
randomized measurement toolbox.

###  1.1 Review

In general, given an ensemble of random unitaries, the classical shadows
protocol is as follows. A quantum state of interest $\rho$ on $N$ qubits is
transformed under a unitary $U$ drawn from the ensemble. It is then measured
in the computational basis yielding a bitstring $b$. The pairs $\\{(U,b)\\}$
of basis choice and measurement outcome represent classical data that can be
used to efficiently construct a compressed description of the state. Namely
one builds “snapshots” $\hat{\sigma}=U^{\dagger}\outerproduct{b}{b}U$ which in
expectation are related to the state of interest $\rho$ by a channel
$\mathcal{M}$, called the shadow channel:
$\mathbb{E}[\hat{\sigma}]=\mathcal{M}(\rho)$. From this, one defines “inverted
snapshots” $\hat{\rho}=\mathcal{M}^{-1}(\hat{\sigma})$ which by construction
yield $\rho$ in expectation [1]. The set of inverted snapshots
$\\{\hat{\rho}_{i}\\}_{i=1}^{K}$ (obtained over $K$ iterations fo the quantum
experiment) is a classical shadow of $\rho$ of size $K$.

The practical usefulness of classical shadows depends on the sample complexity
of various estimation tasks, i.e., how many experimental shots are needed in
order to predict a given property of $\rho$ to a fixed (additive) accuracy
$\epsilon$ with high probability. For predicting $M$ linear functions (i.e.
expectation values of a set of operators $\\{O_{i}\\}_{i=1}^{M}$), this is
bounded above by $\log(M)\max_{i}\|O_{i}\|_{\rm sh}^{2}/\epsilon^{2}$ [1],
where $\|\cdot\|_{\rm sh}$ is a norm determined by the measurement protocol,
called the shadow norm. For a Pauli operator $P$ in an $N$-qubit system,
assuming Pauli invariance of the measurement ensemble [11], the shadow norm is
given by

$\|P\|_{\rm sh}^{2}=\frac{1}{2^{N}}\Tr(P\mathcal{M}^{-1}(P)),$ (1)

independent of the state $\rho$. For random Pauli measurements, the shadow
channel factors into single-qubit depolarizing channels
$\mathcal{M}=\mathcal{E}_{1}^{\otimes N}$, with
$\mathcal{E}_{1}(\sigma^{\alpha})=\lambda_{\alpha}\sigma^{\alpha}$ and
eigenvalues

$\lambda_{\circ}=1,\qquad\lambda_{\bullet}=\frac{1}{3},$ (2)

where $\circ$ denotes the identity ($\alpha=0$) and $\bullet$ stands for
$\alpha\in\\{x,y,z\\}$. It follows that $\|P\|_{\rm
sh}^{2}=\lambda_{\circ}^{k-N}\lambda_{\bullet}^{-k}=3^{k}$, where $k$ is the
weight of operator $P$, i.e., the number of qubits on which it acts
nontrivially [1].

A simple way to understand this scaling is that there are three possible basis
choices ($X$, $Y$ or $Z$) per site, sampled randomly in each experimental run.
Only some basis choices are useful towards the estimation of a Pauli
expectation value $\langle P\rangle$. In particular, only measurement bases
that correctly match all nontrivial Pauli matrices in $P$ contribute to its
estimation (in the language of Ref. [28], we say such measurements “hit” $P$).
As only one in $3^{k}$ bases “hits” $P$, estimating $\langle P\rangle$ to
accuracy $\epsilon$ requires of order $3^{k}/\epsilon^{2}$ iterations of the
experiment.

It is known on information-theoretic grounds [1] that the scaling of $3^{k}$
is optimal in general. However, it is possible to improve performance on
certain Pauli operators at the expense of others. For example, shallow shadows
[24, 25] were shown to achieve a scaling of $\sim k2^{k}$ (when tuned to a
$k$-dependent optimal depth) for Pauli operators with contiguous support in
one dimension [27], while typically performing worse on operators with a
sparse support. Such trade-offs may be worthwhile in many cases, given the
importance of geometric locality in many-body physics. The protocols we
introduce in this work feature a similar trade-off, with very favorable
performance on a physically-relevant class of operators obtained at the
expense of the learnability of other operators.

[width=]fig0.pdf

Figure 1: Schematic of the Bell shadows protocol. (a) Unknown state $\rho$ is
locally scrambled with random single-qubit Clifford gates (colored squares),
then pairs of neighboring qubits are measured in the Bell basis (shown as a
sequence of CZ, Hadamard and computational basis measurements). (b) Bell
measurements define a dimer covering of the lattice (ellipses). An operator is
compatible with the covering if its support intersects each dimer on 0 or 2
sites (green), incompatible otherwise (red). Bell shadows only learn
compatible operators.

##  2 Bell shadows

###  2.1 Protocol

We begin by introducing a variant of the random Pauli measurement protocol
based on two-qubit measurements in the Bell basis. The protocol requires first
to choose a grouping of the qubits into pairs (we assume the number of qubits
$N$ is even). For concreteness, we take this pairing to be geometrically-local
on an underlying lattice, and thus refer to this as a dimer covering of the
lattice; however geometric locality is not necessary. The protocol then
involves the following steps, illustrated in Fig. 1(a):

  1. (i)

“Locally scramble” the state, $\rho\mapsto U\rho U^{\dagger}$ with
$U=\bigotimes_{i=1}^{N}u_{i}$, each $u_{i}$ being a random Clifford gate;

  2. (ii)

Measure each pair of qubits in the Bell basis;

  3. (iii)

Build the classical shadow according to the standard prescription [1].

In Fig. 1(a), the Bell measurement [step (ii)] is compiled as a sequence of
CZ, Hadamard and $X$-basis measurements. CZ is the controlled-$Z$ gate,
$\textsf{CZ}=\textsf{diag}(1,1,1,-1)$; it is a Clifford operation that maps
the Pauli-$X$ basis to the basis stabilized by $\pm X_{1}Z_{2}$, $\pm
Z_{1}X_{2}$. This basis, up to local unitary transformations (which may be
absorbed into the local scrambling step), is equivalent to the standard Bell
basis stabilized by $\pm X_{1}X_{2}$, $\pm Z_{1}Z_{2}$, i.e. the basis vectors
$\\{\ket{\Phi^{\alpha}}:\alpha=0,x,y,z\\}$, with
$\ket{\Phi^{0}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ and
$\ket{\Phi^{\alpha}}=(\sigma^{\alpha}\otimes I)\ket{\Phi^{0}}$.

[width=0.8]fig_dimer_coverings.pdf

Figure 2: Use cases of Bell shadows, Sec. 2.3. The graphical conventions are
as in Fig. 1(b): blue ellipses denote dimers whose qubits are measured in a
Bell basis, green operators are compatible with the given dimer covering and
thus learnable, red operators are incompatible and not learnable. (a) Pauli
string operators in 1D chains. All operators of even length are learnable by
sampling two distinct dimer coverings of the chain (left and right). (b)
Plaquette operators of a honeycomb system (e.g. color code stabilizers). The
dimer covering in the picture is compatible with two thirds of all hexagonal
plaquettes; the remaining ones may be learned by translating the dimer
covering by one lattice vector. (c) Multi-point functions of two-body
operators.

###  2.2 Sample complexity

The sample complexity of learning the expectation value of a Pauli operator
$P$ via this protocol is determined by the shadow norm $\|P\|_{\rm sh}^{2}$.
This can be analyzed in analogy with the random Pauli measurement protocol
[1], by noting that the shadow channel factors into a product of two-qubit
channels, $\mathcal{M}=\mathcal{E}_{2}^{\otimes N/2}$. Each two-qubit channel
$\mathcal{E}_{2}$ acts on a single dimer as

$\displaystyle\mathcal{E}_{2}(\rho)$ $\displaystyle=\sum_{\alpha}\int{\rm
d}u\,{\rm d}v\,\bra{\Phi^{\alpha}}u\otimes v\rho(u\otimes
v)^{\dagger}\ket{\Phi^{\alpha}}$ $\displaystyle\qquad\times(u\otimes
v)^{\dagger}\ket{\Phi^{\alpha}}\bra{\Phi^{\alpha}}u\otimes v.$ (3)

Here both ${\rm d}u$ and ${\rm d}v$ are the Haar measure111While the protocol
is defined in terms of random Clifford gates, we may use the 2-design property
to replace the sum over Clifford gates with the integral over the Haar
measure. over $U(2)$. The channel is diagonal in the Pauli basis owing to
local scrambling [24, 25],
$\mathcal{E}_{2}(\sigma^{\alpha}\otimes\sigma^{\beta})=\lambda_{\alpha\beta}\sigma^{\alpha}\otimes\sigma^{\beta}$.
The eigenvalues are given by

$\displaystyle\lambda_{\alpha\beta}$
$\displaystyle=\frac{1}{4}\Tr[\sigma^{\alpha}\otimes\sigma^{\beta}\mathcal{E}_{2}(\sigma^{\alpha}\otimes\sigma^{\beta})]$
$\displaystyle=\int{\rm d}u\ {\rm d}v\
\bra{\Phi^{0}}(u\sigma^{\alpha}u^{\dagger})\otimes(v\sigma^{\beta}v^{\dagger})\ket{\Phi^{0}}^{2}.$
(4)

Note that the four possible Bell state outcomes
$\\{\ket{\Phi^{\gamma}}:\gamma=0,x,y,z\\}$ all yield the same contribution to
Eq. (4) due to unitary invariance of the ${\rm d}u$ measure, hence a factor of
4.

Next, using the fact that $\bra{\Phi^{0}}B\otimes
C\ket{\Phi^{0}}=\frac{1}{2}\sum_{i,j}B_{ij}C_{ij}=\frac{1}{2}\Tr(BC^{T})$ for
any single-qubit operators $B$, $C$, we have

$\lambda_{\alpha\beta}=\frac{1}{4}\int{\rm d}u\ {\rm d}v\
\left[\Tr(u\sigma^{\alpha}u^{\dagger}v\sigma^{\beta}v^{\dagger})\right]^{2}$
(5)

We see that one of the random rotations is redundant: e.g., the rotation $v$
may be absorbed into the (unitarily invariant) measure ${\rm d}u$, or vice
versa. This illustrates an advantageous property of the protocol: it is enough
to scramble only one qubit per dimer. Physically, this is a consequence of
gate teleportation across the Bell pair: $(u\otimes I)\ket{\Phi^{0}}=(I\otimes
u^{T})\ket{\Phi^{0}}$.

From Eq. (5), it is straightforward to derive the results

$\lambda_{\circ\circ}=1,\quad\lambda_{\circ\bullet}=\lambda_{\bullet\circ}=0,\quad\lambda_{\bullet\bullet}=\frac{1}{3}$
(6)

(like in Eq. (2), $\circ$ stands for the identity, $\alpha=0$, while $\bullet$
stands for a traceless Pauli matrix $\alpha\in\\{x,y,z\\}$). These eigenvalues
fully determine the shadow norm of any Pauli operator $P$:

$\|P\|_{\rm sh}^{2}=\prod_{(i,j)}\lambda_{\alpha_{i}\alpha_{j}}^{-1}$ (7)

where the pair $(i,j)$ ranges over dimers in the system and $\alpha_{i}$
indices are defined by $P=\bigotimes_{i=1}^{N}\sigma^{\alpha_{i}}_{i}$.

The presence of null eigenvalues in $\mathcal{M}$ immediately shows that the
ensemble is not tomographically complete. For convenience, let us introduce
the following definition: a Pauli operator $P$ is _compatible_ with the dimer
covering if its support intersects each dimer in either 0 or 2 sites. Clearly
Pauli operators that are incompatible with the dimer covering are not
learnable, as sketched in Fig. 1(b), since they feature at least one
$\lambda_{\circ\bullet}=0$ eigenvalue. Nonetheless, for the large set222There
are $10^{N/2}$ such operators out of a total of $4^{N}$: each one of the $N/2$
dimers may host $\sigma^{0}\otimes\sigma^{0}$ or
$\sigma^{\alpha}\otimes\sigma^{\beta}$ with $\alpha,\beta\in\\{x,y,z\\}$, for
a total of 10 options. of Pauli operators that are compatible with the dimer
covering, the shadow norm is remarkably low:

$\|P\|_{\rm
sh}^{2}=\lambda_{\circ\circ}^{k/2-N}\lambda_{\bullet\bullet}^{-k/2}=3^{k/2}$
(8)

where $k$ is the weight of $P$.

In analogy with the random Pauli case, we may understand the performance of
Bell shadows with a simple basis counting argument. For each qubit pair, each
run of the experiment measures 3 out of the 9 two-qubit operators
$\\{\sigma^{\alpha}\otimes\sigma^{\beta}:\ \alpha,\beta=x,y,z\\}$—e.g., the
experimentalist may explicitly measure $XX$ and $YZ$, but that also implicitly
measures $ZY=XX\cdot YZ$. Thus the probability that the measurement “hits” a
given $k$-qubit Pauli operator $P$ (compatible with the dimer covering) is
$3/9=1/3$ per pair of qubits on which $P$ acts nontrivially, i.e. $3^{-k/2}$
overall. We also see why operators that are incompatible with the dimer
covering are not learnable, as two-qubit operators of weight 1 such as $IX$ or
$YI$ necessarily anticommute with some of the measured operators.

###  2.3 Some use cases

While tomographically incomplete, the random Bell measurement ensemble is very
powerful for learning Pauli operators compatible with the chosen dimer
covering. This includes many cases of interest for condensed matter physics
and quantum information science; we list some examples below.

##### String operators.

In a 1D lattice, any Pauli operator $P$ whose support is made of $k$
consecutive sites, with $k$ even, is learnable. Operators of this form are
interesting in condensed matter physics as they include string order
parameters for symmetry-protected topological (SPT) phases [29]. To learn all
operators of this form with a given length $k$, regardless of endpoint
location, one must sample two dimer coverings of the lattice (pairing even and
odd bonds, respectively, see Fig. 2(a)). The overall sample complexity of
learning all $M=N\cdot 3^{k}$ operators of this form ($N$ possible endpoint
locations, $3^{k}$ sequences of Pauli matrices inside the support) with
accuracy $\epsilon$ is $2\ln(M/2)3^{k/2}\epsilon^{-2}$, where the factors of
$2$ account for the two distinct dimer coverings. The corresponding scaling
for random Pauli measurements is $\ln(M)3^{k}\epsilon^{-2}$, larger by a
factor of $\simeq 3^{k/2}/2$.

##### Plaquette operators.

Products of Pauli matrices around a plaquette in a two-dimensional lattice may
also be learnable by choosing suitable dimer coverings. Stabilizers of
topological codes [30] typically take this form, as do “ring exchange” terms
[31] in lattice Hamiltonians. As an example, all hexagonal plaquette operators
of a honeycomb qubit lattice may be learned by sampling two dimer coverings
(Fig. 2(b)). The prefactor to the sample complexity is $2\cdot 3^{3}=54$ (i.e.
the squared shadow norm $3^{k/2}$, $k=6$, for each of the 2 dimer coverings).
For comparison, with random Pauli measurements the corresponding prefactor is
$3^{6}=729$, over an order of magnitude larger.

##### Multi-point functions.

Learnable operators need not be geometrically local; in particular, multi-
point correlation functions of $k$-body Hamiltonian terms (with $k$ even) may
be learnable. These quantities play an important role e.g. in diagnosing
equilibration in many-body dynamics. As an example, consider a local
Hamiltonian in a $d$-dimensional lattice, $H=\sum_{\langle
i,j\rangle}h_{(i,j)}$, where
$h_{(i,j)}=\sum_{\alpha,\beta=x,y,z}J_{i,j}^{\alpha\beta}\sigma_{i}^{\alpha}\sigma_{j}^{\beta}$
is the energy density operator at bond $b=(i,j)$, and $J_{i,j}^{\alpha\beta}$
are a priori unknown couplings333With some prior knowledge, one could further
improve performance by biasing or derandomization, which we ignore here.. Bell
shadows can efficiently estimate $p$-point functions $\langle
h_{b_{1}}h_{b_{2}}\cdots h_{b_{p}}\rangle$ of the energy density (as long as
all bonds $b_{1},\dots b_{p}$ match the dimer covering, see Fig. 2(c)) with
sample complexity scaling with $p$ as $\sim 3^{p}$, compared to the scaling
for random Pauli measurements $\sim 9^{p}$.

##  3 General two-qubit bases

Despite the applicability of Bell shadows to several problems of interest, it
would be desirable to have a tomographically complete ensemble with similar
properties. To this end, one can consider general two-qubit entangled bases,
which may interpolate between random Pauli and random Bell measurements.

For a general locally-scrambled measurement ensemble [32, 24], the eigenvalues
of the shadow channel are fully specified by the entanglement feature [33, 34]
$\\{\overline{\mathcal{P}}_{A}\\}$ of the measurement basis—i.e., the purity
of each subsystem $A$ averaged over basis states. As shown in Ref. [11], the
shadow channel eigenvalues are given by

$\lambda_{A}=(-1/3)^{|A|}\sum_{B\subseteq
A}(-2)^{|B|}\overline{\mathcal{P}}_{B}$ (9)

(here $\lambda_{A}$ refers to any Pauli operator with support $A$). In the
present (two-qubit) case, the entanglement feature contains only one
nontrivial parameter: the average purity of a single qubit, which we will
denote by $e^{-S_{2}}$. It is convenient to introduce a “deformation
parameter” $\delta=\ln(2)-S_{2}$, so that $\delta=0$ recovers Bell shadows.
Then, from Eq. (9), the nontrivial eigenvalues of the two-qubit shadow channel
$\mathcal{E}_{2}$ are

$\left\\{\begin{aligned}
&\lambda_{\bullet\circ}=\lambda_{\circ\bullet}=\frac{e^{\delta}-1}{3}\simeq\frac{\delta}{3},\\\
&\lambda_{\bullet\bullet}=\frac{5-2e^{\delta}}{9}\simeq\frac{1}{3+2\delta},\end{aligned}\right.$
(10)

where the $\simeq$ holds to leading order in $\delta\to 0$.

Thus for $\delta>0$ the spectrum of $\mathcal{M}$ becomes strictly positive,
and the ensemble tomographically complete. The shadow norm of a Pauli operator
$P$ with support $A$ that cuts $c_{A}$ dimers is given by

$\displaystyle\|P\|_{\rm sh}^{2}$
$\displaystyle=\lambda_{\bullet\bullet}^{-(|A|-c_{A})/2}\lambda_{\bullet\circ}^{-c_{A}}$
(11)
$\displaystyle\simeq(3+2\delta)^{|A|/2}\left(\frac{\sqrt{3}}{\delta}\right)^{c_{A}}$
(12)

where the second line is up to subleading corrections in small $\delta$. We
recover Eq. (8) for $\delta\to 0$: operators that are compatible with the
dimer covering ($c_{A}=0$) have squared shadow norm $3^{|A|/2}$, the others
($c_{A}>0$) are not learnable.

For the practically-relevant case of string operators in 1D, the result Eq.
(11) is illustrated in Fig. 3. For small $\delta$ (highly entangled
measurement basis), the asymptotic scaling in large $k$ is close to $3^{k/2}$,
but odd-$k$ operators (which break a dimer) are much more costly to learn.
Increasing $\delta$ alleviates the even-odd discrepancy at the expense of a
slightly worse asymptotic scaling in $k$. In particular for
$\delta=\ln(11/8)\simeq 0.318$, we have $\|P\|_{\rm sh}^{2}=4^{k\,{\rm
mod}\,2}\cdot 2^{k}$. This is notable as it beats the performance of optimal-
depth shallow shadows ($\sim k2^{k}$) [27] for modest values $k\gtrsim 4$
(including odd $k$) that are relevant to near-term applications. It is
especially remarkable given the much simpler protocol; see Sec. 5.2 for
further discussion of the relationship between these results.

[width=]qB_shdn.pdf

Figure 3: Pauli shadow norm from two-qubit measurements in bases with variable
entanglement. (a) Setup: qubits (circles) in a 1D chain are grouped into pairs
(blue ellipses) and measured in a given two-qubit basis. The Pauli operator’s
support (full circles) has length $k$. Operators with odd $k$ break a dimer.
(b) $\|P\|_{\rm sh}^{2}$ as a function of $k$ for different values of the
basis entanglement $S_{2}=\ln(2)-\delta$. Also shown are the scalings
$3^{k/2}$ (dashed line), $2^{k}$ (dotted line) and $3^{k}$ (dot-dashed line).

##  4 Beyond two-qubit measurements

It is straightforward to generalize the previous discussion to measurements
that factor into $n$-qubit bases, with $n>2$. For $n=3$, this requires picking
a trimer covering and a choice of measurements on each trimer. It is easy to
show444Eq. (9) gives
$\lambda_{\bullet\bullet\bullet}=(7-6\overline{\mathcal{P}})/27$ where
$\overline{\mathcal{P}}$ is the average purity of a single qubit in the
measurement basis (averaged over sites and states in the basis). This is
maximized for $\overline{\mathcal{P}}=1/2$, which is achieved by the GHZ
basis. that the optimal protocol (optimized for the learnability of compatible
operators, defined here as having either 0 or 3 non-identity operators per
trimer) is given by measurements in locally-scrambled GHZ bases, i.e., the 8
orthonormal states stabilized by $\pm X_{1}X_{2}X_{3}$, $\pm Z_{1}Z_{2}$, $\pm
Z_{2}Z_{3}$, up to local Clifford transformations.

While the optimization is less straightforward for $n>3$, one can show that
the $n$-qubit GHZ basis remains at least near-optimal at large $n$. The
relevant eigenvalue for compatible operators, adapting Eq. (9), is

$\lambda_{[n]}=(-1/3)^{n}\sum_{A\subseteq[n]}(-2)^{|A|}\overline{\mathcal{P}}_{A},$
(13)

where $[n]\equiv\\{1,\dots n\\}$. The entanglement feature of an $n$-qubit GHZ
state is $\overline{\mathcal{P}}_{A}=1/2$ for all subsystems $A$ except
$A=\emptyset$ and $A=[n]$, where $\overline{\mathcal{P}}_{A}=1$; thus

$\displaystyle\lambda_{[n]}$
$\displaystyle=(-1/3)^{n}\left[1+(-2)^{n}+\sum_{l=1}^{n-1}\binom{n}{l}(-2)^{l}\frac{1}{2}\right]$
$\displaystyle=\frac{2^{n}+1+(-1)^{n}}{2\cdot 3^{n}}.$ (14)

Thus the shadow norm of Pauli operators that are compatible with the partition
is $\|P\|_{\rm sh}^{2}=(f_{n})^{k}$, with $k$ the Pauli weight and

$f_{n}=\left\\{\begin{aligned} &\frac{3}{[2^{n-1}+1]^{1/n}}&&\text{if $n$ is
even,}\\\ &\frac{3}{2^{1-1/n}}&&\text{if $n$ is odd.}\end{aligned}\right.$
(15)

Let us unpack this result:

  * •

For $n=1$ we recover random Pauli shadows, $f_{1}=3$;

  * •

For $n=2$ we recover Bell shadows, $f_{2}=\sqrt{3}\simeq 1.732$;

  * •

For $n=3$ we find $f_{3}=3/2^{2/3}\simeq 1.890$, larger than $f_{2}$ and thus
less efficient than Bell shadows when both are applicable, but potentially
useful to learn quantities such as multi-point functions of 3-body operators;

  * •

For $n\geq 4$, $f_{n}$ decreases monotonically and asymptotes to $3/2$,
meaning a scaling of shadow norms as $\|P\|_{\rm sh}^{2}=(3/2)^{k}$ for
compatible operators.

This scaling with $k$ is optimal for stabilizer measurements, i.e. when each
run of the experiment measures $n$ independent, commuting Pauli operators
$\\{g_{i}\\}_{i=1}^{n}$. In effect this corresponds to measuring $2^{n}$
stabilizers: $\\{\prod_{i}g_{i}^{s_{i}}:\ \mathbf{s}\in\\{0,1\\}^{n}\\}$. Thus
each basis choice “hits” at most $2^{n}$ out of the $3^{n}$ maximum-weight
Pauli operators. It follows that the probability of “hitting” a given
compatible operator is $\leq[(2/3)^{n}]^{k/n}=(2/3)^{k}$, hence the bound on
the shadow norm $\|P\|_{\rm sh}^{2}\geq(3/2)^{k}$ for all stabilizer
measurement bases. It would be interesting to investigate optimality of this
scaling more generally, beyond stabilizer measurements.

GHZ measurements come very close to saturating this bound, as $\|P\|_{\rm
sh}^{2}=(f_{n})^{k}$ and $f_{n}\xrightarrow[]{n\to\infty}3/2$. The improved
scaling of sample complexity however comes with some trade-offs. For one, the
set of “compatible” operators whose shadow norm obeys the scaling in Eq. (15)
gets more constrained with increasing $n$ (the set comprises $[3^{n}+1]^{N/n}$
operators). Secondly, preparing the GHZ measurement basis on $n$ qubits
requires circuit depth linear in $n$, which makes the method less scalable on
noisy hardware and limits $n$ to modest finite values.

##  5 Discussion

###  5.1 Summary

We have introduced classical shadows protocols based on randomized
measurements that feature entanglement over finite-sized subsystems. These
protocols are NISQ-friendly, requiring only local shallow circuits; further,
the classical post-processing steps are straightforward, on par with the
standard classical shadows protocols based on random Pauli or Clifford
measurements [1].

We have shown that locally-entangled measurements can lead to substantial
improvements in sample complexity for some Pauli estimation tasks. As a
paradigmatic example, we have focused on two-qubit Bell measurements, Sec. 2.
These achieve an improved scaling of sample complexity $\propto 3^{k/2}$ with
Pauli weight $k$ for many operators, while failing to learn others. Such
trade-offs are unavoidable since the scaling $\sim 3^{k}$ of random Pauli
shadows is optimal in general under a fixed set of local measurements [1]
(i.e. it is not possible to do better for all Pauli operators); nonetheless,
the trade-off can be advantageous for tasks of interest in quantum many-body
physics such as the estimation of string operators or multi-point functions of
local operators.

We have further shown (Sec. 3) that general two-qubit entangled bases make it
possible to interpolate between Pauli and Bell measurements. This gives a
family of tomographically-complete protocols that retain a favorable scaling
of sample complexity in many cases, Eq. (12). Finally, when allowing
entanglement between $n>2$ qubits (Sec. 4), we have found that $n$-qubit GHZ
measurements enable the estimation of certain ‘compatible’ Pauli operators
with even more advantageous scaling of the shadow norm, $\|P\|_{\rm
sh}^{2}\sim(3/2)^{k}$ for large $n$, Eq. (15). This scaling in $k$ is optimal
for stabilizer measurements.

###  5.2 Connections with prior work

####  5.2.1 Shallow shadows

Recent works have focused on leveraging locality—an important factor in many
NISQ architectures—to develop variations of classical shadows with certain
practical advantages. In particular, shallow shadows [24, 25] implement the
basis randomization step via circuits of variable depth and have been recently
shown to give a significantly improved sample complexity (relative to random
Pauli measurements) for learning expectation values of geometrically local
Pauli operators, among other advantageous properties [24, 25, 26, 27].

Bell shadows (and other $n=2$ protocols) may be seen as a depth-1 instance of
shallow shadows, featuring a single layer of two-qubit entangling gates.
However, this appears to raise a puzzle in relation to the shadow norm of
Pauli string operators in 1D. While shallow shadows were shown to achieve an
optimal scaling of sample complexity $\sim k2^{k}$ [27], Bell shadows manage
to achieve the improved scaling $\sim 3^{k/2}$ for some of the same operators.
How can a depth-1 instance outperform the optimal-depth version of the
protocol?

The answer lies in the fact that Bell shadows feature a partly deterministic
measurement sequence: the state is locally-scrambled, then evolved by a
deterministic circuit (a single layer of entangling CZ or
$\textsf{CPhase}(\phi)$ gates) and measured in a deterministic local basis
($X$). Shallow shadows, on the contrary, are based on fully-random circuits
[25, 26], or feature a local scrambling step right before the final single-
qubit measurements [32, 24]. Exploiting this final local-scrambling step, Ref.
[27] maps the shadow norm to properties of the operator weight distribution
under the twirling circuit, and as a consequence derives the optimal
scaling555This is the same scaling one would obtain from a tensor product of
random Clifford bases on $k$-qubit segments ($\sim 2^{k}$), iterated $k$ times
to address all possible Pauli endpoint locations modulo $k$. Surprisingly,
shallow shadows achieve this scaling already at depth $O(\ln k)$ [27]. $\sim
k2^{k}$. Bell shadows, by avoiding the local scrambling step before the final
single-qubit measurements, evade this result and are thus able to improve the
scaling to $\sim 3^{k/2}$ in the best case.

Another advantage of locally-entangled shadows over generic shallow shadows is
that the inversion of $\mathcal{M}$ is effortless (on par with the random
Pauli and random Clifford protocols [1]), and does not require tensor network
algorithms [24, 25]. This straightforwardly unlocks applications to higher-
dimensional systems. Moreover, locally-entangled shadows may also be more
advantageous for learning $k$-local, but geometrically non-local Pauli
operators (as long as these are compatible with the partition of the system
into $n$-qubit sets)—see the discussion on multi-point correlators in Sec.
2.3.

At the same time, generic shallow shadows retain some important advantages.
First of all, shallow shadows can efficiently learn many-body fidelity (at
depth $t\sim\log(N)$), akin to random Clifford measurements [25]. This is
beyond the scope of locally-entangled shadows. Within Pauli estimation,
generic shallow shadows are more efficient for estimating expectation values
of local Pauli operators in 1D with a finite (sufficiently low) density of
identity operators between their endpoints [27]. These operators would have a
finite density of broken dimers and thus be impossible to learn in Bell
shadows and expensive to learn under general two-qubit measurements, cf Eq.
(12).

####  5.2.2 Learning via locally-entangled measurements

Various other state-learning protocols that make use of Bell, GHZ, or other
locally-entangled measurements have been studied. Refs. [35, 36, 37] focus on
including Bell and GHZ measurements as part of a measurement optimization
algorithm for learning a given set of operators, which is complementary to our
focus on randomized measurements.

Ref. [38], while written prior to the introduction of classical shadows, has
several analogies with our discussion of Bell shadows, Sec. 2. The approach
relies on introducing one auxiliary qubit $\vec{\tau}_{i}$ per system qubit
$\vec{\sigma}_{i}$; each of the auxiliary qubits is in an initial state
$\xi=(\mathbb{I}+\hat{n}\cdot\vec{\tau})/2$ with $\hat{n}=(1,1,1)/\sqrt{3}$.
By measuring the two qubits $\vec{\sigma}_{i}$, $\vec{\tau}_{i}$ in the
standard Bell basis, one simultaneously learns the expectation all three
commuting operators666A similar idea was recently employed to embed non-
commuting Hamiltonians into commuting “Ising” models in an enlarged space
[39]. $\sigma^{\alpha}_{i}\otimes\tau^{\alpha}_{i}$ for all $\alpha=x,y,z$ and
each site $i$. We thus learn the expectation of
$\tilde{P}=\bigotimes_{i}\sigma_{i}^{\alpha_{i}}\otimes\tau_{i}^{\alpha_{i}}$:

$\displaystyle\langle\tilde{P}\rangle$
$\displaystyle=\langle\bigotimes_{i}\sigma_{i}^{\alpha_{i}}\otimes\tau_{i}^{\alpha_{i}}\rangle=\langle
P\rangle\prod_{i}\Tr(\xi_{i}\tau_{i}^{\alpha_{i}})$
$\displaystyle=3^{-k/2}\langle P\rangle,$ (16)

where $P=\bigotimes_{i}\sigma_{i}^{\alpha_{i}}$ is a Pauli operator on the
system qubits, and $k$ is its weight. Learning $\langle P\rangle$ with
additive error $\epsilon$ requires learning $\langle\tilde{P}\rangle$ with
additive error $3^{-k/2}\epsilon$, thus the sample complexity scales as
$3^{k}\epsilon^{-2}$.

The relationship with Bell shadows becomes apparent if one views the above
protocol as learning a Pauli operator $\tilde{P}$ of weight $2k$ on a two-leg
ladder. The dimer covering is given by pairing qubits $\vec{\sigma}_{i}$ and
$\vec{\tau}_{i}$ on each rung, and $\tilde{P}$ is manifestly compatible with
the covering, giving the expected sample complexity $\sim
3^{|\tilde{P}|/2}=3^{k}$. Thus the protocol of Ref. [38] may be seen as a
“derandomized” version of Bell shadows with a specific geometry, dimer
covering, and subset of initial states.

###  5.3 Future directions

The advantages and limitations of locally-entangled shadows both follow from
using a structured, (partially) non-random circuit. This observation points to
interesting directions for future research, based on leveraging structure in a
problem of interest to design tailored, highly-optimized shadow (or shadow-
like) state-learning protocols. Several such proposals have been put forth,
e.g. with the goal of optimizing energy estimates for molecular Hamiltonians
[3, 28, 40, 41, 42, 43]. However, these proposals typically deal with the
optimization of local basis choices within a Pauli measurement framework. Our
work points to the possibility of substantial gains from using entangled
measurement bases, even in the simplest and most practically accessible case
of two-qubit entanglement. It would be interesting to identify more complex
many-body entanglement structures optimized for learning different classes of
properties of quantum states, such as entropies or other nonlinear
functionals.

Another interesting direction is to bring Bell shadows within reach of analog
quantum simulators, by adapting the approaches of Refs. [44, 45]. In lieu of
random unitary gates, these approaches make use of fixed Hamiltonian dynamics
and the stochastic nature of quantum measurements to supply the randomization
needed for classical shadows without digital control [46, 47, 48, 49, 50, 51,
52]. The “patched quench” scenario of Ref. [44] in particular appears as a
natural setup for optimized locally-entangled shadows. The task of finely
tuning the amount of entanglement in the measurement basis for these protocols
is nontrivial, but may be achievable depending on the nature of the analog
simulator dynamics.

I thank Vedika Khemani, Yaodong Li and Tibor Rakovszky for previous and
ongoing collaborations on related topics. This work is supported in part by
the Gordon and Betty Moore Foundation’s EPiQS Initiative through Grant
GBMF8686.

## References

  * [1] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  “Predicting many properties of a quantum system from very few measurements”.  Nature Physics 16, 1050–1057 (2020).
  * [2] Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoit Vermersch, and Peter Zoller.  “The randomized measurement toolbox”.  Nature Reviews Physics 5, 9–24 (2023).
  * [3] Charles Hadfield, Sergey Bravyi, Rudy Raymond, and Antonio Mezzacapo.  “Measurements of Quantum Hamiltonians with Locally-Biased Classical Shadows” (2020).  arXiv:2006.15788.
  * [4] Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia.  “Robust Shadow Estimation”.  PRX Quantum 2, 030348 (2021).
  * [5] Atithi Acharya, Siddhartha Saha, and Anirvan M. Sengupta.  “Shadow tomography based on informationally complete positive operator-valued measure”.  Physical Review A 104, 052418 (2021).
  * [6] G.I. Struchalin, Ya. A. Zagorovskii, E.V. Kovlakov, S.S. Straupe, and S.P. Kulik.  “Experimental Estimation of Quantum State Properties from Classical Shadows”.  PRX Quantum 2, 010307 (2021).
  * [7] Ryan Levy, Di Luo, and Bryan K. Clark.  “Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers” (2021).  arXiv:2110.02965.
  * [8] Jonathan Kunjummen, Minh C. Tran, Daniel Carney, and Jacob M. Taylor.  “Shadow process tomography of quantum channels” (2022).  arXiv:2110.03629.
  * [9] Hsin-Yuan Huang.  “Learning quantum states from their classical shadows”.  Nature Reviews Physics 4, 81–81 (2022).
  * [10] Kianna Wan, William J. Huggins, Joonho Lee, and Ryan Babbush.  “Matchgate Shadows for Fermionic Quantum Simulation” (2022).  arXiv:2207.13723.
  * [11] Kaifeng Bu, Dax Enshan Koh, Roy J. Garcia, and Arthur Jaffe.  “Classical shadows with Pauli-invariant unitary ensembles” (2022).  arXiv:2202.03272.
  * [12] H. Chau Nguyen, Jan Lennart Bonsel, Jonathan Steinberg, and Otfried Guhne.  “Optimizing Shadow Tomography with Generalized Measurements”.  Physical Review Letters 129, 220502 (2022).
  * [13] Dax Enshan Koh and Sabee Grewal.  “Classical Shadows With Noise”.  Quantum 6, 776 (2022).
  * [14] Daniel Grier, Hakop Pashayan, and Luke Schaeffer.  “Sample-optimal classical shadows for pure states” (2022).  arXiv:2211.11810.
  * [15] Simon Becker, Nilanjana Datta, Ludovico Lami, and Cambyse Rouze.  “Classical shadow tomography for continuous variables quantum systems” (2022).  arXiv:2211.07578.
  * [16] Alireza Seif, Ze-Pei Cian, Sisi Zhou, Senrui Chen, and Liang Jiang.  “Shadow Distillation: Quantum Error Mitigation with Classical Shadows for Near-Term Quantum Processors”.  PRX Quantum 4, 010303 (2023).
  * [17] Katherine Van Kirk, Jordan Cotler, Hsin-Yuan Huang, and Mikhail D. Lukin.  “Hardware-efficient learning of quantum many-body states” (2022).  arXiv:2212.06084.
  * [18] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, et al.  “Quantum supremacy using a programmable superconducting processor”.  Nature 574, 505–510 (2019).
  * [19] Ehud Altman, Kenneth R. Brown, Giuseppe Carleo, Lincoln D. Carr, Eugene Demler, Cheng Chin, Brian DeMarco, Sophia E. Economou, et al.  “Quantum Simulators: Architectures and Opportunities”.  PRX Quantum 2, 017003 (2021).
  * [20] Sepehr Ebadi, Tout T. Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, et al.  “Quantum phases of matter on a 256-atom programmable quantum simulator”.  Nature 595, 227–232 (2021).
  * [21] Xiao Mi, Pedram Roushan, Chris Quintana, Salvatore Mandra, Jeffrey Marshall, Charles Neill, Frank Arute, Kunal Arya, et al.  “Information scrambling in quantum circuits”.  Science 374, 1479–1483 (2021).
  * [22] Tiff Brydges, Andreas Elben, Petar Jurcevic, Benoit Vermersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, et al.  “Probing Renyi entanglement entropy via randomized measurements”.  Science 364, 260–263 (2019).
  * [23] A. Elben, B. Vermersch, C. F. Roos, and P. Zoller.  “Statistical correlations between locally randomized measurements: A toolbox for probing entanglement in many-body quantum states”.  Phys. Rev. A 99, 052323 (2019).
  * [24] Ahmed A. Akhtar, Hong-Ye Hu, and Yi-Zhuang You.  “Scalable and Flexible Classical Shadow Tomography with Tensor Networks” (2022).  arXiv:2209.02093.
  * [25] Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, and Hakop Pashayan.  “Shallow shadows: Expectation estimation using low-depth random Clifford circuits” (2022).  arXiv:2209.12924.
  * [26] Mirko Arienzo, Markus Heinrich, Ingo Roth, and Martin Kliesch.  “Closed-form analytic expressions for shadow estimation with brickwork circuits” (2022).  arXiv:2211.09835.
  * [27] Matteo Ippoliti, Yaodong Li, Tibor Rakovszky, and Vedika Khemani.  “Operator relaxation and the optimal depth of classical shadows” (2023).  arXiv:2212.11963.
  * [28] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  “Efficient Estimation of Pauli Observables by Derandomization”.  Physical Review Letters 127, 030503 (2021).
  * [29] Jutho Haegeman, David Perez-Garcia, Ignacio Cirac, and Norbert Schuch.  “Order Parameter for Symmetry-Protected Phases in One Dimension”.  Physical Review Letters 109, 050402 (2012).
  * [30] H. Bombin.  “An Introduction to Topological Quantum Codes” (2013).  arXiv:1311.0277.
  * [31] D. J. Thouless.  “Exchange in solid 3He and the Heisenberg Hamiltonian”.  Proceedings of the Physical Society 86, 893 (1965).
  * [32] Hong-Ye Hu, Soonwon Choi, and Yi-Zhuang You.  “Classical Shadow Tomography with Locally Scrambled Quantum Dynamics” (2021).  arXiv:2107.04817.
  * [33] Yi-Zhuang You and Yingfei Gu.  “Entanglement features of random Hamiltonian dynamics”.  Physical Review B 98, 014309 (2018).
  * [34] Wei-Ting Kuo, A. A. Akhtar, Daniel P. Arovas, and Yi-Zhuang You.  “Markovian Entanglement Dynamics under Locally Scrambled Quantum Evolution”.  Physical Review B 101, 224202 (2020).
  * [35] Ikko Hamamura and Takashi Imamichi.  “Efficient evaluation of quantum observables using entangled measurements”.  npj Quantum Information 6, 1–8 (2020).
  * [36] Ruho Kondo, Yuki Sato, Satoshi Koide, Seiji Kajita, and Hideki Takamatsu.  “Computationally Efficient Quantum Expectation with Extended Bell Measurements”.  Quantum 6, 688 (2022).
  * [37] Francisco Escudero, David Fernandez-Fernandez, Gabriel Jauma, Guillermo F. Penas, and Luciano Pereira.  “Hardware-efficient entangled measurements for variational quantum algorithms” (2022).  arXiv:2202.06979.
  * [38] Zhang Jiang, Amir Kalev, Wojciech Mruczkiewicz, and Hartmut Neven.  “Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning”.  Quantum 4, 276 (2020).
  * [39] Ruben Verresen.  “Everything is a quantum Ising model” (2023).  arXiv:2301.11917.
  * [40] Charles Hadfield.  “Adaptive Pauli Shadows for Energy Estimation” (2021).  arXiv:2105.12207.
  * [41] Stefan Hillmich, Charles Hadfield, Rudy Raymond, Antonio Mezzacapo, and Robert Wille.  “Decision Diagrams for Quantum Measurements with Shallow Circuits”.  In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE).  Pages 24–34.  (2021).
  * [42] Tzu-Ching Yen, Aadithya Ganeshram, and Artur F. Izmaylov.  “Deterministic improvements of quantum measurements with grouping of compatible operators, non-local transformations, and covariance estimates” (2022).  arXiv:2201.01471.
  * [43] Bujiao Wu, Jinzhao Sun, Qi Huang, and Xiao Yuan.  “Overlapped grouping measurement: A unified framework for measuring quantum states”.  Quantum 7, 896 (2023).
  * [44] Minh C. Tran, Daniel K. Mark, Wen Wei Ho, and Soonwon Choi.  “Measuring Arbitrary Physical Properties in Analog Quantum Simulation”.  Physical Review X 13, 011049 (2023).
  * [45] Max McGinley and Michele Fava.  “Shadow tomography from emergent state designs in analog quantum simulators” (2022).  arXiv:2212.02543.
  * [46] Joonhee Choi, Adam L. Shaw, Ivaylo S. Madjarov, Xin Xie, Ran Finkelstein, Jacob P. Covey, Jordan S. Cotler, Daniel K. Mark, et al.  “Preparing random states and benchmarking with many-body quantum chaos”.  Nature 613, 468–473 (2023).
  * [47] Jordan S. Cotler, Daniel K. Mark, Hsin-Yuan Huang, Felipe Hernandez, Joonhee Choi, Adam L. Shaw, Manuel Endres, and Soonwon Choi.  “Emergent Quantum State Designs from Individual Many-Body Wave Functions”.  PRX Quantum 4, 010311 (2023).
  * [48] Wen Wei Ho and Soonwon Choi.  “Exact Emergent Quantum State Designs from Quantum Chaotic Dynamics”.  Physical Review Letters 128, 060601 (2022).
  * [49] Pieter W. Claeys and Austen Lamacraft.  “Emergent quantum state designs and biunitarity in dual-unitary circuit dynamics”.  Quantum 6, 738 (2022).
  * [50] Matteo Ippoliti and Wen Wei Ho.  “Dynamical purification and the emergence of quantum state designs from the projected ensemble” (2023).  arXiv:2204.13657.
  * [51] Matteo Ippoliti and Wen Wei Ho.  “Solvable model of deep thermalization with distinct design times”.  Quantum 6, 886 (2022).
  * [52] Pieter W. Claeys.  “Universality in quantum snapshots”.  Quantum Views 7, 71 (2023).