Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States
Abstract
We study coherent classical shadows protocols for an unknown d-dimensional quantum state of rank at most r, allowing an arbitrary joint measurement on all available copies. For observables with operator norm at most one and centered squared Frobenius norm at most F, we study the minumum number of copies T needed for the protocol to successed with propbability $1 - δ$. We prove a lower bound on T, that depends both on δ and the number M of post-measurement observables. Denoting ℓ=max{log(2M),log(1/δ)}, we show that T=Ω(min{√(rFℓ)/ε,(Fℓ)2/3/ε4/3}+ℓ/ε2) under the mild assumption log(2M)≲ dmin{r,F}. The lower bound nearly matches the known upper bound and matches the conjectural strengthening of the known upper bound. The proof is inspired by the framework of the proof of the lower bound for Boolean Hidden Matching. We develop a Gaussian-lift noise kernel that transfers forward and reverse Gaussian hypercontractivity to the Grassmannian, allowing us to bound the distinguishing advantage in an auxiliary game with a revealed query observable. We use Schur--Weyl structure and posterior moment bounds to control arbitrary coherent measurements on the source side.
Related
- Practical fermionic shadows enabled by improved sample-complexity bounds
- Finite-Sample Selected Covariance Spectra in Classical Shadows
- Verification Complexity and Extension of Classical Shadows
- An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
BibTeX
@misc{svetlichnyy2026optimal,
title = {{Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States}},
author = {Pavel Svetlichnyy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18031},
eprint = {2610.18031},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18031},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States
AU - Pavel Svetlichnyy
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18031
UR - https://arxiv.org/abs/2610.18031
AB - We study coherent classical shadows protocols for an unknown d-dimensional quantum state of rank at most r, allowing an arbitrary joint measurement on all available copies. For observables with operator norm at most one and centered squared Frobenius norm at most F, we study the minumum number of copies T needed for the protocol to successed with propbability $1 - δ$. We prove a lower bound on T, that depends both on δ and the number M of post-measurement observables. Denoting ℓ=max{log(2M),log(1/δ)}, we show that T=Ω(min{√(rFℓ)/ε,(Fℓ)^2/3/ε^4/3}+ℓ/ε^2) under the mild assumption log(2M)≲ dmin{r,F}. The lower bound nearly matches the known upper bound and matches the conjectural strengthening of the known upper bound. The proof is inspired by the framework of the proof of the lower bound for Boolean Hidden Matching. We develop a Gaussian-lift noise kernel that transfers forward and reverse Gaussian hypercontractivity to the Grassmannian, allowing us to bound the distinguishing advantage in an auxiliary game with a revealed query observable. We use Schur--Weyl structure and posterior moment bounds to control arbitrary coherent measurements on the source side.
ER -