Resource-efficient algorithm for estimating the trace of quantum state powers

Myeongjin Shin; Junseo Lee; Seungwoo Lee; Kabgyun Jeong

doi:10.22331/q-2025-08-27-1832

Resource-efficient algorithm for estimating the trace of quantum state powers

Myeongjin Shin^1,2, Junseo Lee^2,3, Seungwoo Lee^1,2, and Kabgyun Jeong^2,4,5

¹School of Computing, KAIST, Daejeon 34141, Korea
²Team QST, Seoul National University, Seoul 08826, Korea
³Quantum AI Team, Norma Inc., Seoul 04799, Korea
⁴Research Institute of Mathematics, Seoul National University, Seoul 08826, Korea
⁵School of Computational Sciences, Korea Institute for Advanced Study, Seoul 02455, Korea

Published:	2025-08-27, volume 9, page 1832
Editor:	Felix Huber
Eprint:	arXiv:2408.00314v3
Doi:	https://doi.org/10.22331/q-2025-08-27-1832
Citation:	Quantum 9, 1832 (2025).

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

Abstract

Estimating the trace of quantum state powers, $\text{Tr}(\rho^k)$, for $k$ identical quantum states is a fundamental task with numerous applications in quantum information processing, including nonlinear function estimation of quantum states and entanglement detection. On near-term quantum devices, reducing the required quantum circuit depth, the number of multi-qubit quantum operations, and the copies of the quantum state needed for such computations is crucial. In this work, inspired by the Newton-Girard method, we significantly improve upon existing results by introducing an algorithm that requires only $\mathcal{O}(\widetilde{r})$ qubits and $\mathcal{O}(\widetilde{r})$ multi-qubit gates, where $\widetilde{r} = \min\left\{\text{rank}(\rho), \left\lceil\ln\left({2k}/{\epsilon}\right)\right\rceil\right\}$. This approach is efficient, as it employs the $\tilde{r}$-entangled copy measurement instead of the conventional $k$-entangled copy measurement, while asymptotically preserving the known sample complexity upper bound. Furthermore, we prove that estimating $\{\text{Tr}(\rho^i)\}_{i=1}^{\tilde{r}}$ is sufficient to approximate $\text{Tr}(\rho^k)$ even for large integers $k \gt \widetilde{r}$. This leads to a rank-dependent complexity for solving the problem, providing an efficient algorithm for low-rank quantum states while also improving existing methods when the rank is unknown or when the state is not low-rank. Building upon these advantages, we extend our algorithm to the estimation of $\text{Tr}(M\rho^k)$ for arbitrary observables and $\text{Tr}(\rho^k \sigma^l)$ for multiple quantum states.

Featured image: Diagram of the complete process of the proposed algorithm. The red box represents the quantum processing step, where the values from $\mathrm{Tr}(\rho)$ to $\mathrm{Tr}(\rho^t)$ are obtained. The subsequent blue dashed lines indicate classical computations performed using a simple recurrence relation, without requiring quantum resources.

► BibTeX data

@article{Shin2025resourceefficient,
  doi = {10.22331/q-2025-08-27-1832},
  url = {https://doi.org/10.22331/q-2025-08-27-1832},
  title = {Resource-efficient algorithm for estimating the trace of quantum state powers},
  author = {Shin, Myeongjin and Lee, Junseo and Lee, Seungwoo and Jeong, Kabgyun},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1832},
  month = aug,
  year = {2025}
}

► References

[1] Sonika Johri, Damian S. Steiger, and Matthias Troyer. ``Entanglement spectroscopy on a quantum computer''. Physical Review B 96, 195136 (2017).
https://doi.org/10.1103/PhysRevB.96.195136

[2] A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, and P. Zoller. ``Rényi entropies from random quenches in atomic hubbard and spin models''. Physical Review Letters 120, 050406 (2018).
https://doi.org/10.1103/PhysRevLett.120.050406

[3] B. Vermersch, A. Elben, M. Dalmonte, J. I. Cirac, and P. Zoller. ``Unitary $n$-designs via random quenches in atomic hubbard and spin models: Application to the measurement of rényi entropies''. Physical Review A 97, 023604 (2018).
https://doi.org/10.1103/PhysRevA.97.023604

[4] Artur K. Ekert, Carolina Moura Alves, Daniel K. L. Oi, Michał Horodecki, Paweł Horodecki, and L. C. Kwek. ``Direct estimations of linear and nonlinear functionals of a quantum state''. Physical Review Letters 88, 217901 (2002).
https://doi.org/10.1103/PhysRevLett.88.217901

