Quantum state tomography is fundamental to quantum information processing but becomes infeasible at scale due to the exponential growth of the state space. Shadow tomography alleviates this challenge by focusing on predicting measurement outcomes rather than reconstructing the full state. Its online variant models adaptive and potentially adversarial measurement scenarios, where a learner sequentially predicts outcomes while competing with the best fixed quantum state in hindsight.
We show that exploiting additional structure in the measurements leads to significantly stronger regret guarantees. In particular, under the assumption that the adversarial measurements have bounded Frobenius norm, we analyze Projected Online Gradient Descent and derive regret bounds that depend on intrinsic structural properties, such as rank or sparsity, rather than the ambient Hilbert space dimension. As a complementary result, we show that one can achieve logarithmic regret, independent of both the number of qubits and measurement outcomes, for multi-outcome measurements under squared $L_2$ loss. These results demonstrate that incorporating realistic structural assumptions can substantially enhance the learnability of quantum states in online environments.
Quantum state tomography is fundamental to quantum information processing but becomes infeasible at scale due to the exponential growth of the state space. Shadow tomography alleviates this challenge by focusing on predicting measurement outcomes rather than reconstructing the full state. Its online variant models adaptive and potentially adversarial measurement scenarios, where a learner sequentially predicts outcomes while competing with the best fixed quantum state in hindsight.
We show that exploiting additional structure in the measurements leads to significantly stronger regret guarantees. In particular, under the assumption that the adversarial measurements have bounded Frobenius norm, we analyze Projected Online Gradient Descent and derive regret bounds that depend on intrinsic structural properties, such as rank or sparsity, rather than the ambient Hilbert space dimension. As a complementary result, we show that one can achieve logarithmic regret, independent of both the number of qubits and measurement outcomes, for multi-outcome measurements under squared L2 loss. These results demonstrate that incorporating realistic structural assumptions can substantially enhance the learnability of quantum states in online environments.
Among recent insights into learning quantum states, online learning and shadow tomography procedures are notable for their ability to accurately predict expectation values even of adaptively chosen observables. In contrast to the state case, quantum process learning tasks with a similarly adaptive nature have received little attention. In this work, we investigate online learning tasks for quantum processes. Whereas online learning is infeasible for general quantum channels, we show that channels of bounded gate complexity as well as Pauli channels can be online learned in the regret and mistake-bounded models of online learning. In fact, we can online learn probabilistic mixtures of any exponentially large set of known channels. We also provide a provably sample-efficient shadow tomography procedure for Pauli channels. Our results extend beyond quantum channels to non-Markovian multi-time processes, with favorable regret and mistake bounds, as well as a shadow tomography procedure. We complement our online learning upper bounds with mistake as well as computational lower bounds. On the technical side, we make use of the multiplicative weights update algorithm, classical adaptive data analysis, and Bell sampling, as well as tools from the theory of quantum combs for multi-time quantum processes. Our work initiates a study of online learning for classes of quantum channels and, more generally, non-Markovian quantum processes. Given the importance of online learning for state shadow tomography, this may serve as a step towards quantum channel variants of adaptive shadow tomography.
We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2) and Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.
We initiate the study of sample-optimal quantum state tomography with minimal disturbance to the samples. Can we efficiently learn a precise description of a quantum state through sequential measurements of samples while at the same time ensuring that the post-measurement states are only minimally perturbed? We quantify the accumulated cost of the protocol over T samples by an additive regret objective, which controls the cumulative expected post-measurement infidelity of the consumed copies. The challenge is to balance informative measurements with measurements that keep this accumulated cost small. Here, we answer this question for all pure states by exhibiting an adaptive protocol whose expected regret is O(d3log2T) , while the infidelity of the online estimate after t samples scales as O(1/t) . We also prove a logarithmic lower bound, showing that for fixed dimension, the dependence on the number of samples is optimal up to one logarithmic factor.
The purpose of this research work is to learn the quantum states in an ideal environments analytically, computationally, and graphically. The analysis starts with the learning of quantum states in identity channels with the help of the Regularized Follow the Leader (RFTL) algorithm. Our machine will try to learn the states based on the previous information, which is called the online learning model. The objective of this problem is to minimize regret by utilizing a learning algorithm that successively anticipates quantum states through observed measurements and losses. We have to produce many copies of quantum state ρ to perform analysis on them, which indicates the use of the shadow tomography approach in an ideal situation. Our goal is to learn the shadow of the state ρ by using a series of measurement operators that have two outcomes in nature. Aaronson et al. [1] developed an online setting for a non-realizable case, where the maximum possible loss is O( √ Tn) for the best possible state up to T−measurements . It is noteworthy that this outcome is an extension of the Aaronson PAC-like findings [2]. GANIT J. Bangladesh Math. Soc. 43.1 (2023) 65-74
In Online Shadow Tomography, we are given copies of an unknown d-dimensional quantum state ρ, an adversary (adaptively) proposes a sequence of bounded observables A(1),…,A(m), and after each A(t) is given we must estimate Tr(A(t)ρ) to within ±ε. This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters m,d,ε, lagging behind the best known and classical rates, 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. Our first algorithm is the first to achieve o(log2m)-dependence together with poly(log(d)/ε); moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of d, and improves the best prior result by a mlogm factor.
The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.
We extend quantum state tomography with minimal cumulative disturbance, first investigated in [arXiv:2406.18370], to arbitrary finite-dimensional pure states. A learner sequentially receives fresh copies of an unknown pure state, chooses a rank-one projector for each copy using the previous outcomes, and performs the corresponding two-outcome projective measurement. The goal is to learn the state while keeping the chosen projectors close to the unknown state in order to minimize disturbance. The qubit solution relies on the special geometry of the Bloch sphere and does not extend directly to qudits, where pure states form a curved manifold. We show that this obstruction can be overcome by working locally on the pure-state manifold. The algorithm proceeds in epochs. In each epoch, it fixes a current estimate, measures pairs of nearby rank-one projectors obtained by moving in opposite tangent directions, and takes differences of the corresponding outcomes. This gives an exact linear observation of the tangent component of the error. The resulting local linear models are combined with a robust variance-adaptive estimator and a hot-start regularization that transfers precision across epochs. For every unknown pure state in dimension d, after T measured copies, our protocol achieves cumulative regret O(d3log2T), and at each intermediate time t≤T its current estimate has online infidelity O(d3log(T)/t). Hence, pure-state tomography with essentially no cumulative disturbance is not a peculiarity of qubits but a geometric phenomenon that persists for qudits.