Sample-optimal classical shadows for pure states

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 $\rho$ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate $\mathrm{Tr}(O\rho )$ for any Hermitian observable $O$ to within additive error $\epsilon$ provided $\mathrm{Tr}(O^2)\le B$ and $\Vert O\Vert =1$. Our main result applies to the joint measurement setting, where we show $\tilde{\Theta }(\sqrt{B}{\epsilon }^{-1}+{\epsilon }^{-2})$ samples of $\rho$ 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 $\rho$ can be compressed for observable estimation. In the independent measurement setting, we show that $\mathcal{O}(\sqrt{Bd}{\epsilon }^{-1}+{\epsilon }^{-2})$ 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.

34 pages; v2 - journal version

References in corpus (2)

• Tight informationally complete quantum measurements
• Scalable and Flexible Classical Shadow Tomography with Tensor Networks

Cited by in corpus (11)

• Shallow shadows: Expectation estimation using low-depth random Clifford circuits
• Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping
• Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach
• Learning Properties of Quantum States Without the I.I.D. Assumption
• Nearly query-optimal classical shadow estimation of unitary channels
• An Error Mitigated Non-Orthogonal Quantum Eigensolver via Shadow Tomography
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• Optimal estimation of three parallel spins with genuine and restricted collective measurements
• Classical Shadows with Improved Median-of-Means Estimation
• Certifying entanglement dimensionality by $k$-reduction moments
• Sample Optimal and Memory Efficient Quantum State Tomography