[5] Todd A. Brun. ``Measuring polynomial functions of states''. Quantum Information and Computation 4, 401 (2004).

[6] S. J. van Enk and C. W. J. Beenakker. ``Measuring $\mathrm{Tr}{{\rho}}^{n}$ on single copies of ${\rho}$ using random measurements''. Physical Review Letters 108, 110503 (2012).
https://doi.org/10.1103/PhysRevLett.108.110503

[7] You Zhou and Zhenhuan Liu. ``A hybrid framework for estimating nonlinear functions of quantum states''. npj Quantum Information 10, 62 (2024).
https://doi.org/10.1038/s41534-024-00846-5

[8] Fabio Antonio Bovino, Giuseppe Castagnoli, Artur Ekert, Paweł Horodecki, Carolina Moura Alves, and Alexander Vladimir Sergienko. ``Direct measurement of nonlinear properties of bipartite quantum states''. Physical Review Letters 95, 240407 (2005).
https://doi.org/10.1103/PhysRevLett.95.240407

[9] Justin Yirka and Yiğit Subaşı. ``Qubit-efficient entanglement spectroscopy using qubit resets''. Quantum 5, 535 (2021).
https://doi.org/10.22331/q-2021-09-02-535

[10] Youle Wang, Guangxi Li, and Xin Wang. ``Variational quantum gibbs state preparation with a truncated taylor series''. Physical Review Applied 16, 054035 (2021).
https://doi.org/10.1103/PhysRevApplied.16.054035

[11] Mirko Consiglio, Jacopo Settino, Andrea Giordano, Carlo Mastroianni, Francesco Plastina, Salvatore Lorenzo, Sabrina Maniscalco, John Goold, and Tony J. G. Apollaro. ``Variational gibbs state preparation on noisy intermediate-scale quantum devices''. Physical Review A 110, 012445 (2024).
https://doi.org/10.1103/PhysRevA.110.012445

[12] Barbara M. Terhal and David P. DiVincenzo. ``Problem of equilibration and the computation of correlation functions on a quantum computer''. Physical Review A 61, 022301 (2000).
https://doi.org/10.1103/PhysRevA.61.022301

[13] Arnau Riera, Christian Gogolin, and Jens Eisert. ``Thermalization in nature and on a quantum computer''. Physical Review Letters 108, 080402 (2012).
https://doi.org/10.1103/PhysRevLett.108.080402

[14] Jingxiang Wu and Timothy H. Hsieh. ``Variational thermal quantum simulation via thermofield double states''. Physical Review Letters 123, 220502 (2019).
https://doi.org/10.1103/PhysRevLett.123.220502

[15] Yiğit Subaşı, Lukasz Cincio, and Patrick J Coles. ``Entanglement spectroscopy with a depth-two quantum circuit''. Journal of Physics A: Mathematical and Theoretical 52, 044001 (2019).
https://doi.org/10.1088/1751-8121/aaf54d

[16] Yihui Quek, Eneet Kaur, and Mark M. Wilde. ``Multivariate trace estimation in constant quantum depth''. Quantum 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220

[17] Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nature Physics 16, 1050–1057 (2020).
https://doi.org/10.1038/s41567-020-0932-7

[18] Aniket Rath, Cyril Branciard, Anna Minguzzi, and Benoı̂t Vermersch. ``Quantum fisher information from randomized measurements''. Physical Review Letters 127, 260501 (2021).
https://doi.org/10.1103/PhysRevLett.127.260501

[19] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. ``Quantum fingerprinting''. Physical Review Letters 87, 167902 (2001).
https://doi.org/10.1103/PhysRevLett.87.167902

[20] Daniel Gottesman and Isaac Chuang. ``Quantum digital signatures'' (2001). arXiv:quant-ph/0105032.
arXiv:quant-ph/0105032

[21] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia, and V. Giovannetti. ``Beyond the swap test: Optimal estimation of quantum state overlap''. Physical Review Letters 124, 060503 (2020).
https://doi.org/10.1103/PhysRevLett.124.060503

[22] Steph Foulds, Viv Kendon, and Tim Spiller. ``The controlled swap test for determining quantum entanglement''. Quantum Science and Technology 6, 035002 (2021).
https://doi.org/10.1088/2058-9565/abe458

