Quantum chi-squared tomography and mutual information testing

Steven T. Flammia; Ryan O'Donnell

doi:10.22331/q-2024-06-20-1381

Quantum chi-squared tomography and mutual information testing

Steven T. Flammia^1,2 and Ryan O'Donnell³

¹AWS Center for Quantum Computing
²IQIM, California Institute of Technology
³Computer Science Department, Carnegie Mellon University

Published:	2024-06-20, volume 8, page 1381
Eprint:	arXiv:2305.18519v2
Doi:	https://doi.org/10.22331/q-2024-06-20-1381
Citation:	Quantum 8, 1381 (2024).

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

Abstract

For quantum state tomography on rank-$r$ dimension-$d$ states, we show that $\widetilde{O}(r^{.5}d^{1.5}/\epsilon) \leq \widetilde{O}(d^2/\epsilon)$ copies suffice for accuracy $\epsilon$ with respect to (Bures) $\chi^2$-divergence, and $\widetilde{O}(rd/\epsilon)$ copies suffice for accuracy $\epsilon$ with respect to quantum relative entropy. The best previous bound was $\widetilde{O}(rd/\epsilon) \leq \widetilde{O}(d^2/\epsilon)$ with respect to infidelity; our results are an improvement since infidelity is bounded above by both the relative entropy and the $\chi^2$-divergence. For algorithms that are required to use single-copy measurements, we show that $\widetilde{O}(r^{1.5} d^{1.5}/\epsilon) \leq \widetilde{O}(d^3/\epsilon)$ copies suffice for $\chi^2$-divergence, and $\widetilde{O}(r^{2} d/\epsilon)$ suffice for relative entropy.
Using this tomography algorithm, we show that $\widetilde{O}(d^{2.5}/\epsilon)$ copies of a $d\times d$-dimensional bipartite state suffice to test if it has quantum mutual information $0$ or at least $\epsilon$. As a corollary, we also improve the best known sample complexity for the $classical$ version of mutual information testing to $\widetilde{O}(d/\epsilon)$.

Featured image: $\chi^2$ divergence

Popular summary

Learning an unknown quantum state, a task known as quantum tomography, is a fundamental primitive in quantum information science. Different tomography methods can be compared via the precision of their estimates when given comparable resources, such as the same number of copies of the unknown state. Precision, however, can take several meanings, as there is no unique way to quantify how different two quantum states are.

In this work, we give a new quantum algorithm for learning an unknown quantum state with respect to two rather demanding notions of precision: relative entropy and chi-squared divergence. We show that the resources required to obtain a given precision are comparable to what is required for less demanding precision notions.

We then give an application of our new algorithm by showing how it leads to a test of whether or not the conditional mutual information of a bipartite quantum state is zero or epsilon-far from zero using almost quadratically fewer measurements than what is achievable with less stringent notions of precision.

► BibTeX data

