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
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 this paper, we study the online quantum state learning problem which is recently proposed by Aaronson et al. (2018). In this problem, the learning algorithm sequentially predicts quantum states based on observed measurements and losses and the goal is to minimize the regret. In the previous work, the existing algorithms may output mixed quantum states. However, in many scenarios, the prediction of a pure quantum state is required. In this paper, we first propose a Follow-the-Perturbed-Leader (FTPL) algorithm that can guarantee to predict pure quantum states. Theoretical analysis shows that our algorithm can achieve an O(√T) expected regret under some reasonable settings. In the case that the pure state prediction is not mandatory, we propose another deterministic learning algorithm which is simpler and more efficient. The algorithm is based on the online gradient descent (OGD) method and can also achieve an O(√T) regret bound. The main technical contribution of this result is an algorithm of projecting an arbitrary Hermitian matrix onto the set of density matrices with respect to the Frobenius norm. We think this subroutine is of independent interest and can be widely used in many other problems in the quantum computing area. In addition to the theoretical analysis, we evaluate the algorithms with a series of simulation experiments. The experimental results show that our FTPL method and OGD method outperform the existing RFTL approach proposed by Aaronson et al. (2018) in almost all settings. In the implementation of the RFTL approach, we give a closed-form solution to the algorithm. This provides an efficient, accurate, and completely executable solution to the RFTL method.
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 online mirror descent and derive optimal regret bounds that depend on intrinsic structural properties, such as rank or sparsity in the standard basis, rather than the dimension of the measurement operators. As a complementary result, we also show that, even in the setting where adversarial measurements are known to be sparse in the Pauli basis commonly used in variational quantum eigensolvers and near-term quantum error mitigation, the underlying regret bound for learning quantum states is the same as that obtained in the generic setting, where the adversarial measurements are not known to possess any particular structure.
The problem of efficient quantum state learning, also called shadow tomography, aims to comprehend an unknown d -dimensional quantum state through POVMs. Yet, these states are rarely static; they evolve due to factors such as measurements, environmental noise, or inherent Hamiltonian state transitions. This paper leverages techniques from adaptive online learning to keep pace with such state changes.The key metrics considered for learning in these mutable environments are enhanced notions of regret, specifically adaptive and dynamic regret. We present adaptive and dynamic regret bounds for online shadow tomography, which are polynomial in the number of qubits and sublinear in the number of measurements. To support our theoretical findings, we include numerical experiments that validate our proposed models.
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.
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.
Online quantum state learning is a recently proposed problem by Aaronson et al. (2018), where the learner sequentially predicts n-qubit quantum states based on given measurements on states and noisy outcomes. In the previous work, the algorithms are worst-case optimal in general but fail in achieving tighter bounds in certain simpler or more practical cases. In this paper, we develop algorithms to advance the online learning of quantum states. First, we show that Regularized Follow-the-Leader (RFTL) method with Tallis-2 entropy can achieve an O(MT) total loss with perfect hindsight on the first T measurements with maximum rank M. This regret bound depends only on the maximum rank M of measurements rather than the number of qubits, which takes advantage of low-rank measurements. Second, we propose a parameter-free algorithm based on a classical adjusting learning rate schedule that can achieve a regret depending on the loss of best states in hindsight, which takes advantage of low noisy outcomes. Besides these more adaptive bounds, we also show that our RFTL with Tallis-2 entropy algorithm can be implemented efficiently on near-term quantum computing devices, which is not achievable in previous works.