Shadow tomography of quantum states with prediction

Abstract

The shadow tomography problem introduced by [1] is an important problem in quantum computing. Given an unknown n-qubit quantum state \rho, the goal is to estimate \mathrm{t}\mathrm{r}(F_1\rho ),\dots ,\mathrm{t}\mathrm{r}(F_M\rho ) using as least copies of \rho as possible, within an additive error of \epsilon, where F_1,\dots ,F_M are known 2-outcome measurements. In this paper, we consider the shadow tomography problem with a potentially inaccurate prediction \varrho of the true state \rho. This corresponds to practical cases where we possess prior knowledge of the unknown state. For example, in quantum verification or calibration, we may be aware of the quantum state that the quantum device is expected to generate. However, the actual state it generates may have deviations. We introduce an algorithm with sample complexity \tilde{\mathcal{O}}(nmax\{\Vert \rho -\varrho {\Vert }_1,\epsilon \}{\log }^{2}M/{\epsilon }^4). In the generic case, even if the prediction can be arbitrarily bad, our algorithm has the same complexity as the best algorithm without prediction [2]. At the same time, as the prediction quality improves, the sample complexity can be reduced smoothly to \tilde{\mathcal{O}}(n{\log }^{2}M/{\epsilon }^3) when the trace distance between the prediction and the unknown state is \mathrm{\Theta } (\epsilon ). Furthermore, we conduct numerical experiments to validate our theoretical analysis. The experiments are constructed to simulate noisy quantum circuits that reflect possible real scenarios in quantum verification or calibration. Notably, our algorithm outperforms the previous work without prediction in most settings.

Graphical abstract

Keywords

shadow tomography / online learning / quantum state learning / FTRL / quantum machine learning

Jiyu Jiang is a master’s student in the School of Data Science, Fudan University, China under the supervision of Prof. Meiyue Shao. He is interested in quantum computing and machine learning

Zongqi Wan is a PhD student at the Institute of Computing Technology, Chinese Academy of Sciences, China under the supervision of Prof. Jialin Zhang. He is interested in several directions of theoretical computer science and machine learning, including bandit theory, submodular maximization, and auction theory

Tongyang Li is an assistant professor at Center on Frontiers of Computing Studies, School of Computer Science, Peking University, China. His research focuses on quantum algorithms, including topics such as quantum algorithms for machine learning and optimization, quantum query complexity, quantum simulation, and quantum walks

Meiyue Shao is an associate professor in the School of Data Science at Fudan University, China. He received his PhD in mathematics from EPF Lausanne in 2014. Before joining Fudan University, China in 2019, he worked in the Computational Research Division at Lawrence Berkeley National Laboratory as a postdoctoral fellow and then as a project scientist. His research interests include numerical linear, high performance computing, and computational quantum mechanics

Jialin Zhang is currently a professor in Institute of Computing Technology, Chinese Academy of Science, China. Prior to ICT, she was a postdoctoral researcher in University of Southern California, USA. She received her PhD in applied mathematics from Tsinghua University under the supervision of Andrew Chi-Chih Yao. Her research interest includes quantum computing, submodular maximization, approximation algorithm, and algorithmic game theory

References

[1] Aaronson S. Shadow tomography of quantum states. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, 325−338

[2] Bădescu C, O’Donnell R. Improved quantum data analysis. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, 1398−1411

[3] Huang X W, Luo J Q, Li L. Quantum speedup and limitations on matroid property problems. Frontiers of Computer Science, 2024, 18( 4): 184905

[4] Paris M, Řeháček J. Quantum State Estimation. Berlin: Springer, 2004

[5] Innan N, Siddiqui O I, Arora S, Ghosh T, Koçak Y P, Paragas D, Galib A A O, Khan M A Z, Bennai M. Quantum state tomography using quantum machine learning. Quantum Machine Intelligence, 2024, 6( 1): 28

[6] Cramer M, Plenio M B, Flammia S T, Somma R, Gross D, Bartlett S D, Landon-Cardinal O, Poulin D, Liu Y K. Efficient quantum state tomography. Nature Communications, 2010, 1: 149

[7] O’Donnell R, Wright J. Efficient quantum tomography. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. 2016, 899−912

[8] Wright J. How to learn a quantum state. Carnegie Mellon University, Dissertation, 2016

[9] Haah J, Harrow A W, Ji Z, Wu X, Yu N. Sample-optimal tomography of quantum states. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. 2016, 913−925

[10] Chen S, Huang B, Li J, Liu A, Sellke M. When does adaptivity help for quantum state learning? In: Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 2023, 391−404

[11] Lanyon B P, Maier C, Holzäpfel M, Baumgratz T, Hempel C, Jurcevic P, Dhand I, Buyskikh A S, Daley A J, Cramer M, Plenio M B, Blatt R, Roos C F. Efficient tomography of a quantum many-body system. Nature Physics, 2017, 13( 12): 1158–1162

