Optimal classical shadow estimation of unitary channels at Heisenberg limit

Abstract

Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown $d$-dimensional unitary $U$ and stores classical data that can later be used to predict expectation values $\mathrm{tr}[OU\rho U^{†}]$ for arbitrary input states $\rho$ and observables $O$. Here we propose a parallel and non-adaptive CSEU protocol that uses $\mathcal{O}(\min \{d{\epsilon }^{-2},d^{3/2}{\epsilon }^{-1}\})$ queries to $U$ when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error $\epsilon$ and is query-optimal, as we prove a matching lower bound $\Omega (\min \{d{\epsilon }^{-2},d^{3/2}{\epsilon }^{-1}\})$ for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.

arXiv comment28+59 pages, 8 figures, 1 table