REVIEW 5 cited by
Optimal high-precision shadow estimation
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
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\in\mathbb{N}$ and $\epsilon \le O(d^{-12})$, measures $O(\log(m)/\epsilon^2)$ copies of an unknown mixed state $\rho\in\mathbb{C}^{d\times d}$ and outputs a classical description of $\rho$ which can then be used to estimate any collection of $m$ observables to within additive accuracy $\epsilon$. 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, \epsilon$, or scaled optimally in $\epsilon, m$ but had additional polynomial factors in $d$ for general observables. Intriguingly, we also show via dimensionality reduction, that we can rescale $\epsilon$ and $d$ to reduce to the regime where $\epsilon \le O(d^{-1/2})$. Our algorithm draws upon representation-theoretic tools recently developed in the context of full state tomography.
Forward citations
Cited by 5 Pith papers
-
Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements
New sequential pretty-good measurement protocol achieves dimension-free shadow tomography with sample complexity O(1/eps^2 * (log(M/delta))^4 / (log log(M/delta))^3).
-
The Keyl-Werner algorithm is not optimal for spectrum estimation
Spectrum estimation of a d-dimensional quantum state is possible with o(d²) copies—specifically O(d² (log log d / log d)²)—beating Keyl–Werner and full tomography.
-
Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach
High-precision shadow tomography of unknown quantum states has sample complexity Θ~(Γ_p/ε²), with Γ_p characterized by the inverse Fisher information matrix of the optimal single-copy measurement.
-
Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
A quantum extension of the low-degree method shows that state designs imply computational hardness for many single-copy quantum measurement strategies, yielding new information-computation gaps.
-
Online Shadow Tomography Matching the Classical Bounds
Online shadow tomography can be solved with O(log m sqrt(log d)/eps^3) or O(sqrt(m)/eps^2) copies, matching known classical rates, but the first bound's key proof lemma contains an invalid inequality.
Discussion (0). Continue with ORCID to comment.