@article{Flammia2024quantumchisquared,
  doi = {10.22331/q-2024-06-20-1381},
  url = {https://doi.org/10.22331/q-2024-06-20-1381},
  title = {Quantum chi-squared tomography and mutual information testing},
  author = {Flammia, Steven T. and O'Donnell, Ryan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1381},
  month = jun,
  year = {2024}
}

► References

[1] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.

[2] Robert Alicki and Mark Fannes. Continuity of quantum conditional information. Journal of Physics A: Mathematical and General, 37 (5): L55, 2004. 10.1088/0305-4470/37/5/L01.
https://doi.org/10.1088/0305-4470/37/5/L01

[3] George Androulakis and Tiju John. Relative entropy via distribution of observables. Infinite Dimensional Analysis, Quantum Probability and Related Topics, volume 27, 2024. 10.1142/S0219025723500212.
https://doi.org/10.1142/S0219025723500212

[4] Koenraad Audenaert. A sharp continuity estimate for the von Neumann entropy. Journal of Physics A: Mathematical and Theoretical, 40 (28): 8127, 2007. 10.1088/1751-8113/40/28/S18.
https://doi.org/10.1088/1751-8113/40/28/S18

[5] Koenraad Audenaert and Jens Eisert. Continuity bounds on the quantum relative entropy–II. Journal of Mathematical Physics, 52 (11): 112201, 2011. 10.1063/1.3657929.
https://doi.org/10.1063/1.3657929

[6] Koenraad Audenaert, Michael Nussbaum, Arleta Szkoła, and Frank Verstraete. Asymptotic error rates in quantum hypothesis testing. Communications in Mathematical Physics, 279 (1): 251–283, feb 2008. 10.1007/s00220-008-0417-5.
https://doi.org/10.1007/s00220-008-0417-5

[7] Costin Bădescu, Ryan O'Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, June 2019. 10.1145/3313276.3316344.
https://doi.org/10.1145/3313276.3316344

[8] Emilio Bagan, Manuel Ballester, Richard Gill, Alex Monràs, and Ramon Muñoz-Tapia. Optimal full estimation of qubit mixed states. Physical Review A, 73 (3): 032301, 2006. 10.1103/physreva.73.032301.
https://doi.org/10.1103/physreva.73.032301

[9] Mario Berta, Omar Fawzi, and Marco Tomamichel. On variational expressions for quantum relative entropies. Letters in Mathematical Physics, 107 (12): 2239–2265, 2017. ISSN 0377-9017. 10.1007/s11005-017-0990-7. URL https://doi.org/10.1007/s11005-017-0990-7.
https://doi.org/10.1007/s11005-017-0990-7

[10] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and N. V. Vinodchandran. Near-optimal learning of tree-structured distributions by Chow–Liu. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ACM, June 2021. 10.1145/3406325.3451066.
https://doi.org/10.1145/3406325.3451066

[11] Robin Blume-Kohout and Patrick Hayden. Accurate quantum state estimation via "keeping the experimentalist honest", 2006.

[12] Samuel Braunstein and Carlton Caves. Statistical distance and the geometry of quantum states. Physical Review Letters, 72 (22): 3439–3443, 1994. 10.1103/PhysRevLett.72.3439.
https://doi.org/10.1103/PhysRevLett.72.3439

[13] Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. When does adaptivity help for quantum state learning? Technical report, arXiv:2206.00220, 2022.
arXiv:2206.00220

[14] Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. When does adaptivity help for quantum state learning?, 2023. New version of [CHLLS22] in preparation.

[15] Constantinos Daskalakis, Gautam Kamath, and John Wright. Which Distribution Distances are Sublinearly Testable?, pages 2747–2764. Society for Industrial and Applied Mathematics, 2018. 10.1137/1.9781611975031.175.
https://doi.org/10.1137/1.9781611975031.175

[16] Nilanjana Datta. Min- and max-relative entropies and a new entanglement monotone. IEEE Transactions on Information Theory, 55 (6): 2816–2826, June 2009. 10.1109/tit.2009.2018325.
https://doi.org/10.1109/tit.2009.2018325

[17] Christopher Ferrie and Robin Blume-Kohout. Minimax quantum tomography: the ultimate bounds on accuracy. Physical Review Letters, 116 (9): 090407, 2016. 10.1103/PhysRevLett.116.090407.
https://doi.org/10.1103/PhysRevLett.116.090407

[18] Steven T. Flammia, Jeongwan Haah, Michael Kastoryano, and Isaac Kim. Limits on the storage of quantum information in a volume of space. Quantum, 1: 4, April 2017. 10.22331/q-2017-04-25-4.
https://doi.org/10.22331/q-2017-04-25-4

[19] Christopher Fuchs and Carlton Caves. Mathematical techniques for quantum communication theory. Open Systems & Information Dynamics, 3 (3): 345–356, October 1995. 10.1007/bf02228997.
https://doi.org/10.1007/bf02228997

[20] Alison Gibbs and Francis Su. On choosing and bounding probability metrics. International Statistical Review, 70 (3): 419, December 2002. 10.2307/1403865.
https://doi.org/10.2307/1403865

[21] Jeongwan Haah, Aram Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, pages 1–1, 2017. 10.1109/tit.2017.2719044.
https://doi.org/10.1109/tit.2017.2719044

[22] Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. Technical Report 2302.14066, arXiv, 2023.

[23] Aram Harrow and Ashley Montanaro. Testing product states, quantum Merlin–Arthur games and tensor optimization. Journal of the ACM, 60 (1): 1–43, 2013. 10.1145/2432622.2432625. URL https://doi.org/10.1145/2432622.2432625.
https://doi.org/10.1145/2432622.2432625

[24] Masahito Hayashi. Asymptotic estimation theory for a finite-dimensional pure state model. Journal of Physics A: Mathematical and General, 31 (20): 4633–4655, may 1998. 10.1088/0305-4470/31/20/006.
https://doi.org/10.1088/0305-4470/31/20/006

[25] Carl Helstrom. Quantum detection and estimation theory, volume 123 of Mathematics in science and engineering. Academic Press, New York, 1 edition, 1976. 10.1016/S0076-5392(08)60515-2.
https://doi.org/10.1016/S0076-5392(08)60515-2

[26] Fumio Hiai and Milán Mosonyi. Different quantum $f$-divergences and the reversibility of quantum operations. Rev. Math. Phys., 29 (7): 1750023, 80, 2017. ISSN 0129-055X. 10.1142/S0129055X17500234. URL https://doi.org/10.1142/S0129055X17500234.
https://doi.org/10.1142/S0129055X17500234

[27] Richard Kueng, Holger Rauhut, and Ulrich Terstiege. Low rank matrix recovery from rank one measurements. Applied and Computational Harmonic Analysis, 42 (1): 88–116, 2017. ISSN 1063-5203. 10.1016/j.acha.2015.07.007. URL https://www.sciencedirect.com/science/article/pii/S1063520315001037.
https://doi.org/10.1016/j.acha.2015.07.007
https://www.sciencedirect.com/science/article/pii/S1063520315001037

[28] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel. On quantum Rényi entropies: A new generalization and some properties. Journal of Mathematical Physics, 54 (12): 122203, December 2013. 10.1063/1.4838856. URL https://doi.org/10.1063/1.4838856.
https://doi.org/10.1063/1.4838856

[29] Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th Anniversary edition, 2010.

[30] Michael Nussbaum and Arleta Szkoła. The Chernoff lower bound for symmetric quantum hypothesis testing. Annals of Statistics, 37 (2), apr 2009. 10.1214/08-aos593.
https://doi.org/10.1214/08-aos593

[31] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1145/2897518.2897544.
https://doi.org/10.1145/2897518.2897544

[32] Ryan O'Donnell and John Wright. Efficient quantum tomography ii. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 962–974, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345286. 10.1145/3055399.3055454.
https://doi.org/10.1145/3055399.3055454

[33] Luciana Pereira, Leonardo Zambrano, Jean Cortés-Vega, Sebastián Niklitschek, and Aldo Delgado. Adaptive quantum tomography in high dimensions. Physical Review A, 98 (1): 012339, July 2018. 10.1103/physreva.98.012339.
https://doi.org/10.1103/physreva.98.012339

[34] Luciano Pereira, Juan García-Ripoll, and Tomá Ramos. Parallel tomography of quantum non-demolition measurements in multi-qubit devices. npj Quantum Information, 9 (1): 22, 2023. 10.1038/s41534-023-00688-7.
https://doi.org/10.1038/s41534-023-00688-7

[35] Yuval Peres. Finite-sample deviation bound of empirical distribution from true distribution. MathOverflow, 2019. https://mathoverflow.net/q/331405.
https://mathoverflow.net/q/331405

[36] Dénes Petz. Quasi-entropies for finite quantum systems. Reports on Mathematical Physics, 23 (1): 57–65, February 1986. 10.1016/0034-4877(86)90067-4.
https://doi.org/10.1016/0034-4877(86)90067-4

[37] Dénes Petz. Monotone metrics on matrix spaces. Linear Algebra and its Applications, 244: 81–96, September 1996. 10.1016/0024-3795(94)00211-8. URL https://doi.org/10.1016/0024-3795(94)00211-8.
https://doi.org/10.1016/0024-3795(94)00211-8

[38] Jaroslav Řeháček, Berthold-Georg Englert, and Dagomir Kaszlikowski. Minimal qubit tomography. Physical Review A, 70 (5): 052321, November 2004. 10.1103/physreva.70.052321.
https://doi.org/10.1103/physreva.70.052321

[39] Igal Sason and Sergio Verdú. $f$-divergence inequalities. IEEE Transactions on Information Theory, 62 (11): 5973–6006, 2016. 10.1109/TIT.2016.2603151.
https://doi.org/10.1109/TIT.2016.2603151

[40] M. E. Shirokov. Tight uniform continuity bounds for the quantum conditional mutual information, for the Holevo quantity, and for capacities of quantum channels. Journal of Mathematical Physics, 58 (10): 102202, October 2017. 10.1063/1.4987135.
https://doi.org/10.1063/1.4987135

[41] Ewin Tang, 2022. https://twitter.com/ewintang/status/1569426816821248001?cxt=HHwWgoDS2f3X3McrAAAA.
https://twitter.com/ewintang/status/1569426816821248001?cxt=HHwWgoDS2f3X3McrAAAA

[42] Kristan Temme and Frank Verstraete. Quantum chi-squared and goodness of fit testing. Journal of Mathematical Physics, 56 (1): 012202, January 2015. 10.1063/1.4905843.
https://doi.org/10.1063/1.4905843

[43] Kristan Temme, Michael Kastoryano, Mary Beth Ruskai, Michael Wolf, and Frank Verstraete. The $\chi^2$-divergence and mixing times of quantum Markov processes. Journal of Mathematical Physics, 51 (12): 122201, 2010. 10.1063/1.3511335.
https://doi.org/10.1063/1.3511335

[44] Marco Tomamichel. Quantum Information Processing with Finite Resources. Springer International Publishing, 2016. 10.1007/978-3-319-21891-5.
https://doi.org/10.1007/978-3-319-21891-5

[45] Marco Tomamichel and Jan Seyfried. Personal communication, 2024.

[46] Hisaharu Umegaki. Conditional expectation in an operator algebra. IV. Entropy and information. Kodai Mathematical Journal, 14 (2), January 1962. 10.2996/kmj/1138844604.
https://doi.org/10.2996/kmj/1138844604

[47] Wikipedia. Graph factorization (complete graphs), 2023. https://en.wikipedia.org/wiki/Graph_factorization#Complete_graphs.
https://en.wikipedia.org/wiki/Graph_factorization#Complete_graphs

[48] Mark Wilde, Andreas Winter, and Dong Yang. Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Rényi relative entropy. Communications in Mathematical Physics, 331 (2): 593–622, jul 2014. 10.1007/s00220-014-2122-x.
https://doi.org/10.1007/s00220-014-2122-x

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

[50] Yihong Wu. Lecture notes: Information-theoretic methods for high-dimensional statistics. www.stat.yale.edu/ yw562/teaching/it-stats.pdf, 2020.
http://www.stat.yale.edu/~yw562/teaching/it-stats.pdf

[51] Henry Yuen. An improved sample complexity lower bound for (fidelity) quantum state tomography. Quantum, 7: 890, 2023. 10.22331/q-2023-01-03-890.
https://doi.org/10.22331/q-2023-01-03-890

Cited by

[1] Logeswaran Selvaraj, Anusha Gururajan, Bhuvanesh Kumar Manickam, and Ananda Kumar Subbaiyan, "Machine learning-based analysis of factors influencing bus station traffic management in India", Canadian Journal of Civil Engineering 53, 1 (2026).

[2] Benjamin Lovitz and Angus Lowe, "Nearly Tight Bounds for Testing Tree Tensor Network States", IEEE Transactions on Information Theory 72 5, 3074 (2026).

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

[4] Adam Bouland, Tudor Giurgică-Tiron, and John Wright, Proceedings of the 57th Annual ACM Symposium on Theory of Computing 463 (2025) ISBN:9798400715105.

[5] Angus Lowe and Ashwin Nayak, "Lower Bounds for Learning Quantum States with Single-Copy Measurements", ACM Transactions on Computation Theory 17 1, 1 (2025).

[6] Omar Fawzi, Richard Kueng, Damian Markham, and Aadil Oufkir, "Learning properties of quantum states without the IID assumption", Nature Communications 15 1, 9677 (2024).

[7] Li Gao and Nengkun Yu, "Optimal Tomography of Quantum Markov Chains via Continuity of Petz Recovery States", IEEE Transactions on Information Theory 71 9, 7016 (2025).

[8] Mohammad Aamir Sohail, Mohsen Heidari, and S. Sandeep Pradhan, "Quantum natural stochastic pairwise coordinate descent", npj Quantum Information 11 1, 109 (2025).

[9] Yupan Liu, "Quantum state testing beyond the polarizing regime and quantum triangular discrimination", computational complexity 34 2, 11 (2025).

[10] Masahito Hayashi, "Measuring quantum relative entropy with finite-size effect", Quantum 9, 1725 (2025).

[11] Adam Bouland, Tudor Giurgica-Tiron, and John Wright, "The state hidden subgroup problem and an efficient algorithm for locating unentanglement", arXiv:2410.12706, (2024).

[12] Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, and Ewin Tang, "Learning the closest product state", arXiv:2411.04283, (2024).

[13] Yupan Liu, "Quantum state testing beyond the polarizing regime and quantum triangular discrimination", arXiv:2303.01952, (2023).

[14] Julian Arnold, Flemming Holtorf, Frank Schäfer, and Niels Lörch, "Phase Transitions in the Output Distribution of Large Language Models", arXiv:2405.17088, (2024).

[15] Carlos de Gois and Matthias Kleinmann, "User-friendly confidence regions for quantum state tomography", Physical Review A 109 6, 062417 (2024).

[16] Yuhan Liu and Jayadev Acharya, "The role of shared randomness in quantum state certification with unentangled measurements", arXiv:2401.09650, (2024).

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

[18] Ruo Cheng Huang, "A Demon that remembers: An agential approach towards quantum thermodynamics of temporal correlations", arXiv:2604.04462, (2026).

[19] Benjamin Lovitz and Angus Lowe, "Nearly tight bounds for testing tree tensor network states", arXiv:2410.21417, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 15:17:56) and SAO/NASA ADS (last updated successfully 2026-08-10 15:18:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.