Classical shadow

{{Short description|Quantum computing protocol}}

{{Orphan|date=July 2021}}

In quantum computing, classical shadow is a protocol for predicting functions of a quantum state using only a logarithmic number of measurements.{{Cite journal | arxiv=2002.08953|last1=Huang |first1=Hsin-Yuan |last2=Kueng |first2=Richard |last3=Preskill|first3=John |title =Predicting many properties of a quantum system from very few measurements|year=2020 |journal=Nat. Phys.|volume=16 | issue=10 |pages=1050–1057|doi=10.1038/s41567-020-0932-7|bibcode=2020NatPh..16.1050H |s2cid=211205098 }} Given an unknown state $\backslash rho$, a tomographically complete set of gates $U$ (e.g. Clifford gates), a set of $M$ observables $\backslash \{O\_\{i\}\backslash \}$ and a quantum channel $\backslash mathcal\{E\}$ defined by randomly sampling from $U$, applying it to $\backslash rho$ and measuring the resulting state, predict the expectation values $\backslash operatorname\{tr\}(O\_\{i\}\; \backslash rho)$.{{cite journal | arxiv=2011.11580|last1= Koh |first1=D. E. |last2=Grewal|first2= Sabee |title=Classical Shadows with Noise|journal= Quantum |year=2022|volume= 6 |page= 776 |doi= 10.22331/q-2022-08-16-776 |bibcode= 2022Quant...6..776K |s2cid= 227127118 }} A list of classical shadows $S$ is created using $\backslash rho$, $U$ and $\backslash mathcal\{E\}$ by running a Shadow generation algorithm. When predicting the properties of $\backslash rho$, a Median-of-means estimation algorithm is used to deal with the outliers in $S$.{{Cite journal | arxiv=2008.05234|last1=Struchalin |first1=G.I. |last2=Zagorovskii |first2=Ya. A. |last3=Kovlakov |first3=E.V. |last4=Straupe | first4=S.S. |last5=Kulik |first5= S.P.|title=Experimental Estimation of Quantum State Properties from Classical Shadows|year=2021 |journal=PRX Quantum|volume=2 | issue=1 |page=010307 |doi=10.1103/PRXQuantum.2.010307|s2cid=221103573 }} Classical shadow is useful for direct fidelity estimation, entanglement verification, estimating correlation functions, and predicting entanglement entropy.

Recently, researchers have built on classical shadow to devise provably efficient classical machine learning algorithms for a wide range of quantum many-body problems.{{cite journal |last1=Huang |first1=Hsin-Yuan |last2=Kueng |first2=Richard |last3=Torlai |first3=Giacomo |last4=Albert |first4=Victor A. |last5=Preskill |first5=John |title=Provably efficient machine learning for quantum many-body problems |journal=Science |year=2022 |volume=377 |issue=6613 |pages=eabk3333 |doi=10.1126/science.abk3333 |pmid=36137032 |arxiv=2106.12627|s2cid=235624289 }} For example, machine learning models could learn to solve ground states of quantum many-body systems and classify quantum phases of matter.

{{Algorithm-begin|name=Shadow generation}}

:Inputs $N$ copies of an unknown $n$-qubit state $\backslash rho$

                  A list of unitaries $U$ that is tomographically complete

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

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

:Return $S$

{{Algorithm-end}}

{{Algorithm-begin|name=Median-of-means estimation}}

:Inputs A list of observables $O\_\{1\},\; ....,\; O\_\{M\}$

                  A classical shadow $S(\backslash rho;\; N)\; =\; [\backslash hat\{\backslash rho\}\_1,\; \backslash ldots,\; \backslash hat\{\backslash rho\}\_N]$

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

:Return A list $[o\_\{1\},\; ...,\; o\_\{M\}]$ where $o\_\{i\}\; =\; \backslash mathrm\{median\}(\backslash mathrm\{trace\}(O\_\{1\}\; p\_\{1\}),...,\; \backslash mathrm\{trace\}(O\_\{1\}\; p\_\{K\}))$

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

{{Algorithm-end}}