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

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

RIGHTS & PERMISSIONS

Higher Education Press