Abstract
Characterizing unknown quantum states is a fundamental task in quantum information science. While full state tomography is computationally prohibitive for large systems, online learning offers a more efficient alternative. This paper presents significant advancements in online quantum state learning by introducing two new algorithms: Follow-the-Perturbed-Leader (FTPL) and a projected Online Gradient Descent (OGD). These methods address the practical need for pure state predictions and replace slow iterative solvers with exact, closed-form calculations. Experimental simulations demonstrate that these algorithms achieve superior regret bounds across various adversarial settings.
Introduction
The challenge of learning a quantum state—represented by a density matrix $\rho$—is central to the development of quantum technologies. Traditional methods require an exponential number of measurements as the system size grows. Online learning mitigates this by predicting states sequentially and minimizing "regret," the cumulative loss difference between the learner and the best fixed state in hindsight. However, existing approaches like Regularized Follow-the-Leader (RFTL) often suffer from high computational complexity and a bias toward predicting "mixed" states, which are less useful for many physical applications requiring "pure" (rank-1) states.
Algorithmic Innovations
The researchers propose three primary technical improvements to the online learning framework:
- Follow-the-Perturbed-Leader (FTPL): By incorporating a stochastic linear perturbation into the optimization objective, the authors prove that the resulting prediction is always a rank-1 matrix. This ensures the output is a pure quantum state while maintaining an optimal expected regret bound of $O(\sqrt{T})$.
- Projected Online Gradient Descent (OGD): The authors adapt OGD for quantum states using a novel projection subroutine. This method projects an arbitrary Hermitian matrix onto the set of valid density matrices by decomposing the matrix and projecting its eigenvalues onto a probability simplex. This approach is both exact and computationally efficient.
- Closed-form RFTL Solution: To improve the standard RFTL method (using von Neumann entropy), the authors derived an exact solution using matrix exponentials. This replaces approximate iterative solvers with a direct calculation, bridging the gap between theory and practice.
Experimental Evaluation
The algorithms were tested in a 4-qubit simulated environment ($16 \times 16$ density matrices) against both stochastic and "immediate-punishment" adversaries. The latter is an adaptive adversary designed to maximize the learner's error.
As shown in the figure above, both FTPL and OGD consistently outperform the traditional RFTL approach. In stochastic settings (subplots a and e), the performance is comparable across methods. However, in adversarial scenarios (subplots b, c, d, f, g, and h), FTPL and OGD demonstrate significantly lower and more stable average regret. Notably, when the target state is pure, FTPL maintains its advantage even against adversaries specifically designed to exploit its perturbation mechanism.
Conclusion
This work provides a more robust and physically grounded framework for online quantum state learning. By guaranteeing pure state predictions and providing exact computational solutions, FTPL and OGD represent a significant step forward. Future research will focus on improving the scaling of regret bounds relative to the number of qubits, as current bounds depend on the total dimension of the state space.
Summary updated