[12] Carrasquilla J, Torlai G, Melko R G, Aolita L. Reconstructing quantum states with generative models. Nature Machine Intelligence, 2019, 1( 3): 155–161

[13] Torlai G, Mazzola G, Carrasquilla J, Troyer M, Melko R, Carleo G. Neural-network quantum state tomography. Nature Physics, 2018, 14( 5): 447–450

[14] Aaronson S, Chen X, Hazan E, Kale S. Online learning of quantum states. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, 8976−8986

[15] Hazan E. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2016, 2(3−4): 157−325

[16] Sack S H, Medina R A, Michailidis A A, Kueng R, Serbyn M. Avoiding barren plateaus using classical shadows. PRX Quantum, 2022, 3( 2): 020365

[17] McClean J R, Boixo S, Smelyanskiy V N, Babbush R, Neven H. Barren plateaus in quantum neural network training landscapes. Nature Communications, 2018, 9( 1): 4812

[18] Cerezo M, Arrasmith A, Babbush R, Benjamin S C, Endo S, Fujii K, McClean J R, Mitarai K, Yuan X, Cincio L, Coles P J. Variational quantum algorithms. Nature Reviews Physics, 2021, 3( 9): 625–644

[19] Huang H Y, Kueng R, Preskill J. Predicting many properties of a quantum system from very few measurements. Nature Physics, 2020, 16( 10): 1050–1057

[20] Huang H Y, Kueng R, Torlai G, Albert V V, Preskill J. Provably efficient machine learning for quantum many-body problems. Science, 2022, 377( 6613): eabk3333

[21] Chen Y, Wang X. More practical and adaptive algorithms for online quantum state learning. 2020, arXiv preprint arXiv: 2006.01013

[22] Yang F, Jiang J, Zhang J, Sun X. Revisiting online quantum state learning. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 6607−6614

[23] Chen X, Hazan E, Li T, Lu Z, Wang X, Yang R. Adaptive online learning of quantum states. 2022, arXiv preprint arXiv: 2206.00220

[24] Gong W, Aaronson S. Learning distributions over quantum measurement outcomes. In: Proceedings of the 40th International Conference on Machine Learning. 2023, 11598−11613

[25] Yin X F, Du Y, Fei Y Y, Zhang R, Liu L Z, Mao Y, Liu T, Hsieh M H, Li L, Liu N L, Tao D, Chen Y A, Pan J W. Efficient bipartite entanglement detection scheme with a quantum adversarial solver. Physical Review Letters, 2022, 128( 11): 110501

[26] Aaronson S, Rothblum G N. Gentle measurement of quantum states and differential privacy. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, 322−333

[27] Chen S, Cotler J, Huang H Y, Li J. Exponential separations between learning with and without quantum memory. In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS). 2022, 574−585

[28] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010

[29] Osamu H. Application of quantum Pinsker inequality to quantum communications. 2020, arXiv preprint arXiv: 2005.04553

[30] Greenberger D M, Horne M A, Zeilinger A. Going beyond Bell’s theorem. In: Kafatos M, ed. Bell’s Theorem, Quantum Theory and Conceptions of the Universe. Dordrecht: Springer, 1989, 69−72

[31] Rocchetto A, Aaronson S, Severini S, Carvacho G, Poderini D, Agresti I, Bentivegna M, Sciarrino F. Experimental learning of quantum states. Science Advances, 2019, 5( 3): eaau1946

[32] Möttönen M, Vartiainen J J, Bergholm V, Salomaa M M. Transformation of quantum states using uniformly controlled rotations. Quantum Information & Computation, 2005, 5( 6): 467–473

[33] Plesch M, Brukner Č. Quantum-state preparation with universal gate decompositions. Physical Review A, 2011, 83( 3): 032302

[34] Chen S, Yu W, Zeng P, Flammia S T. Robust shadow estimation. PRX Quantum, 2021, 2( 3): 030348

[35] Metropolis N, Ulam S. The Monte Carlo method. Journal of the American Statistical Association, 1949, 44( 247): 335–341

[36] Wilde M M. Quantum Information Theory. 2nd ed. Cambridge: Cambridge University Press, 2017

[37] Preskill J. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79

[38] Chen S, Cotler J, Huang H Y, Li J. The complexity of NISQ. Nature Communications, 2023, 14( 1): 6001

Acknowledgements

J. Zhang, Z. Wan were supported by the National Natural Science Foundation of China (Grant Nos. 62325210, and 62272441), and the Strategic Priority Research Program of Chinese Academy of Sciences (No. XDB28000000). T. Li was supported by the National Natural Science Foundation of China (Grant Nos. 62372006, 92365117), and the Fundamental Research Funds for the Central Universities, Peking University. J. Jiang completed his work during an exchange study at the Institute of Computing Technology, Chinese Academy of Sciences.

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2025 Higher Education Press