Sample-optimal classical shadows for pure states

Sample-optimal classical shadows for pure states

Time Stamp: June 17, 2024 8:05 AM
Sample-optimal classical shadows for pure states PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Daniel Grier1,2, Hakop Pashayan2,3,4,5, and Luke Schaeffer2,3,6

1Department of Mathematics and Department of Computer Science and Engineering, UC San Diego
2Institute for Quantum Computing, University of Waterloo, Canada
3Department of Combinatorics and Optimization, University of Waterloo, Canada
4Perimeter Institute for Theoretical Physics, Waterloo, Canada
5Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Germany
6Joint Center for Quantum Information and Computer Science, University of Maryland, College Park

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

Abstract

We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state $rho$ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate $mathrm{Tr}(O rho)$ for any Hermitian observable $O$ to within additive error $epsilon$ provided $mathrm{Tr}(O^2)leq B$ and $lVert O rVert = 1$. Our main result applies to the joint measurement setting, where we show $tilde{Theta}(sqrt{B}epsilon^{-1} + epsilon^{-2})$ samples of $rho$ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of $rho$ can be compressed for observable estimation. In the independent measurement setting, we show that $mathcal O(sqrt{Bd} epsilon^{-1} + epsilon^{-2})$ samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.

â–º BibTeX data

â–º References

[1] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. “Sample-optimal tomography of quantum states”. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2016). Page 913–925. New York, NY, USA (2016). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​2897518.2897585

[2] Ryan O’Donnell and John Wright. “Efficient quantum tomography”. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2016). Page 899–912. New York, NY, USA (2016). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​2897518.2897544

[3] Scott Aaronson. “Shadow tomography of quantum states”. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). Page 325–338. New York, NY, USA (2018). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​3188745.3188802

[4] Costin Bădescu and Ryan O’Donnell. “Improved quantum data analysis”. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021). Page 1398–1411. New York, NY, USA (2021). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​3406325.3451109

[5] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. “Exponential separations between learning with and without quantum memory”. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2022). Pages 574–585. Los Alamitos, CA, USA (2022).
https:/​/​doi.org/​10.1109/​FOCS52979.2021.00063

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

[7] David Gosset and John Smolin. “A compressed classical description of quantum states”. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:9. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2019.8

[8] A J Scott. “Tight informationally complete quantum measurements”. Journal of Physics A: Mathematical and General 39, 13507 (2006).
https:/​/​doi.org/​10.1088/​0305-4470/​39/​43/​009

[9] D. Gross, F. Krahmer, and R. Kueng. “A partial derandomization of PhaseLift using spherical designs”. Journal of Fourier Analysis and Applications 21, 229–266 (2015).
https:/​/​doi.org/​10.1007/​s00041-014-9361-2

[10] Daniel A. Roberts and Beni Yoshida. “Chaos and complexity by design”. Journal of High Energy Physics 2017, 121 (2017).
https:/​/​doi.org/​10.1007/​JHEP04(2017)121

[11] G. Lugosi and S. Mendelson. “Mean estimation and regression under heavy-tailed distributions: A survey”. Found. Comp. Math. 19, 1145–1190 (2019).
https:/​/​doi.org/​10.1007/​s10208-019-09427-x

[12] M. Lerasle. “Lecture notes: Selected topics on robust statistical learning theory” (2019). arXiv:1908.10761.
arXiv:1908.10761

[13] Bela Bajnok. “Construction of spherical $t$-designs”. Geometriae Dedicata 43, 167–179 (1992).
https:/​/​doi.org/​10.1007/​BF00147866

[14] A. Hayashi, T. Hashimoto, and M. Horibe. “Reexamination of optimal quantum state estimation of pure states”. Phys. Rev. A 72, 032325 (2005).
https:/​/​doi.org/​10.1103/​PhysRevA.72.032325

[15] Andriy Bondarenko, Danylo Radchenko, and Maryna Viazovska. “Optimal asymptotic bounds for spherical designs”. Annals of Mathematics 178, 443–452 (2013).
https:/​/​doi.org/​10.4007/​annals.2013.178.2.2

[16] Michael A Nielsen and Isaac L Chuang. “Quantum computation and quantum information”. Cambridge University Press. (2010).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[17] Zak Webb. “The Clifford group forms a unitary 3-design”. Quantum Information and Computation 16, 1379–1400 (2016).
https:/​/​doi.org/​10.26421/​qic16.15-16-8

[18] Huangjun Zhu. “Multiqubit Clifford groups are unitary 3-designs”. Physical Review A 96 (2017).
https:/​/​doi.org/​10.1103/​physreva.96.062336

