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.