{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T18:19:56Z","timestamp":1765995596418,"version":"3.44.0"},"reference-count":45,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T00:00:00Z","timestamp":1756252800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["RS-2023-00211817"],"award-info":[{"award-number":["RS-2023-00211817"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["RS-2024-00404854"],"award-info":[{"award-number":["RS-2024-00404854"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["RS-2025-00515537"],"award-info":[{"award-number":["RS-2025-00515537"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Information & Communications Technology Promotion","award":["RS-2025-02304540"],"award-info":[{"award-number":["RS-2025-02304540"]}]},{"name":"Information & Communications Technology Promotion","award":["2019-II190003"],"award-info":[{"award-number":["2019-II190003"]}]},{"DOI":"10.13039\/501100008783","name":"National Research Council of Science & Technology","doi-asserted-by":"crossref","award":["GTL25011-401"],"award-info":[{"award-number":["GTL25011-401"]}],"id":[{"id":"10.13039\/501100008783","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003708","name":"Korea Institute of Science and Technology Information","doi-asserted-by":"crossref","award":["KISTI: P25026"],"award-info":[{"award-number":["KISTI: P25026"]}],"id":[{"id":"10.13039\/501100003708","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Estimating the trace of quantum state powers, Tr<\/mml:mtext>(<\/mml:mo>&#x03C1;<\/mml:mi>k<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math>, for k<\/mml:mi><\/mml:math> 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 O<\/mml:mi><\/mml:mrow>(<\/mml:mo>r<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>)<\/mml:mo><\/mml:math> qubits and O<\/mml:mi><\/mml:mrow>(<\/mml:mo>r<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>)<\/mml:mo><\/mml:math> multi-qubit gates, where r<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>=<\/mml:mo>min<\/mml:mo>{<\/mml:mo>rank<\/mml:mtext>(<\/mml:mo>&#x03C1;<\/mml:mi>)<\/mml:mo>,<\/mml:mo>&#x2308;<\/mml:mo>ln<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>2<\/mml:mn>k<\/mml:mi><\/mml:mrow>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:mrow><\/mml:mrow>)<\/mml:mo><\/mml:mrow><\/mml:mrow>&#x2309;<\/mml:mo><\/mml:mrow><\/mml:mrow>}<\/mml:mo><\/mml:mrow><\/mml:math>. This approach is efficient, as it employs the r<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math>-entangled copy measurement instead of the conventional k<\/mml:mi><\/mml:math>-entangled copy measurement, while asymptotically preserving the known sample complexity upper bound. Furthermore, we prove that estimating {<\/mml:mo>Tr<\/mml:mtext>(<\/mml:mo>&#x03C1;<\/mml:mi>i<\/mml:mi><\/mml:msup>)<\/mml:mo>}<\/mml:mo>i<\/mml:mi>=<\/mml:mo>1<\/mml:mn><\/mml:mrow>r<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:mrow><\/mml:msubsup><\/mml:math> is sufficient to approximate Tr<\/mml:mtext>(<\/mml:mo>&#x03C1;<\/mml:mi>k<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math> even for large integers k<\/mml:mi>&#x003E;<\/mml:mo>r<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math>. 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 Tr<\/mml:mtext>(<\/mml:mo>M<\/mml:mi>&#x03C1;<\/mml:mi>k<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math> for arbitrary observables and Tr<\/mml:mtext>(<\/mml:mo>&#x03C1;<\/mml:mi>k<\/mml:mi><\/mml:msup>&#x03C3;<\/mml:mi>l<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math> for multiple quantum states.<\/jats:p>","DOI":"10.22331\/q-2025-08-27-1832","type":"journal-article","created":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T10:57:11Z","timestamp":1756292231000},"page":"1832","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Resource-efficient algorithm for estimating the trace of quantum state powers"],"prefix":"10.22331","volume":"9","author":[{"given":"Myeongjin","family":"Shin","sequence":"first","affiliation":[{"name":"School of Computing, KAIST, Daejeon 34141, Korea"},{"name":"Team QST, Seoul National University, Seoul 08826, Korea"}]},{"given":"Junseo","family":"Lee","sequence":"additional","affiliation":[{"name":"Team QST, Seoul National University, Seoul 08826, Korea"},{"name":"Quantum AI Team, Norma Inc., Seoul 04799, Korea"}]},{"given":"Seungwoo","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Computing, KAIST, Daejeon 34141, Korea"},{"name":"Team QST, Seoul National University, Seoul 08826, Korea"}]},{"given":"Kabgyun","family":"Jeong","sequence":"additional","affiliation":[{"name":"Team QST, Seoul National University, Seoul 08826, Korea"},{"name":"Research Institute of Mathematics, Seoul National University, Seoul 08826, Korea"},{"name":"School of Computational Sciences, Korea Institute for Advanced Study, Seoul 02455, Korea"}]}],"member":"9598","published-online":{"date-parts":[[2025,8,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Sonika Johri, Damian S. Steiger, and Matthias Troyer. ``Entanglement spectroscopy on a quantum computer''. Physical Review B 96, 195136 (2017).","DOI":"10.1103\/PhysRevB.96.195136"},{"key":"1","doi-asserted-by":"publisher","unstructured":"A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, and P. Zoller. ``R\u00e9nyi entropies from random quenches in atomic hubbard and spin models''. Physical Review Letters 120, 050406 (2018).","DOI":"10.1103\/PhysRevLett.120.050406"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u00e9nyi entropies''. Physical Review A 97, 023604 (2018).","DOI":"10.1103\/PhysRevA.97.023604"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Artur K. Ekert, Carolina Moura Alves, Daniel K. L. Oi, Micha\u0142 Horodecki, Pawe\u0142 Horodecki, and L. C. Kwek. ``Direct estimations of linear and nonlinear functionals of a quantum state''. Physical Review Letters 88, 217901 (2002).","DOI":"10.1103\/PhysRevLett.88.217901"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Todd A. Brun. ``Measuring polynomial functions of states''. Quantum Information and Computation 4, 401 (2004).","DOI":"10.26421\/QIC4.5-6"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.108.110503"},{"key":"6","doi-asserted-by":"publisher","unstructured":"You Zhou and Zhenhuan Liu. ``A hybrid framework for estimating nonlinear functions of quantum states''. npj Quantum Information 10, 62 (2024).","DOI":"10.1038\/s41534-024-00846-5"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Fabio Antonio Bovino, Giuseppe Castagnoli, Artur Ekert, Pawe\u0142 Horodecki, Carolina Moura Alves, and Alexander Vladimir Sergienko. ``Direct measurement of nonlinear properties of bipartite quantum states''. Physical Review Letters 95, 240407 (2005).","DOI":"10.1103\/PhysRevLett.95.240407"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Justin Yirka and Yi\u011fit Suba\u015f\u0131. ``Qubit-efficient entanglement spectroscopy using qubit resets''. Quantum 5, 535 (2021).","DOI":"10.22331\/q-2021-09-02-535"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Youle Wang, Guangxi Li, and Xin Wang. ``Variational quantum gibbs state preparation with a truncated taylor series''. Physical Review Applied 16, 054035 (2021).","DOI":"10.1103\/PhysRevApplied.16.054035"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.110.012445"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.61.022301"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Arnau Riera, Christian Gogolin, and Jens Eisert. ``Thermalization in nature and on a quantum computer''. Physical Review Letters 108, 080402 (2012).","DOI":"10.1103\/PhysRevLett.108.080402"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Jingxiang Wu and Timothy H. Hsieh. ``Variational thermal quantum simulation via thermofield double states''. Physical Review Letters 123, 220502 (2019).","DOI":"10.1103\/PhysRevLett.123.220502"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Yi\u011fit Suba\u015f\u0131, Lukasz Cincio, and Patrick J Coles. ``Entanglement spectroscopy with a depth-two quantum circuit''. Journal of Physics A: Mathematical and Theoretical 52, 044001 (2019).","DOI":"10.1088\/1751-8121\/aaf54d"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Yihui Quek, Eneet Kaur, and Mark M. Wilde. ``Multivariate trace estimation in constant quantum depth''. Quantum 8, 1220 (2024).","DOI":"10.22331\/q-2024-01-10-1220"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nature Physics 16, 1050\u20131057 (2020).","DOI":"10.1038\/s41567-020-0932-7"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Aniket Rath, Cyril Branciard, Anna Minguzzi, and Beno\u0131\u0302t Vermersch. ``Quantum fisher information from randomized measurements''. Physical Review Letters 127, 260501 (2021).","DOI":"10.1103\/PhysRevLett.127.260501"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. ``Quantum fingerprinting''. Physical Review Letters 87, 167902 (2001).","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"19","unstructured":"Daniel Gottesman and Isaac Chuang. ``Quantum digital signatures'' (2001). arXiv:quant-ph\/0105032."},{"key":"20","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.124.060503"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Steph Foulds, Viv Kendon, and Tim Spiller. ``The controlled swap test for determining quantum entanglement''. Quantum Science and Technology 6, 035002 (2021).","DOI":"10.1088\/2058-9565\/abe458"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Xavier Gitiaux, Ian Morris, Maria Emelianenko, and Mingzhen Tian. ``Swap test for an arbitrary number of quantum states''. Quantum Information Processing 21, 344 (2022).","DOI":"10.1007\/s11128-022-03643-1"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Micha\u0142 Oszmaniec, Daniel J. Brod, and Ernesto F. Galv\u00e3o. ``Measuring relational information between quantum states, and applications''. New Journal of Physics 26, 013053 (2024).","DOI":"10.1088\/1367-2630\/ad1a27"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Tuan-Yow Chien and Shayne Waldron. ``A characterization of projective unitary equivalence of finite frames and applications''. SIAM Journal on Discrete Mathematics 30, 976\u2013994 (2016).","DOI":"10.1137\/15M1042140"},{"key":"25","doi-asserted-by":"publisher","unstructured":"V. Bargmann. ``Note on wigner's theorem on symmetry operations''. Journal of Mathematical Physics 5, 862\u2013868 (1964).","DOI":"10.1063\/1.1704188"},{"key":"26","doi-asserted-by":"publisher","unstructured":"P. W. Shor. ``Fault-tolerant quantum computation''. In Proceedings of 37th Conference on Foundations of Computer Science. Pages 56\u201365. (1996).","DOI":"10.1109\/SFCS.1996.548464"},{"key":"27","unstructured":"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."},{"key":"28","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1098\/rspa.2022.0733"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Antoine Neven, Jose Carrasco, Vittorio Vitale, Christian Kokail, Andreas Elben, Marcello Dalmonte, Pasquale Calabrese, Peter Zoller, Beno\u0131\u0302t Vermersch, Richard Kueng, et al. ``Symmetry-resolved entanglement detection using partial transpose moments''. npj Quantum Information 7, 152 (2021).","DOI":"10.1038\/s41534-021-00487-y"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Rafael Wagner, Zohar Schwartzman-Nowik, Ismael L Paiva, Amit Te\u2019eni, Antonio Ruiz-Molero, Rui Soares Barbosa, Eliahu Cohen, and Ernesto F Galv\u00e3o. ``Quantum circuits for measuring weak values, kirkwood\u2013dirac quasiprobability distributions, and state spectra''. Quantum Science and Technology 9, 015030 (2024).","DOI":"10.1088\/2058-9565\/ad124c"},{"key":"31","doi-asserted-by":"publisher","unstructured":"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\u2013993. SIAM (2025).","DOI":"10.1137\/1.9781611978322.28"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevB.85.035409"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Armen Bagdasaryan, Serkan Araci, Mehmet A\u00e7ikg\u00f6z, and H. M. Srivastava. ``Analogues of newton\u2013girard power-sum formulas for entire and meromorphic functions with applications to the riemann zeta function''. Journal of Number Theory 147, 92\u2013102 (2015).","DOI":"10.1016\/j.jnt.2014.07.006"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Jos\u00e9 Luis Cereceda. ``Sums of powers of integers and stirling numbers''. Resonance 27, 769\u2013784 (2022).","DOI":"10.1007\/s12045-022-1371-9"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Ronald G Mosier. ``Root neighborhoods of a polynomial''. Mathematics of Computation 47, 265\u2013273 (1986).","DOI":"10.1090\/S0025-5718-1986-0842134-4"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Antonio D. C\u00f3rcoles, 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\u20131352 (2019).","DOI":"10.1109\/JPROC.2019.2954005"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Konstantinos Georgopoulos, Clive Emary, and Paolo Zuliani. ``Modeling and simulating the noisy behavior of near-term quantum computers''. Physical Review A 104, 062432 (2021).","DOI":"10.1103\/PhysRevA.104.062432"},{"key":"38","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.107.012606"},{"key":"39","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevX.11.041036"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631\u2013633 (2014).","DOI":"10.1038\/nphys3029"},{"key":"41","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41534-017-0013-7"},{"key":"42","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.125.200501"},{"key":"43","unstructured":"Zhenhuan Liu, Weiyuan Gong, Zhenyu Du, and Zhenyu Cai. ``Exponential separations between quantum learning with and without purification'' (2024). arXiv:2410.17718."},{"key":"44","doi-asserted-by":"publisher","unstructured":"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\u20131105. (2024).","DOI":"10.1109\/FOCS61266.2024.00072"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-08-27-1832\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T10:57:15Z","timestamp":1756292235000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-08-27-1832\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,27]]},"references-count":45,"URL":"https:\/\/doi.org\/10.22331\/q-2025-08-27-1832","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,27]]},"article-number":"1832"}}