[23] Xavier Gitiaux, Ian Morris, Maria Emelianenko, and Mingzhen Tian. ``Swap test for an arbitrary number of quantum states''. Quantum Information Processing 21, 344 (2022).
https://doi.org/10.1007/s11128-022-03643-1

[24] Michał Oszmaniec, Daniel J. Brod, and Ernesto F. Galvão. ``Measuring relational information between quantum states, and applications''. New Journal of Physics 26, 013053 (2024).
https://doi.org/10.1088/1367-2630/ad1a27

[25] Tuan-Yow Chien and Shayne Waldron. ``A characterization of projective unitary equivalence of finite frames and applications''. SIAM Journal on Discrete Mathematics 30, 976–994 (2016).
https://doi.org/10.1137/15M1042140

[26] V. Bargmann. ``Note on wigner's theorem on symmetry operations''. Journal of Mathematical Physics 5, 862–868 (1964).
https://doi.org/10.1063/1.1704188

[27] P. W. Shor. ``Fault-tolerant quantum computation''. In Proceedings of 37th Conference on Foundations of Computer Science. Pages 56–65. (1996).
https://doi.org/10.1109/SFCS.1996.548464

[28] Angelos Pelecanos, Xinyu Tan, Ewin Tang, and John Wright. ``Beating full state tomography for unentangled spectrum estimation'' (2025). url: https://arxiv.org/abs/2504.02785.
arXiv:2504.02785

[29] Zachary P. Bradshaw, Margarite L. LaBorde, and Mark M. Wilde. ``Cycle index polynomials and generalized quantum separability tests''. Proceedings of the Royal Society A 479, 20220733 (2023).
https://doi.org/10.1098/rspa.2022.0733

[30] Antoine Neven, Jose Carrasco, Vittorio Vitale, Christian Kokail, Andreas Elben, Marcello Dalmonte, Pasquale Calabrese, Peter Zoller, Benoı̂t Vermersch, Richard Kueng, et al. ``Symmetry-resolved entanglement detection using partial transpose moments''. npj Quantum Information 7, 152 (2021).
https://doi.org/10.1038/s41534-021-00487-y

[31] 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, 015030 (2024).
https://doi.org/10.1088/2058-9565/ad124c

[32] Yupan Liu and Qisheng Wang. ``On estimating the trace of quantum state powers''. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 947–993. SIAM (2025).
https://doi.org/10.1137/1.9781611978322.28

[33] H. Francis Song, Stephan Rachel, Christian Flindt, Israel Klich, Nicolas Laflorencie, and Karyn Le Hur. ``Bipartite fluctuations as a probe of many-body entanglement''. Physical Review B 85, 035409 (2012).
https://doi.org/10.1103/PhysRevB.85.035409

[34] Armen Bagdasaryan, Serkan Araci, Mehmet Açikgöz, and H. M. Srivastava. ``Analogues of newton–girard power-sum formulas for entire and meromorphic functions with applications to the riemann zeta function''. Journal of Number Theory 147, 92–102 (2015).
https://doi.org/10.1016/j.jnt.2014.07.006

[35] José Luis Cereceda. ``Sums of powers of integers and stirling numbers''. Resonance 27, 769–784 (2022).
https://doi.org/10.1007/s12045-022-1371-9

[36] Ronald G Mosier. ``Root neighborhoods of a polynomial''. Mathematics of Computation 47, 265–273 (1986).
https://doi.org/10.1090/S0025-5718-1986-0842134-4

[37] Antonio D. Córcoles, Abhinav Kandala, Ali Javadi-Abhari, Douglas T. McClure, Andrew W. Cross, Kristan Temme, Paul D. Nation, Matthias Steffen, and Jay M. Gambetta. ``Challenges and opportunities of near-term quantum computing systems''. Proceedings of the IEEE 108, 1338–1352 (2019).
https://doi.org/10.1109/JPROC.2019.2954005

[38] Konstantinos Georgopoulos, Clive Emary, and Paolo Zuliani. ``Modeling and simulating the noisy behavior of near-term quantum computers''. Physical Review A 104, 062432 (2021).
https://doi.org/10.1103/PhysRevA.104.062432

[39] Jin-Min Liang, Qiao-Qiao Lv, Zhi-Xi Wang, and Shao-Ming Fei. ``Unified multivariate trace estimation and quantum error mitigation''. Physical Review A 107, 012606 (2023).
https://doi.org/10.1103/PhysRevA.107.012606

