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

Henry Yuen

Columbia University

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


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).

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

► 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:/​/​​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:/​/​​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:/​/​​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:/​/​​10.1145/​2897518.2897544.

[5] Reinhard F Werner. Optimal cloning of pure states. Physical Review A, 58 (3): 1827, 1998. https:/​/​​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:/​/​​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] 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).

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

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

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

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

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

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

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

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

[12] Ming-Chien Hsu, En-Jui Kuo, Wei-Hsuan Yu, Jian-Feng Cai, and Min-Hsiu Hsieh, "Quantum state tomography via non-convex Riemannian gradient descent", arXiv:2210.04717, (2022).

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 09:57:10) and SAO/NASA ADS (last updated successfully 2024-05-21 09:57:10). The list may be incomplete as not all publishers provide suitable and complete citation data.