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

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

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

[4] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", arXiv:2305.20069, (2023).

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 14:33:54) and SAO/NASA ADS (last updated successfully 2023-11-29 14:33:55). The list may be incomplete as not all publishers provide suitable and complete citation data.