Classical shadow

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 [{\hat {o}}_{1},...,{\hat {o}}_{M}]}$ where ${\displaystyle {\hat {o}}_{i}=\mathrm {median} (\mathrm {trace} (O_{i}p_{1}),...,\mathrm {trace} (O_{i}p_{K}))}$

where ${\displaystyle p_{k}={\frac {1}{\lfloor N/K\rfloor }}\sum _{i=(k-1)\lfloor N/K\rfloor +1}^{k\lfloor N/K\rfloor }{\hat {\rho }}_{i}}$ for ${\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.