Randomized measurement protocols such as classical shadows represent powerful resources for quantum technologies, with applications ranging from quantum state characterization and process tomography to machine learning and error mitigation. Recently, the notion of measurement dual frames, in which classical shadows are generalized to dual operators of positive operator-valued measure (POVM) effects, resurfaced in the literature. This brought attention to additional degrees of freedom in the postprocessing stage of randomized measurements that are often neglected by established techniques. In this work, we leverage dual frames to construct improved observable estimators from informationally complete measurement samples. We introduce novel classes of parametrized frame superoperators and optimization-free dual frames based on empirical frequencies, which offer advantages over their canonical counterparts while retaining computational efficiency. Remarkably, this comes at almost no quantum or classical cost, thus rendering dual frame optimization a valuable addition to the randomized measurement toolbox. Published by the American Physical Society 2024
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown
d-dimensional quantum state
ρ and a known set of observables
{Oi}i=1m, the goal is to estimate expectation values
{tr(Oiρ)}i=1m to accuracy
ε in
Lp-norm, using possibly adaptive measurements that act on
O(polylog(d)) number of copies of
ρ at a time. We focus on the regime where
ε is below an instance-dependent threshold.
Our main contribution is an instance-optimal characterization of the sample complexity as
Θ~(Γp/ε2), where
Γp is a function of
{Oi}i=1m defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with
L∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form
∑i=1mαiOi with
∥α∥q=1 (where
q is dual to
p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of
Θ(Γpob/ε2). We then show
Θ~(Γp/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably,
Γ∞ob=Γ∞. In both cases, allowing
c-copy measurements improves the sample complexity by at most
Ω(1/c).
Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.
Quantum process tomography is a powerful tool for understanding quantum channels and characterizing the properties of quantum devices. Inspired by recent advances using classical shadows in quantum state tomography [H.-Y. Huang, R. Kueng, and J. Preskill, .], we have developed ShadowQPT, a classical shadow method for quantum process tomography. We introduce two related formulations with and without ancilla qubits. ShadowQPT stochastically reconstructs the Choi matrix of the device allowing for an classical evaluation of the device on arbitrary inputs with respect to arbitrary outputs. Using shadows, we then show how to compute overlaps, generate all k -weight reduced processes, and perform reconstruction via Hamiltonian learning. These latter two tasks are efficient for large systems as the number of quantum measurements needed scales only logarithmically with the number of qubits. A number of additional approximations and improvements are developed, including the use of a pair-factorized Clifford shadow and a series of postprocessing techniques that significantly enhance the accuracy for recovering the quantum channel. We have implemented ShadowQPT using both Pauli and Clifford measurements on the IonQ trapped ion quantum computer for quantum processes up to n=4 qubits, and we achieved good performance. Published by the American Physical Society 2024
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown
d-dimensional quantum state
ρ and a known collection of observables
E1,…,EM, the goal is to estimate all expectation values
{Tr(ρEi)}i=1M to additive accuracy
ε with probability at least
1−δ.
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(ε2log(M)log(M/δ)), 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.
Efficiently learning expectation values of a quantum state using classical shadow tomography has become a fundamental task in quantum information theory. In a classical shadows protocol, one measures a state in a chosen basis W after it has evolved under a unitary transformation randomly sampled from a chosen distribution U. In this work we study the case where U corresponds to either local or global orthogonal Clifford gates, and W consists of real-valued vectors. Our results show that for various situations of interest, this ``real'' classical shadow protocol improves the sample complexity over the standard scheme based on general Clifford unitaries. For example, when one is interested in estimating the expectation values of arbitrary real-valued observables, global orthogonal Cliffords decrease the required number of samples by a factor of two. More dramatically, for k-local observables composed only of real-valued Pauli operators, sampling local orthogonal Cliffords leads to a reduction by an exponential-in-k factor in the sample complexity over local unitary Cliffords. Finally, we show that by measuring in a basis containing complex-valued vectors, orthogonal shadows can, in the limit of large system size, exactly reproduce the original unitary shadows protocol.
Accurate estimation of observables in quantum systems is a central challenge in quantum information science, yet practical implementations are fundamentally constrained by the limited number of measurement shots. In this work we explore a variation of the classical shadows protocol in which the measurements are kept local while allowing the resulting classical shadows themselves to be correlated. By constructing locally optimal shadows, we obtain unbiased estimators that are competitive with state-of-the-art methods in terms of measurement overhead, while requiring only single-qubit measurements and allowing for the estimation of any observable in pure post-processing, reducing estimation errors by orders of magnitude over standard classical shadows. We validate our approach through numerical experiments on molecular Hamiltonians with up to 40 qubits consistently observing significant reductions in estimation errors, including for estimations of multiple chemically relevant observables simultaneously.