An Improved Sample Complexity Lower Bound for (Fidelity) Quantum State Tomography

Henry Yuen

doi:10.22331/q-2023-01-03-890

An Improved Sample Complexity Lower Bound for (Fidelity) Quantum State Tomography

Henry Yuen

Columbia University

Published:	2023-01-03, volume 7, page 890
Eprint:	arXiv:2206.11185v2
Doi:	https://doi.org/10.22331/q-2023-01-03-890
Citation:	Quantum 7, 890 (2023).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We show that $\Omega(rd/\epsilon)$ copies of an unknown rank-$r$, dimension-$d$ quantum mixed state are necessary in order to learn a classical description with $1 – \epsilon$ fidelity. This improves upon the tomography lower bounds obtained by Haah, et al. and Wright (when closeness is measured with respect to the fidelity function).

Featured image: Quantum state tomography.

Popular summary

This paper presents a sharper lower bound on the number of copies of a quantum state needed to learn a classical description of it.

► BibTeX data

@article{Yuen2023improvedsample,
  doi = {10.22331/q-2023-01-03-890},
  url = {https://doi.org/10.22331/q-2023-01-03-890},
  title = {An {I}mproved {S}ample {C}omplexity {L}ower {B}ound for ({F}idelity) {Q}uantum {S}tate {T}omography},
  author = {Yuen, Henry},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {890},
  month = jan,
  year = {2023}
}

► References

[1] Dagmar Bruß and Chiara Macchiavello. Optimal state estimation for $d$-dimensional quantum systems. Physics Letters A, 253 (5-6): 249–251, 1999. https://doi.org/10.1016/S0375-9601(99)00099-7.
https://doi.org/10.1016/S0375-9601(99)00099-7

[2] Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63 (9): 5628–5641, 2017. https://doi.org/10.1145/2897518.2897585.
https://doi.org/10.1145/2897518.2897585

[3] Michael Keyl and Reinhard F Werner. Optimal cloning of pure states, testing single clones. Journal of Mathematical Physics, 40 (7): 3283–3299, 1999. https://doi.org/10.1063/1.532887.
https://doi.org/10.1063/1.532887

[4] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 899–912, 2016. https://doi.org/10.1145/2897518.2897544.
https://doi.org/10.1145/2897518.2897544

[5] Reinhard F Werner. Optimal cloning of pure states. Physical Review A, 58 (3): 1827, 1998. https://doi.org/10.1103/PhysRevA.58.1827.
https://doi.org/10.1103/PhysRevA.58.1827

[6] Andreas Winter. Coding theorem and strong converse for quantum channels. IEEE Transactions on Information Theory, 45 (7): 2481–2485, 1999. https://doi.org/10.1109/18.796385.
https://doi.org/10.1109/18.796385

[7] John Wright. How to learn a quantum state. PhD thesis, Carnegie Mellon University, 2016.

Cited by

[1] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", Nature Reviews Physics 6 1, 59 (2023).

[2] Xinbiao Wang, Yuxuan Du, Zhuozhuo Tu, Yong Luo, Xiao Yuan, and Dacheng Tao, "Transition role of entangled data in quantum machine learning", Nature Communications 15 1, 3716 (2024).

[3] Rafael Wagner, Filipa C R Peres, Emmanuel Zambrini Cruzeiro, and Ernesto F Galvão, "Unitary-invariant method for witnessing nonstabilizerness in quantum processors", Journal of Physics A: Mathematical and Theoretical 58 28, 285302 (2025).

[4] Yanglin Hu, Enrique Cervero-Martín, Elias Theil, Laura Mančinska, and Marco Tomamichel, "Sample-optimal and memory-efficient quantum state tomography", Physical Review A 113 5, 052446 (2026).

[5] Harshdeep Singh, Sonjoy Majumder, and Sabyashachi Mishra, "Hückel molecular orbital theory on a quantum computer: A scalable system-agnostic variational implementation with compact encoding", The Journal of Chemical Physics 160 19, 194106 (2024).

[6] Angelos Pelecanos, Jack Spilecki, and John Wright, Proceedings of the 58th Annual ACM Symposium on Theory of Computing 1266 (2026) ISBN:9798400725364.

[7] Subhadeep Mondal and Amit Kumar Dutta, "A modified least squares-based tomography with density matrix perturbation and linear entropy consideration along with performance analysis", New Journal of Physics 25 8, 083051 (2023).

[8] Sreejith Sreekumar and Mario Berta, 2024 IEEE International Symposium on Information Theory (ISIT) 333 (2024) ISBN:979-8-3503-8284-6.

[9] Ziv Goldfeld, Dhrumil Patel, Sreejith Sreekumar, and Mark M. Wilde, "Quantum neural estimation of entropies", Physical Review A 109 3, 032431 (2024).

[10] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro, "Learning Quantum States and Unitaries of Bounded Gate Complexity", PRX Quantum 5 4, 040306 (2024).

[11] Sreejith Sreekumar and Mario Berta, "Limit Distribution Theory for Quantum Divergences", IEEE Transactions on Information Theory 71 1, 459 (2025).

[12] Sreejith Sreekumar, Ziv Goldfeld, and Mark M. Wilde, "Performance Guarantees for Quantum Neural Estimation of Entropies", Quantum 10, 2113 (2026).

[13] Federico Girotti, Alfred Godley, and Mădălin Guţă, "Optimal estimation of pure states with displaced-null measurements", Journal of Physics A: Mathematical and Theoretical 57 24, 245304 (2024).

[14] Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, and Nengkun Yu, Proceedings of the 57th Annual ACM Symposium on Theory of Computing 718 (2025) ISBN:9798400715105.

[15] Refik Mansuroglu, Arsalan Adil, Michael J. Hartmann, Zoë Holmes, and Andrew T. Sornborger, "Quantum Tensor-Product Decomposition from Choi-State Tomography", PRX Quantum 5 3, 030306 (2024).

[16] Alexander Mandl, Johanna Barzen, Marvin Bechtold, and Frank Leymann, Communications in Computer and Information Science 2221, 107 (2025) ISBN:978-3-031-72577-7.

[17] Steven T. Flammia and Ryan O'Donnell, "Quantum chi-squared tomography and mutual information testing", Quantum 8, 1381 (2024).

[18] Rafael Wagner, Zohar Schwartzman-Nowik, Ismael L Paiva, Amit Te’eni, Antonio Ruiz-Molero, Rui Soares Barbosa, Eliahu Cohen, and Ernesto F Galvão, "Quantum circuits for measuring weak values, Kirkwood–Dirac quasiprobability distributions, and state spectra", Quantum Science and Technology 9 1, 015030 (2024).

[19] Haimeng Zhao, Giuseppe Carleo, and Filippo Vicentini, "Empirical Sample Complexity of Neural Network Mixed State Reconstruction", Quantum 8, 1358 (2024).

[20] Xiaozhou Feng, Zihan Cheng, and Matteo Ippoliti, "Hardness of Observing Strong-to-Weak Symmetry Breaking", Physical Review Letters 135 20, 200402 (2025).

[21] Yi Shen and Lin Chen, "Additivity of states uniquely determined by marginals", Physical Review A 108 6, 062418 (2023).

[22] Ming-Chien Hsu, En-Jui Kuo, Wei-Hsuan Yu, Jian-Feng Cai, and Min-Hsiu Hsieh, "Quantum State Tomography via Nonconvex Riemannian Gradient Descent", Physical Review Letters 132 24, 240804 (2024).

[23] Jiaqi Leng and Bin Shi, Communications in Computer and Information Science 2724, 170 (2026) ISBN:978-981-95-7828-3.

[24] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[25] Nic Ezzell, Elliott M. Ball, Aliza U. Siddiqui, Mark M. Wilde, Andrew T. Sornborger, Patrick J. Coles, and Zoë Holmes, "Quantum mixed state compiling", Quantum Science and Technology 8 3, 035001 (2023).

[26] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder, "Optimal algorithms for learning quantum phase states", arXiv:2208.07851, (2022).

[27] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini, "Quantum tomography using state-preparation unitaries", arXiv:2207.08800, (2022).

[28] Rafael Wagner, "Coherence and contextuality as quantum resources", arXiv:2511.16785, (2025).

[29] Nai-Hui Chia, Daniel Liang, and Fang Song, "Quantum State Learning Implies Circuit Lower Bounds", arXiv:2405.10242, (2024).

[30] 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).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-17 04:57:54) and SAO/NASA ADS (last updated successfully 2026-07-16 16:50:43). 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-07-17 04:57:54: 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.