Metraipolis › archive › dc_34b4e0d34a42

Dimension-Free Polylogarithmic Quantum Shadow Tomography — arXiv:2608.06345

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.06345
License (as archived)
CC0-1.0
Archived
2026-10-31T10:53:52.111Z
SHA-256 of the archived text
7f0c9b5b51b3be2ac07ee2e7669b5517fe27b551c1dd0ebc505fd556444ce72d
Stable URL of this page
https://metraipolis.com/documento/dc_34b4e0d34a42

How to cite

Dimension-Free Polylogarithmic Quantum Shadow Tomography — arXiv:2608.06345 — arXiv (en), https://arxiv.org/abs/2608.06345 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_34b4e0d34a42 (Metraipolis archive dc_34b4e0d34a42, sha256 7f0c9b5b51b3be2ac07ee2e7669b5517fe27b551c1dd0ebc505fd556444ce72d)
BibTeX
@misc{dc34b4e0d34a42,
  title = {Dimension-Free Polylogarithmic Quantum Shadow Tomography — arXiv:2608.06345},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.06345},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_34b4e0d34a42; sha256 7f0c9b5b51b3be2ac07ee2e7669b5517fe27b551c1dd0ebc505fd556444ce72d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06345. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown $d$-dimensional quantum state $\rho$ and a known collection of observables $E_1,\ldots,E_M$, the goal is to estimate all expectation values $\{\text{Tr}(\rho E_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ with probability at least $1-\delta$. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on $M$, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity \[ O\left( \frac{\log(M)\log(M/\delta)}{\varepsilon^2} \right), \] which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-08-07 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2608.06345 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T10:40:45.630Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).