# Optimal high-precision shadow estimation

arXiv: https://arxiv.org/abs/2407.13874 · HTML: https://mlsanity.com/paper/2407.13874/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 18 Jul 2024.

## Builds on (most cited first, 7 of 7)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)
- [Efficient Pauli channel estimation with logarithmic quantum memory](https://mlsanity.com/paper/2309.14326/) (2023)
- [Sample-optimal classical shadows for pure states](https://mlsanity.com/paper/2211.11810/) (2022)
- [An optimal tradeoff between entanglement and copy complexity for state tomography](https://mlsanity.com/paper/2402.16353/) (2024)
- [Improved classical shadows from local symmetries in the Schur basis](https://mlsanity.com/paper/2405.09525/) (2024)

## Built on by (most cited first, 1 of 1)

- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)

## Abstract (arXiv)

We give the first tight sample complexity bounds for shadow tomography and classical shadows in the regime where the target error is below some sufficiently small inverse polynomial in the dimension of the Hilbert space. Formally we give a protocol that, given any m∈mathbbN and ε ≤ O(d-12), measures O(log(m)/ε2) copies of an unknown mixed state ρ∈mathbbCd× d and outputs a classical description of ρ which can then be used to estimate any collection of m observables to within additive accuracy ε. Previously, even for the simpler task of shadow tomography -- where the m observables are known in advance -- the best known rates either scaled benignly but suboptimally in all of m, d, ε, or scaled optimally in ε, m but had additional polynomial factors in d for general observables. Intriguingly, we also show via dimensionality reduction, that we can rescale ε and d to reduce to the regime where ε ≤ O(d-1/2). Our algorithm draws upon representation-theoretic tools recently developed in the context of full state tomography.