Multivariate trace estimation in constant quantum depth

Yihui Quek1,2,3, Eneet Kaur4,5, and Mark M. Wilde6,7

1Department of Mathematics, Massachusetts Institute of Technology, Cambridge MA 02139
2Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
3Information Systems Laboratory, Stanford University, Palo Alto, CA 94305, USA
4Cisco Quantum Lab, Los Angeles, USA
5Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
6School of Electrical and Computer Engineering, Cornell University, Ithaca, New York 14850, USA
7Hearne Institute for Theoretical Physics, Department of Physics and Astronomy, and Center for Computation and Technology, Louisiana State University, Baton Rouge, Louisiana 70803, USA

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


There is a folkloric belief that a depth-$\Theta(m)$ quantum circuit is needed to estimate the trace of the product of $m$ density matrices (i.e., a multivariate trace), a subroutine crucial to applications in condensed matter and quantum information science. We prove that this belief is overly conservative by constructing a constant quantum-depth circuit for the task, inspired by the method of Shor error correction. Furthermore, our circuit demands only local gates in a two dimensional circuit – we show how to implement it in a highly parallelized way on an architecture similar to that of Google's $Sycamore$ processor. With these features, our algorithm brings the central task of multivariate trace estimation closer to the capabilities of near-term quantum processors. We instantiate the latter application with a theorem on estimating nonlinear functions of quantum states with "well-behaved" polynomial approximations.

► BibTeX data

► References

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

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

[3] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. ``Quantum fingerprinting''. Physical Review Letters 87, 167902 (2001).

[4] Sonika Johri, Damian S. Steiger, and Matthias Troyer. ``Entanglement spectroscopy on a quantum computer''. Physical Review B 96, 195136 (2017).

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

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

[7] Paweł Horodecki and Artur Ekert. ``Method for direct detection of quantum entanglement''. Physical Review Letters 89, 127902 (2002).

[8] Matthew S. Leifer, Noah Linden, and Andreas Winter. ``Measuring polynomial invariants of multiparty quantum states''. Physical Review A 69, 052304 (2004).

[9] Tiff Brydges, Andreas Elben, Petar Jurcevic, Benoît Vermersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, and Christian F. Roos. ``Probing Rényi entanglement entropy via randomized measurements''. Science 364, 260–263 (2019).

[10] Michał Oszmaniec, Daniel J. Brod, and Ernesto F. Galvão. ``Measuring relational information between quantum states, and applications'' (2021) arXiv:2109.10006.

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

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

[13] Valentine Bargmann. ``Note on Wigner's theorem on symmetry operations''. Journal of Mathematical Physics 5, 862–868 (1964).

[14] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009).

[15] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Symposium on the Theory of Computing. Pages 193–204. (2019).

[16] András Gilyén, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M. Wilde. ``Quantum algorithm for Petz recovery channels and pretty good measurements''. Physical Review Letters 128, 220502 (2022).

[17] Frank Pollmann, Ari M. Turner, Erez Berg, and Masaki Oshikawa. ``Entanglement spectrum of a topological phase in one dimension''. Physical Review B 81, 064439 (2010).

[18] Hong Yao and Xiao-Liang Qi. ``Entanglement entropy and entanglement spectrum of the Kitaev model''. Physical Review Letters 105, 080501 (2010).

[19] Lukasz Fidkowski. ``Entanglement spectrum of topological insulators and superconductors''. Physical Review Letters 104, 130502 (2010).

[20] Hui Li and F. D. M. Haldane. ``Entanglement spectrum as a generalization of entanglement entropy: Identification of topological order in non-Abelian fractional quantum Hall effect states''. Physical Review Letters 101, 010504 (2008).

[21] Claudio Chamon, Alioscia Hamma, and Eduardo R. Mucciolo. ``Emergent irreversibility and entanglement spectrum statistics''. Physical Review Letters 112, 240501 (2014).

[22] G. De Chiara, L. Lepori, M. Lewenstein, and A. Sanpera. ``Entanglement spectrum, critical exponents, and order parameters in quantum spin chains''. Physical Review Letters 109, 237208 (2012).

[23] Jens Eisert, Marcus Cramer, and Martin B. Plenio. ``Colloquium: Area laws for the entanglement entropy''. Reviews of Modern Physics 82, 277–306 (2010).

[24] M. Mezard, G. Parisi, and M. Virasoro. ``Spin glass theory and beyond''. World Scientific. (1986).

