Online Shadow Tomography Matching the Classical Bounds

arXiv:2607.29686v1 Announce Type: new Abstract: In \emph{Online Shadow Tomography}, we are given copies of an unknown $d$-dimensional quantum state $\rho$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\Tr(A^{(t)}\rho)$ to within $\pm \epsilon$. This is the direct quantum generalization of the classical problem of \emph{Adaptive Data Analysis}. %The ``offline'' case, in which $A^{(1)}, \ldots, A^{(m)}$ are given upfront, is also a well-studied problem. The main goal is to minimize the number of copies, $n$, required. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, \epsilon$, lagging behind the best known and classical rates~\cite{bassily2021algorithmic}, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. The bound on the left is the first to achieve $o(\log^2 m)$-dependence together with $\poly(\log(d)/\eps)$; moreover, it improves all three exponents even in the \emph{Offline} Shadow Tomography setting. The bound on the right is known to be optimal among bounds independent of~$d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron--Stein decomposition.

Abstract:In \emph{Online Shadow Tomography}, we are given copies of an unknown $d$-dimensional quantum state $\rho$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\Tr(A^{(t)}\rho)$ to within $\pm \epsilon$. This is the direct quantum generalization of the classical problem of \emph{Adaptive Data Analysis}. %The ``offline'' case, in which $A^{(1)}, \ldots, A^{(m)}$ are given upfront, is also a well-studied problem. The main goal is to minimize the number of copies, $n$, required. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, \epsilon$, lagging behind the best known and classical rates~\cite{bassily2021algorithmic}, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. The bound on the left is the first to achieve $o(\log^2 m)$-dependence together with $\poly(\log(d)/\eps)$; moreover, it improves all three exponents even in the \emph{Offline} Shadow Tomography setting. The bound on the right is known to be optimal among bounds independent of~$d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron--Stein decomposition.

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)

arXiv:2607.29686 [quant-ph]

(or arXiv:2607.29686v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.29686 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Online Shadow Tomography Matching the Classical Bounds

Related coverage