[19] Richard Kueng and David Gross. “Qubit stabilizer states are complex projective 3-designs” (2015). arXiv:1510.02767.
arXiv:1510.02767

[20] Huangjun Zhu, Richard Kueng, Markus Grassl, and David Gross. “The Clifford group fails gracefully to be a unitary 4-design” (2016). arXiv:1609.08172.
arXiv:1609.08172

[21] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald De Wolf. “Exponential separations for one-way quantum communication complexity, with applications to cryptography”. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC 2007). Pages 516–525. New York, NY, USA (2007). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​1250790.1250866

[22] Carl W. Helstrom. “Quantum detection and estimation theory”. Journal of Statistical Physics 1, 231–252 (1969).
https:/​/​doi.org/​10.1007/​BF01007479

[23] C.A. Fuchs and J. van de Graaf. “Cryptographic distinguishability measures for quantum-mechanical states”. IEEE Transactions on Information Theory 45, 1216–1227 (1999).
https:/​/​doi.org/​10.1109/​18.761271

[24] Andrew Chi-Chin Yao. “Probabilistic computations: Toward a unified measure of complexity”. In 18th Annual Symposium on Foundations of Computer Science (SFCS 1977). Pages 222–227. IEEE (1977).
https:/​/​doi.org/​10.1109/​SFCS.1977.24

[25] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. “The communication complexity of correlation”. IEEE Transactions on Information Theory 56, 438–449 (2010).
https:/​/​doi.org/​10.1109/​TIT.2009.2034824

[26] Alexander Semenovich Holevo. “Bounds for the quantity of information transmitted by a quantum communication channel”. Problemy Peredachi Informatsii 9, 3–11 (1973). url: http:/​/​mi.mathnet.ru/​ppi903.
http:/​/​mi.mathnet.ru/​ppi903

[27] Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, and Hakop Pashayan. “Shallow shadows: Expectation estimation using low-depth random Clifford circuits” (2022). arXiv:2209.12924.
arXiv:2209.12924

[28] Ahmed A. Akhtar, Hong-Ye Hu, and Yi-Zhuang You. “Scalable and flexible classical shadow tomography with tensor networks”. Quantum 7, 1026 (2023).
https:/​/​doi.org/​10.22331/​q-2023-06-01-1026

Cited by

[1] Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, and Hakop Pashayan, “Shallow shadows: Expectation estimation using low-depth random Clifford circuits”, arXiv:2209.12924, (2022).

[2] Bujiao Wu and Dax Enshan Koh, “Error-mitigated fermionic classical shadows on noisy quantum devices”, npj Quantum Information 10, 39 (2024).

[3] Minh C. Tran, Daniel K. Mark, Wen Wei Ho, and Soonwon Choi, “Measuring Arbitrary Physical Properties in Analog Quantum Simulation”, Physical Review X 13 1, 011049 (2023).

[4] Matteo Ippoliti, “Classical shadows based on locally-entangled measurements”, Quantum 8, 1293 (2024).

[5] Alexander Gresch and Martin Kliesch, “Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping”, arXiv:2301.03385, (2023).

[6] Sitan Chen, Weiyuan Gong, and Qi Ye, “Optimal tradeoffs for estimating Pauli observables”, arXiv:2404.19105, (2024).

[7] Daniel Grier, Hakop Pashayan, and Luke Schaeffer, “Principal eigenstate classical shadows”, arXiv:2405.13939, (2024).

[8] Adam Bene Watts and John Bostanci, “Quantum Event Learning and Gentle Random Measurements”, arXiv:2210.09155, (2022).

[9] Omar Fawzi, Richard Kueng, Damian Markham, and Aadil Oufkir, “Learning Properties of Quantum States Without the I.I.D. Assumption”, arXiv:2401.16922, (2024).

[10] Yinfei Li, Sanjib Ghosh, Jiangwei Shang, Qihua Xiong, and Xiangdong Zhang, “Estimating many properties of a quantum state via quantum reservoir processing”, Physical Review Research 6 1, 013211 (2024).

[11] Fong Yew Leong, Dax Enshan Koh, Jian Feng Kong, Siong Thye Goh, Jun Yong Khoo, Wei-Bin Ewe, Hongying Li, Jayne Thompson, and Dario Poletti, “Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach”, arXiv:2406.08755, (2024).

[12] Daniel Grier, Sihan Liu, and Gaurav Mahajan, “Improved classical shadows from local symmetries in the Schur basis”, arXiv:2405.09525, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-06-20 00:23:11). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2024-06-20 00:23:09).

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.

Time Stamp:

More from Quantum Journal