[25] Justin Yirka and Yiğit Subaşı. ``Qubit-efficient entanglement spectroscopy using qubit resets''. Quantum 5, 535 (2021).

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

[27] Frank Arute, Kunal Arya, et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).

[28] Peter W. Shor. ``Fault-tolerant quantum computation''. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. Page 56. FOCS '96USA (1996). IEEE Computer Society.

[29] Wassily Hoeffding. ``Probability inequalities for sums of bounded random variables''. Journal of the American Statistical Association 58, 13–30 (1963).

[30] Daniel Gottesman. ``An introduction to quantum error correction and fault-tolerant quantum computation''. Quantum Information Science and Its Contributions to Mathematics, Proceedings of Symposia in Applied Mathematics 68, 13–58 (2010). arXiv:0904.2557.

[31] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. ``Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 515–526. STOC 2019New York, NY, USA (2019). Association for Computing Machinery.

[32] Zhenning Liu and Alexandru Gheorghiu. ``Depth-efficient proofs of quantumness''. Quantum 6, 807 (2022).

[33] Markus Grassl and Thomas Beth. ``Cyclic quantum error-correcting codes and quantum shift registers''. Proceedings of the Royal Society A 456, 2689–2706 (2000). arXiv:quant-ph/​991006.

[34] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014).

[35] 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, 1–7 (2017).

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

[37] 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). arXiv:2002.08953.

[38] Aniket Rath, Cyril Branciard, Anna Minguzzi, and Benoı̂t Vermersch. ``Quantum Fisher information from randomized measurements''. Physical Review Letters 127, 260501 (2021).

[39] Fedja. ``Answer to stack exchange post''. https:/​/​​3b9v7pum (2021).

[40] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. ``Minimax estimation of functionals of discrete distributions''. IEEE Transactions on Information Theory 61, 2835–2885 (2015).

[41] Yihong Wu and Pengkun Yang. ``Minimax rates of entropy estimation on large alphabets via best polynomial approximation''. IEEE Transactions on Information Theory 62, 3702–3720 (2016).

[42] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. ``Maximum likelihood estimation of functionals of discrete distributions''. IEEE Transactions on Information Theory 63, 6774–6798 (2017).

[43] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. ``Estimating Rényi entropy of discrete distributions''. IEEE Transactions on Information Theory 63, 38–56 (2017).

[44] Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende, and Aaron B. Wagner. ``Estimating quantum entropy''. IEEE Journal on Selected Areas in Information Theory 1, 454–468 (2020).

[45] András Gilyén and Tongyang Li. ``Distributional Property Testing in a Quantum World''. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:19. Dagstuhl, Germany (2020). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[46] Alessandro Luongo and Changpeng Shao. ``Quantum algorithms for spectral sums''. unpublished (2020) arXiv:2011.06475.

[47] Sathyawageeswar Subramanian and Min-Hsiu Hsieh. ``Quantum algorithm for estimating ${\alpha}$-Rényi entropies of quantum states''. Physical Review A 104, 022428 (2021).

[48] Youle Wang, Benchi Zhao, and Xin Wang. ``Quantum algorithms for estimating quantum entropies''. Physical Review Applied 19, 044041 (2023).

[49] Tom Gur, Min-Hsiu Hsieh, and Sathyawageeswar Subramanian. ``Sublinear quantum algorithms for estimating von Neumann entropy'' (2021) arXiv:2111.11139.

[50] Tongyang Li, Xinzhao Wang, and Shengyu Zhang. ``A unified quantum algorithm framework for estimating properties of discrete probability distributions'' (2022) arXiv:2212.01571.

[51] Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, and Mingsheng Ying. ``Quantum algorithm for fidelity estimation''. IEEE Transactions on Information Theory 69, 273–282 (2023).

[52] András Gilyén and Alexander Poremba. ``Improved quantum algorithms for fidelity estimation'' (2022) arXiv:2203.15993.

[53] David Pérez-García, Michael M. Wolf, Denes Petz, and Mary Beth Ruskai. ``Contractivity of positive and trace-preserving maps under $L_p$ norms''. Journal of Mathematical Physics 47, 083506 (2006). arXiv:math-ph/​0601063.

[54] Umesh Vazirani. ``Computational probes of Hilbert space''. Talk available at https:/​/​​watch?v=ajKoO5RFtwo (2019). Quote from Q2B 2019, attributed to an unknown person.

[55] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborger, and Patrick J. Coles. ``Quantum-assisted quantum compiling''. Quantum 3, 140 (2019).

