{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T03:09:52Z","timestamp":1770088192174,"version":"3.49.0"},"reference-count":44,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["92365117"],"award-info":[{"award-number":["92365117"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372006"],"award-info":[{"award-number":["62372006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"The problem of efficient quantum state learning, also called shadow tomography, aims to comprehend an unknown d<\/mml:mi><\/mml:math>-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.<\/jats:p>","DOI":"10.22331\/q-2024-09-12-1471","type":"journal-article","created":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T14:58:53Z","timestamp":1726153133000},"page":"1471","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Adaptive Online Learning of Quantum States"],"prefix":"10.22331","volume":"8","author":[{"given":"Xinyi","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science, Princeton University, NJ 08540, USA"},{"name":"Google DeepMind Princeton, NJ 08542, USA"}]},{"given":"Elad","family":"Hazan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Princeton University, NJ 08540, USA"},{"name":"Google DeepMind Princeton, NJ 08542, USA"}]},{"given":"Tongyang","family":"Li","sequence":"additional","affiliation":[{"name":"Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, China"},{"name":"School of Computer Science, Peking University, 100871 Beijing, China"}]},{"given":"Zhou","family":"Lu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Princeton University, NJ 08540, USA"},{"name":"Google DeepMind Princeton, NJ 08542, USA"}]},{"given":"Xinzhao","family":"Wang","sequence":"additional","affiliation":[{"name":"Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, China"},{"name":"School of Computer Science, Peking University, 100871 Beijing, China"}]},{"given":"Rui","family":"Yang","sequence":"additional","affiliation":[{"name":"Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, China"},{"name":"School of Computer Science, Peking University, 100871 Beijing, China"}]}],"member":"9598","published-online":{"date-parts":[[2024,9,12]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. ``Shadow tomography of quantum states''. SIAM Journal on Computing 49, STOC18\u2013368\u2013STOC18\u2013394 (2020).","DOI":"10.1137\/18M120275X"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Costin B\u0103descu and Ryan O'Donnell. ``Improved quantum data analysis''. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Pages 1398\u20131411. (2021).","DOI":"10.1145\/3406325.3451109"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o, 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\u201327:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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\u2013333. (2019).","DOI":"10.1145\/3313276.3316378"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1742-5468\/ab3988"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u20136614. (2020).","DOI":"10.1609\/aaai.v34i04.6136"},{"key":"6","unstructured":"Yifang Chen and Xin Wang. ``More practical and adaptive algorithms for online quantum state learning'' (2020). arXiv:2006.01013."},{"key":"7","doi-asserted-by":"publisher","unstructured":"Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. ``Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states''. Quantum 6, 749 (2022).","DOI":"10.22331\/q-2022-06-29-749"},{"key":"8","unstructured":"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\u2013226. PMLR (2022). url: https:\/\/proceedings.mlr.press\/v178\/zimmert22a.html."},{"key":"9","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.93.022303"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Daniel Greenbaum and Zachary Dutton. ``Modeling coherent errors in quantum error correction''. Quantum Science and Technology 3, 015007 (2017).","DOI":"10.1088\/2058-9565\/aa9a06"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.117.170502"},{"key":"12","unstructured":"Joel J. Wallman. ``Bounding experimental quantum error rates relative to fault-tolerant thresholds'' (2015). arXiv:1511.00727."},{"key":"13","doi-asserted-by":"publisher","unstructured":"Joel Wallman, Chris Granade, Robin Harper, and Steven T. Flammia. ``Estimating the coherence of noise''. New Journal of Physics 17, 113020 (2015).","DOI":"10.1088\/1367-2630\/17\/11\/113020"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Quoc Hoan Tran and Kohei Nakajima. ``Learning temporal quantum tomography''. Physical Review Letters 127, 260401 (2021).","DOI":"10.1103\/PhysRevLett.127.260401"},{"key":"15","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"16","unstructured":"Martin Zinkevich. ``Online convex programming and generalized infinitesimal gradient ascent''. In International Conference on Machine Learning. Pages 928\u2013936. (2003). url: https:\/\/dl.acm.org\/doi\/10.5555\/3041838.3041955."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Elad Hazan and Comandur Seshadhri. ``Efficient learning algorithms for changing environments''. In International Conference on Machine Learning. Pages 393\u2013400. (2009).","DOI":"10.1145\/1553374.1553425"},{"key":"18","unstructured":"Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. ``Strongly adaptive online learning''. In International Conference on Machine Learning. Pages 1405\u20131411. PMLR (2015). url: https:\/\/proceedings.mlr.press\/v37\/daniely15.html."},{"key":"19","unstructured":"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\u2013951. PMLR (2017). url: https:\/\/proceedings.mlr.press\/v54\/jun17a.html."},{"key":"20","unstructured":"Ashok Cutkosky. ``Parameter-free, dynamic, and strongly-adaptive online learning''. In International Conference on Machine Learning. Pages 2250\u20132259. PMLR (2020). url: https:\/\/proceedings.mlr.press\/v119\/cutkosky20a.html."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Koenraad M. R. Audenaert. ``A sharp continuity estimate for the von Neumann entropy''. Journal of Physics A: Mathematical and Theoretical 40, 8127\u20138136 (2007).","DOI":"10.1088\/1751-8113\/40\/28\/s18"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, and et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505\u2013510 (2019).","DOI":"10.1038\/s41586-019-1666-5"},{"key":"23","unstructured":"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."},{"key":"24","doi-asserted-by":"publisher","unstructured":"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\u2013245 (2022).","DOI":"10.1016\/j.scib.2021.10.017"},{"key":"25","unstructured":"Weiyuan Gong and Scott Aaronson. ``Learning distributions over quantum measurement outcomes''. In International Conference on Machine Learning. Pages 11598\u201311613. PMLR (2023). url: https:\/\/proceedings.mlr.press\/v202\/gong23a.html."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Elad Hazan. ``Introduction to online convex optimization''. Foundations and Trends\u00ae in Optimization 2, 157\u2013325 (2016).","DOI":"10.1561\/2400000013"},{"key":"27","unstructured":"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."},{"key":"28","doi-asserted-by":"publisher","unstructured":"M. Fannes. ``A continuity property of the entropy density for spin lattice systems''. Communications in Mathematical Physics 31, 291\u2013294 (1973).","DOI":"10.1007\/BF01646490"},{"key":"29","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.100.070502"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Johan \u00c5berg. ``Catalytic coherence''. Physical Review Letters 113, 150402 (2014).","DOI":"10.1103\/PhysRevLett.113.150402"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Andreas Winter and Dong Yang. ``Operational resource theory of coherence''. Physical Review Letters 116, 120404 (2016).","DOI":"10.1103\/PhysRevLett.116.120404"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Eric Chitambar and Gilad Gour. ``Quantum resource theories''. Reviews of Modern Physics 91, 025001 (2019).","DOI":"10.1103\/RevModPhys.91.025001"},{"key":"33","unstructured":"Eric Hall and Rebecca Willett. ``Dynamical models and tracking regret in online convex programming''. In International Conference on Machine Learning. Pages 579\u2013587. PMLR (2013). url: https:\/\/proceedings.mlr.press\/v28\/hall13.html."},{"key":"34","doi-asserted-by":"publisher","unstructured":"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\u20131772 (2012).","DOI":"10.1016\/j.cpc.2012.02.021"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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\u20131240 (2013).","DOI":"10.1016\/j.cpc.2012.11.019"},{"key":"36","unstructured":"Asad Raza, Matthias C. Caro, Jens Eisert, and Sumeet Khatri. ``Online learning of quantum processes'' (2024). arXiv:2406.04250."},{"key":"37","doi-asserted-by":"publisher","unstructured":"Heinz H. Bauschke and Patrick L. Combettes. ``Convex analysis and monotone operator theory in hilbert spaces''. Springer Publishing Company, Incorporated. (2011). 1st edition.","DOI":"10.1007\/978-3-319-48311-5"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Eric P. Hanson and Nilanjana Datta. ``Maximum and minimum entropy states yielding local continuity bounds''. Journal of Mathematical Physics 59, 042204 (2018).","DOI":"10.1063\/1.5000120"},{"key":"39","doi-asserted-by":"crossref","unstructured":"Joel A. Tropp. ``From joint convexity of quantum relative entropy to a concavity theorem of lieb''. Proceedings of the American Mathematical Society 140, 1757\u20131760 (2012). url: http:\/\/www.jstor.org\/stable\/41505631.","DOI":"10.1090\/S0002-9939-2011-11141-9"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Rajendra Bhatia. ``Matrix analysis''. Volume 169. Springer. New York (1997).","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"41","doi-asserted-by":"publisher","unstructured":"G\u00f6ran Lindblad. ``Completely positive maps and entropy inequalities''. Communications in Mathematical Physics 40, 147\u2013151 (1975).","DOI":"10.1007\/BF01609396"},{"key":"42","unstructured":"William F. Stinespring. ``Positive functions on c*-algebras''. Proceedings of the American Mathematical Society 6, 211\u2013216 (1955). url: https:\/\/community.ams.org\/journals\/proc\/1955-006-02\/S0002-9939-1955-0069403-4\/S0002-9939-1955-0069403-4.pdf."},{"key":"43","unstructured":"Emanuel Knill. ``Approximation by quantum circuits'' (1995). arXiv:quant-ph\/9508006."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-12-1471\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T14:59:04Z","timestamp":1726153144000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-12-1471\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,12]]},"references-count":44,"URL":"https:\/\/doi.org\/10.22331\/q-2024-09-12-1471","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,12]]},"article-number":"1471"}}