Sample-optimal classical shadows for pure states
Daniel Grier, Hakop Pashayan, Luke Schaeffer
Abstract
We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03C1;</mml:mi></mml:math> in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">T</mml:mi><mml:mi mathvariant="normal">r</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>O</mml:mi><mml:mi>&#x03C1;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> for any Hermitian observable <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi></mml:math> to within additive error <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03F5;</mml:mi></mml:math> provided <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">T</mml:mi><mml:mi mathvariant="normal">r</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>O</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mo>&#x2264;</mml:mo><mml:mi>B</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo fence="false" stretchy="false">&#x2016;</mml:mo><mml:mi>O</mml:mi><mml:mo fence="false" stretchy="false">&#x2016;</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:math>. Our main result applies to the joint measurement setting, where we show <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi mathvariant="normal">&#x0398;</mml:mi><mml:mo stretchy="false">&#x007E;</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>B</mml:mi></mml:msqrt><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> samples of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03C1;</mml:mi></mml:math> are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03C1;</mml:mi></mml:math> can be compressed for observable estimation. In the independent measurement setting, we show that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>B</mml:mi><mml:mi>d</mml:mi></mml:msqrt><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.