[56] Kunal Sharma, Sumeet Khatri, Marco Cerezo, and Patrick J. Coles. ``Noise resilience of variational quantum compiling''. New Journal of Physics 22, 043006 (2020).

[57] Sang Min Lee, Jinhyoung Lee, and Jeongho Bang. ``Learning unknown pure quantum states''. Physical Review A 98, 052302 (2018).

[58] Ranyiliu Chen, Zhixin Song, Xuanqiang Zhao, and Xin Wang. ``Variational quantum algorithms for trace distance and fidelity estimation''. Quantum Science and Technology 7, 015019 (2022). arXiv:2012.05768.

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

[60] Y. Ding, P. Gokhale, S. Lin, R. Rines, T. Propson, and F. T. Chong. ``Systematic crosstalk mitigation for superconducting qubits via frequency-aware compilation''. In 2020 53rd Annual IEEE/​ACM International Symposium on Microarchitecture (MICRO). Pages 201–214. Los Alamitos, CA, USA (2020). IEEE Computer Society.

[61] Ashley Montanaro. ``Quantum speedup of monte carlo methods''. Proceedings of the Royal Society A 471, 20150301 (2015).

[62] Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng. ``Low depth algorithms for quantum amplitude estimation''. Quantum 6, 745 (2022).

[63] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini, and Michael Lubasch. ``Variational quantum amplitude estimation''. Quantum 6, 670 (2022).

[64] Dénes Petz. ``Quasi-entropies for states of a von Neumann algebra''. Publ. RIMS, Kyoto University 21, 787–800 (1985).

[65] Dénes Petz. ``Quasi-entropies for finite quantum systems''. Reports in Mathematical Physics 23, 57–65 (1986).

Cited by

[1] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).

[2] Kevin C. Smith, Eleanor Crane, Nathan Wiebe, and S. M. Girvin, "Deterministic Constant-Depth Preparation of the AKLT State on a Quantum Processor Using Fusion Measurements", PRX Quantum 4 2, 020315 (2023).

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

[4] Soorya Rethinasamy, Rochisha Agarwal, Kunal Sharma, and Mark M. Wilde, "Estimating distinguishability measures on quantum computers", Physical Review A 108 1, 012409 (2023).

[5] Ziv Goldfeld, Dhrumil Patel, Sreejith Sreekumar, and Mark M. Wilde, "Quantum Neural Estimation of Entropies", arXiv:2307.01171, (2023).

[6] Qisheng Wang and Zhicheng Zhang, "Fast Quantum Algorithms for Trace Distance Estimation", arXiv:2301.06783, (2023).

[7] Zachary P. Bradshaw, Margarite L. LaBorde, and Mark M. Wilde, "Cycle index polynomials and generalized quantum separability tests", Proceedings of the Royal Society of London Series A 479 2274, 20220733 (2023).

[8] Filipa C. R. Peres and Ernesto F. Galvão, "Quantum circuit compilation and hybrid computation using Pauli-based computation", Quantum 7, 1126 (2023).

[9] Nouédyn Baspin, Omar Fawzi, and Ala Shayeghi, "A lower bound on the overhead of quantum error correction in low dimensions", arXiv:2302.04317, (2023).

[10] J. Knörzer, D. Malz, and J. I. Cirac, "Cross-platform verification in quantum networks", Physical Review A 107 6, 062424 (2023).

[11] Michael de Oliveira, Luís S. Barbosa, and Ernesto F. Galvão, "Quantum advantage in temporally flat measurement-based quantum computation", arXiv:2212.03668, (2022).

[12] Filipa C. R. Peres, "Pauli-based model of quantum computation with higher-dimensional systems", Physical Review A 108 3, 032606 (2023).

[13] Margarite L. LaBorde, "A Menagerie of Symmetry Testing Quantum Algorithms", arXiv:2305.14560, (2023).

[14] T. J. Volkoff and Yiğit Subaşı, "Ancilla-free continuous-variable SWAP test", Quantum 6, 800 (2022).

[15] Jue Xu and Qi Zhao, "Towards efficient and generic entanglement detection by machine learning", arXiv:2211.05592, (2022).

[16] 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 1, 012606 (2023).

[17] Sreejith Sreekumar and Mario Berta, "Limit Distribution Theory for Quantum Divergences", arXiv:2311.13694, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-02-27 14:17:40) and SAO/NASA ADS (last updated successfully 2024-02-27 14:17:41). The list may be incomplete as not all publishers provide suitable and complete citation data.