Classical shadow

In quantum computing, classical shadow is a protocol for predicting functions of a quantum state using only a logarithmic number of measurements.^[1] Given an unknown state ${\displaystyle \rho }$, a tomographically complete set of gates ${\displaystyle U}$ (e.g. Clifford gates), a set of ${\displaystyle M}$ observables ${\displaystyle \{O_{i}\}}$ and a quantum channel ${\displaystyle {\mathcal {E}}}$ defined by randomly sampling from ${\displaystyle U}$, applying it to ${\displaystyle \rho }$ and measuring the resulting state, predict the expectation values ${\displaystyle \operatorname {tr} (O_{i}\rho )}$.^[2] A list of classical shadows ${\displaystyle S}$ is created using ${\displaystyle \rho }$, ${\displaystyle U}$ and ${\displaystyle {\mathcal {E}}}$ by running a Shadow generation algorithm. When predicting the properties of ${\displaystyle \rho }$, a Median-of-means estimation algorithm is used to deal with the outliers in ${\displaystyle S}$.^[3] Classical shadow is useful for direct fidelity estimation, entanglement verification, estimating correlation functions, and predicting entanglement entropy.^[1]

Recently, researchers have built on classical shadow to devise provably efficient classical machine learning algorithms for a wide range of quantum many-body problems.^[4] For example, machine learning models could learn to solve ground states of quantum many-body systems and classify quantum phases of matter.

Algorithm Shadow generation

Inputs ${\displaystyle N}$ copies of an unknown ${\displaystyle n}$-qubit state ${\displaystyle \rho }$

                  A list of unitaries ${\displaystyle U}$ that is tomographically complete

                  A classical description of a quantum channel ${\displaystyle {\mathcal {E}}^{-1}}$

1. For ${\displaystyle i}$ ranging from ${\displaystyle 1}$ to ${\displaystyle N}$:
   1. Choose a random unitary ${\displaystyle U_{i}}$ from ${\displaystyle U}$
   2. Apply ${\displaystyle U_{i}}$ to ${\displaystyle \rho }$ to get a state ${\displaystyle \rho _{i}}$
   3. Perform a computational basis measurement on ${\displaystyle \rho _{i}}$ for an outcome ${\displaystyle b_{i}\in \{0,1\}^{n}}$
   4. Classically compute ${\displaystyle {\mathcal {E}}^{-1}(U_{i}^{\dagger }|b_{i}\rangle \langle b_{i}|U_{i})}$ and add it to a list ${\displaystyle S}$

Return ${\displaystyle S}$

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

Algorithm Median-of-means estimation

Inputs A list of observables ${\displaystyle O_{1},....,O_{M}}$

                  A classical shadow ${\displaystyle S(\rho ;N)=[{\hat {\rho }}_{1},\ldots ,{\hat {\rho }}_{N}]}$

                  A positive integer ${\displaystyle K}$ that specifies how many linear estimates of ${\displaystyle \rho }$ to calculate.

Return A list ${\displaystyle [o_{1},...,o_{M}]}$ where ${\displaystyle o_{i}=\mathrm {median} (\mathrm {trace} (O_{1}p_{1}),...,\mathrm {trace} (O_{1}p_{K}))}$

where ${\displaystyle p_{k}={\frac {1}{[{\frac {N}{K}}]}}\sum _{i=(k-1)[{\frac {N}{K}}]+1}^{k[{\frac {N}{K}}]}{\hat {\rho }}_{i}}$ and where ${\displaystyle k=1,...,K}$.

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.