[40] William J. Huggins, Sam McArdle, Thomas E. O'Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean. ``Virtual distillation for quantum error mitigation''. Physical Review X 11, 041036 (2021).
https://doi.org/10.1103/PhysRevX.11.041036

[41] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014).
https://doi.org/10.1038/nphys3029

[42] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. ``Hamiltonian simulation with optimal sample complexity''. npj Quantum Information 3, 13 (2017).
https://doi.org/10.1038/s41534-017-0013-7

[43] Andreas Elben, Richard Kueng, Hsin-Yuan Huang, Rick van Bijnen, Christian Kokail, Marcello Dalmonte, Pasquale Calabrese, Barbara Kraus, John Preskill, Peter Zoller, et al. ``Mixed-state entanglement from local randomized measurements''. Physical Review Letters 125, 200501 (2020).
https://doi.org/10.1103/PhysRevLett.125.200501

[44] Zhenhuan Liu, Weiyuan Gong, Zhenyu Du, and Zhenyu Cai. ``Exponential separations between quantum learning with and without purification'' (2024). arXiv:2410.17718.
arXiv:2410.17718

[45] Sitan Chen, Weiyuan Gong, and Qi Ye. ``Optimal tradeoffs for estimating pauli observables''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1086–1105. (2024).
https://doi.org/10.1109/FOCS61266.2024.00072

Cited by

[1] Kyrylo Simonov, Rafael Wagner, and Ernesto F. Galvão, "Estimation of multivariate traces of states given partial classical information", Physical Review A 112 6, 062435 (2025).

[2] J Knörzer, X Liu, B F Schiffer, and J Tura, "Distributed quantum information processing: a review of recent progress", Reports on Progress in Physics 89 7, 074401 (2026).

[3] Yupan Liu and Qisheng Wang, "On Estimating the Trace of Quantum State Powers", IEEE Transactions on Information Theory 72 8, 5830 (2026).

[4] Pedro C. Azado, Rafael Wagner, Rui S. Barbosa, and Ernesto F. Galvão, "Measuring unitary invariants with the quantum switch", arXiv:2508.02345, (2025).

[5] Qi Ye, Zhenhuan Liu, and Dong-Ling Deng, "Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States", arXiv:2509.24000, (2025).

[6] Kean Chen, Qisheng Wang, Zhan Yu, and Zhicheng Zhang, "Simultaneous Estimation of Nonlinear Functionals of a Quantum State", arXiv:2505.16715, (2025).

[7] Yupan Liu and Qisheng Wang, "On estimating the trace of quantum state powers", arXiv:2410.13559, (2024).

[8] Qisheng Wang, "Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation", arXiv:2509.03496, (2025).

[9] Rui-Qi Zhang, Xiao-Qi Liu, Jing Wang, Ming Li, Shu-Qian Shen, and Shao-Ming Fei, "Explicit Formulas for Estimating Trace of Reduced Density Matrix Powers via Single-Circuit Measurement Probabilities", arXiv:2507.17117, (2025).

[10] Kean Chen, Yupan Liu, and Qisheng Wang, "Trace Estimation of Quantum State Powers: Sample Complexity and Computational Hardness", arXiv:2505.09563, (2025).

[11] Hongshun Yao, Yingjian Liu, Tengxiang Lin, and Xin Wang, "Sample-Efficient Estimation of Nonlinear Quantum State Functions", arXiv:2412.01696, (2024).

[12] Xiao Shi, Jiyu Jiang, Xian Wu, Jingu Xie, Hongshun Yao, and Xin Wang, "Near-Optimal Simultaneous Estimation of Quantum State Moments", arXiv:2509.24842, (2025).

[13] Jinge Bao, Minbo Gao, and Qisheng Wang, "On Estimating the Quantum Tsallis Relative Entropy", arXiv:2510.00752, (2025).

[14] Xiaoyu Liu, Jordi Tura, and Albert Rico, "Measuring multipartite entanglement efficiently by testing symmetries", arXiv:2511.07537, (2025).

[15] Xiaoyu Liu, Johannes Knörzer, Zherui Jerry Wang, and Jordi Tura, "Generalized concentratable entanglement via parallelized permutation tests", Physical Review Research 7 3, L032022 (2025).

[16] Yupan Liu, "Computational hardness of estimating quantum entropies via binary entropy bounds", arXiv:2601.03734, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 12:26:37) and SAO/NASA ADS (last updated successfully 2026-08-09 12:26:38). 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.