Revisiting Online Quantum State Learning

Feidiao Yang, Jiaqing Jiang, Jialin Zhang, Xiaoming Sun

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:

  1. 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})$.
  2. 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.
  3. 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.

Average regret comparison across stochastic and adversarial settings for pure and mixed target states.

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

Abstract

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.
BibTeX
@inproceedings{yang2020revisiting,
  author = {Feidiao Yang and Jiaqing Jiang and Jialin Zhang and Xiaoming Sun},
  title = {{Revisiting Online Quantum State Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.6136},
}
Figure