Adaptive Online Learning of Quantum States
1Department of Computer Science, Princeton University, NJ 08540, USA
2Google DeepMind Princeton, NJ 08542, USA
3Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, China
4School of Computer Science, Peking University, 100871 Beijing, China
| Published: | 2024-09-12, volume 8, page 1471 |
| Eprint: | arXiv:2206.00220v2 |
| Doi: | https://doi.org/10.22331/q-2024-09-12-1471 |
| Citation: | Quantum 8, 1471 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
Featured image: Comparison between Algorithm 3 and non-adaptive RFTL in the $k$-shift setting.
Popular summary
However, current algorithms overlook an important factor in today's quantum computers: fluctuation of quantum states. Advanced quantum computers, such as those based on superconducting qubits, represent $|0\rangle$ and $|1\rangle$ using the ground and first excited states, respectively. Fluctuations must be carefully managed to ensure accurate computations. More broadly, fluctuations are common in quantum optical systems. This raises a key question: how can we learn dynamic quantum states from the perspective of machine learning? In this paper, we apply adaptive online learning techniques to tackle this challenge, achieving results that scale polynomially in the number of qubits and sublinearly in the number of measurements, under the metric of adaptive and dynamic regret.
► BibTeX data
► References
[1] Scott Aaronson. ``Shadow tomography of quantum states''. SIAM Journal on Computing 49, STOC18–368–STOC18–394 (2020).
https://doi.org/10.1137/18M120275X
[2] Costin Bădescu and Ryan O'Donnell. ``Improved quantum data analysis''. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Pages 1398–1411. (2021).
https://doi.org/10.1145/3406325.3451109
[3] Fernando G.S.L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. ``Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning''. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming. Volume 132 of Leibniz International Proceedings in Informatics, pages 27:1–27:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2019).
https://doi.org/10.4230/LIPIcs.ICALP.2019.27
[4] Scott Aaronson and Guy N Rothblum. ``Gentle measurement of quantum states and differential privacy''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 322–333. (2019).
https://doi.org/10.1145/3313276.3316378
[5] Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. ``Online learning of quantum states''. Advances in neural information processing systems 31 (2018). url: https://doi.org/10.1088/1742-5468/ab3988.
https://doi.org/10.1088/1742-5468/ab3988
[6] Feidiao Yang, Jiaqing Jiang, Jialin Zhang, and Xiaoming Sun. ``Revisiting online quantum state learning''. In Proceedings of the AAAI Conference on Artificial Intelligence. Volume 34, pages 6607–6614. (2020).
https://doi.org/10.1609/aaai.v34i04.6136
[7] Yifang Chen and Xin Wang. ``More practical and adaptive algorithms for online quantum state learning'' (2020). arXiv:2006.01013.
arXiv:2006.01013
[8] Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. ``Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states''. Quantum 6, 749 (2022).
https://doi.org/10.22331/q-2022-06-29-749
[9] Julian Zimmert, Naman Agarwal, and Satyen Kale. ``Pushing the efficiency-regret pareto frontier for online learning of portfolios and quantum states''. In Conference on Learning Theory. Pages 182–226. PMLR (2022). url: https://proceedings.mlr.press/v178/zimmert22a.html.
https://proceedings.mlr.press/v178/zimmert22a.html
[10] Harrison Ball, Thomas M. Stace, Steven T. Flammia, and Michael J. Biercuk. ``Effect of noise correlations on randomized benchmarking''. Physical Review A 93, 022303 (2016).
https://doi.org/10.1103/PhysRevA.93.022303
[11] Daniel Greenbaum and Zachary Dutton. ``Modeling coherent errors in quantum error correction''. Quantum Science and Technology 3, 015007 (2017).
https://doi.org/10.1088/2058-9565/aa9a06
[12] Richard Kueng, David M. Long, Andrew C. Doherty, and Steven T. Flammia. ``Comparing experiments to the fault-tolerance threshold''. Physical Review Letters 117, 170502 (2016).
https://doi.org/10.1103/PhysRevLett.117.170502
[13] Joel J. Wallman. ``Bounding experimental quantum error rates relative to fault-tolerant thresholds'' (2015). arXiv:1511.00727.
arXiv:1511.00727
[14] Joel Wallman, Chris Granade, Robin Harper, and Steven T. Flammia. ``Estimating the coherence of noise''. New Journal of Physics 17, 113020 (2015).
https://doi.org/10.1088/1367-2630/17/11/113020
[15] Quoc Hoan Tran and Kohei Nakajima. ``Learning temporal quantum tomography''. Physical Review Letters 127, 260401 (2021).
https://doi.org/10.1103/PhysRevLett.127.260401
[16] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[17] Martin Zinkevich. ``Online convex programming and generalized infinitesimal gradient ascent''. In International Conference on Machine Learning. Pages 928–936. (2003). url: https://dl.acm.org/doi/10.5555/3041838.3041955.
https://dl.acm.org/doi/10.5555/3041838.3041955
[18] Elad Hazan and Comandur Seshadhri. ``Efficient learning algorithms for changing environments''. In International Conference on Machine Learning. Pages 393–400. (2009).
https://doi.org/10.1145/1553374.1553425
[19] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. ``Strongly adaptive online learning''. In International Conference on Machine Learning. Pages 1405–1411. PMLR (2015). url: https://proceedings.mlr.press/v37/daniely15.html.
https://proceedings.mlr.press/v37/daniely15.html
[20] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. ``Improved strongly adaptive online learning using coin betting''. In Artificial Intelligence and Statistics. Pages 943–951. PMLR (2017). url: https://proceedings.mlr.press/v54/jun17a.html.
https://proceedings.mlr.press/v54/jun17a.html
[21] Ashok Cutkosky. ``Parameter-free, dynamic, and strongly-adaptive online learning''. In International Conference on Machine Learning. Pages 2250–2259. PMLR (2020). url: https://proceedings.mlr.press/v119/cutkosky20a.html.
https://proceedings.mlr.press/v119/cutkosky20a.html
[22] Koenraad M. R. Audenaert. ``A sharp continuity estimate for the von Neumann entropy''. Journal of Physics A: Mathematical and Theoretical 40, 8127–8136 (2007).
https://doi.org/10.1088/1751-8113/40/28/s18
[23] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, and et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[24] IBM Quantum. ``Pushing quantum performance forward with our highest quantum volume yet''. https://research.ibm.com/blog/quantum-volume-256 (2022). Accessed: 2022-05-13.
https://research.ibm.com/blog/quantum-volume-256
[25] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, and et al. ``Quantum computational advantage via 60-qubit 24-cycle random circuit sampling''. Science Bulletin 67, 240–245 (2022).
https://doi.org/10.1016/j.scib.2021.10.017
[26] Weiyuan Gong and Scott Aaronson. ``Learning distributions over quantum measurement outcomes''. In International Conference on Machine Learning. Pages 11598–11613. PMLR (2023). url: https://proceedings.mlr.press/v202/gong23a.html.
https://proceedings.mlr.press/v202/gong23a.html
[27] Elad Hazan. ``Introduction to online convex optimization''. Foundations and Trends® in Optimization 2, 157–325 (2016).
https://doi.org/10.1561/2400000013
[28] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. ``Adaptive online learning in dynamic environments''. In Advances in Neural Information Processing Systems. Volume 31. (2018). arXiv:1810.10815.
arXiv:1810.10815
[29] M. Fannes. ``A continuity property of the entropy density for spin lattice systems''. Communications in Mathematical Physics 31, 291–294 (1973).
https://doi.org/10.1007/BF01646490
[30] Michael M. Wolf, Frank Verstraete, Matthew B. Hastings, and J. Ignacio Cirac. ``Area laws in quantum systems: mutual information and correlations''. Physical Review Letters 100, 070502 (2008).
https://doi.org/10.1103/PhysRevLett.100.070502
[31] Johan Åberg. ``Catalytic coherence''. Physical Review Letters 113, 150402 (2014).
https://doi.org/10.1103/PhysRevLett.113.150402
[32] Andreas Winter and Dong Yang. ``Operational resource theory of coherence''. Physical Review Letters 116, 120404 (2016).
https://doi.org/10.1103/PhysRevLett.116.120404
[33] Eric Chitambar and Gilad Gour. ``Quantum resource theories''. Reviews of Modern Physics 91, 025001 (2019).
https://doi.org/10.1103/RevModPhys.91.025001
[34] Eric Hall and Rebecca Willett. ``Dynamical models and tracking regret in online convex programming''. In International Conference on Machine Learning. Pages 579–587. PMLR (2013). url: https://proceedings.mlr.press/v28/hall13.html.
https://proceedings.mlr.press/v28/hall13.html
[35] J.R. Johansson, P.D. Nation, and Franco Nori. ``QuTiP: An open-source Python framework for the dynamics of open quantum systems''. Computer Physics Communications 183, 1760–1772 (2012).
https://doi.org/10.1016/j.cpc.2012.02.021
[36] J.R. Johansson, P.D. Nation, and Franco Nori. ``QuTiP 2: A Python framework for the dynamics of open quantum systems''. Computer Physics Communications 184, 1234–1240 (2013).
https://doi.org/10.1016/j.cpc.2012.11.019
[37] Asad Raza, Matthias C. Caro, Jens Eisert, and Sumeet Khatri. ``Online learning of quantum processes'' (2024). arXiv:2406.04250.
arXiv:2406.04250
[38] Heinz H. Bauschke and Patrick L. Combettes. ``Convex analysis and monotone operator theory in hilbert spaces''. Springer Publishing Company, Incorporated. (2011). 1st edition.
https://doi.org/10.1007/978-3-319-48311-5
[39] Eric P. Hanson and Nilanjana Datta. ``Maximum and minimum entropy states yielding local continuity bounds''. Journal of Mathematical Physics 59, 042204 (2018).
https://doi.org/10.1063/1.5000120
[40] Joel A. Tropp. ``From joint convexity of quantum relative entropy to a concavity theorem of lieb''. Proceedings of the American Mathematical Society 140, 1757–1760 (2012). url: http://www.jstor.org/stable/41505631.
http://www.jstor.org/stable/41505631
[41] Rajendra Bhatia. ``Matrix analysis''. Volume 169. Springer. New York (1997).
https://doi.org/10.1007/978-1-4612-0653-8
[42] Göran Lindblad. ``Completely positive maps and entropy inequalities''. Communications in Mathematical Physics 40, 147–151 (1975).
https://doi.org/10.1007/BF01609396
[43] William F. Stinespring. ``Positive functions on c*-algebras''. Proceedings of the American Mathematical Society 6, 211–216 (1955). url: https://community.ams.org/journals/proc/1955-006-02/S0002-9939-1955-0069403-4/S0002-9939-1955-0069403-4.pdf.
https://community.ams.org/journals/proc/1955-006-02/S0002-9939-1955-0069403-4/S0002-9939-1955-0069403-4.pdf
[44] Emanuel Knill. ``Approximation by quantum circuits'' (1995). arXiv:quant-ph/9508006.
arXiv:quant-ph/9508006
Cited by
[1] Sitan Chen and Weiyuan Gong, "Efficient Pauli Channel Estimation with Logarithmic Quantum Memory", PRX Quantum 6 2, 020323 (2025).
[2] J Knörzer, X Liu, B F Schiffer, and J Tura, "Distributed quantum information processing: a review of recent progress", Reports on Progress in Physics 89 7, 074401 (2026).
[3] Akshay Bansal, Ian George, Soumik Ghosh, Jamie Sikora, and Alice Zheng, "Online learning of a panoply of quantum objects", Quantum Machine Intelligence 7 2, 78 (2025).
[4] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", Nature Reviews Physics 6 1, 59 (2024).
[5] Asad Raza, Matthias C. Caro, Jens Eisert, and Sumeet Khatri, "Online learning of quantum processes", arXiv:2406.04250, (2024).
[6] Sitan Chen and Weiyuan Gong, "Efficient Pauli channel estimation with logarithmic quantum memory", arXiv:2309.14326, (2023).
[7] Steven T. Flammia and Ryan O'Donnell, "Quantum chi-squared tomography and mutual information testing", Quantum 8, 1381 (2024).
[8] Yuxuan Du, Yibo Yang, Tongliang Liu, Zhouchen Lin, Bernard Ghanem, and Dacheng Tao, "ShadowNet for Data-Centric Quantum System Learning", arXiv:2308.11290, (2023).
[9] Maxime Meyer, Soumik Adhikary, Naixu Guo, and Patrick Rebentrost, "Online Learning of Pure States is as Hard as Mixed States", arXiv:2502.00823, (2025).
[10] Naixu Guo, Feng Pan, and Patrick Rebentrost, "Estimating properties of a quantum state by importance-sampled operator shadows", arXiv:2305.09374, (2023).
[11] Wei-Fu Tseng, Kai-Chun Chen, Zi-Hong Xiao, and Yen-Huan Li, "Online Learning Quantum States with the Logarithmic Loss via VB-FTRL", arXiv:2311.04237, (2023).
[12] Taiga Hiroka and Min-Hsiu Hsieh, "Computational Complexity of Learning Efficiently Generatable Pure States", arXiv:2410.04373, (2024).
[13] Chung-En Tsai, Hao-Chung Cheng, and Yen-Huan Li, "Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States", arXiv:2210.00997, (2022).
[14] Jian-Feng Cai, Yuling Jiao, Yinan Li, Xiliang Lu, Jerry Zhijian Yang, and Juntao You, "Online Quantum State Tomography via Stochastic Gradient Descent", arXiv:2507.07601, (2025).
[15] Markus Rambach, Akram Youssry, Marco Tomamichel, and Jacquiline Romero, "Efficient quantum state tracking in noisy environments", Quantum Science and Technology 8 1, 015010 (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 07:27:07) and SAO/NASA ADS (last updated successfully 2026-08-09 19:09:12). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch ADS cited-by data during last attempt 2026-08-10 07:27:07: Cannot retrieve data from ADS due to rate limitations.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.