Estimating expectation values using approximate quantum states

Marco Paini; Amir Kalev; Dan Padilha; Brendan Ruck

doi:10.22331/q-2021-03-16-413

Estimating expectation values using approximate quantum states

Marco Paini¹, Amir Kalev², Dan Padilha¹, and Brendan Ruck³

¹Rigetti Computing, 138 Holborn, London, EC1N 2SW, UK.
²Information Sciences Institute, University of Southern California, Arlington, VA 22203, USA.
³Rigetti Computing, 2919 Seventh St, Berkeley, CA 94710, USA.

Published:	2021-03-16, volume 5, page 413
Eprint:	arXiv:2011.04754v3
Doi:	https://doi.org/10.22331/q-2021-03-16-413
Citation:	Quantum 5, 413 (2021).

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

Abstract

We introduce an approximate description of an $N$-qubit state, which contains sufficient information to estimate the expectation value of any observable to a precision that is upper bounded by the ratio of a suitably-defined seminorm of the observable to the square root of the number of the system's identical preparations $M$, with no explicit dependence on $N$. We describe an operational procedure for constructing the approximate description of the state that requires, besides the quantum state preparation, only single-qubit rotations followed by single-qubit measurements. We show that following this procedure, the cardinality of the resulting description of the state grows as $3MN$. We test the proposed method on Rigetti's quantum processor unit with 12, 16 and 25 qubits for random states and random observables, and find an excellent agreement with the theory, despite experimental errors.

Popular summary

Density matrices represent our knowledge about state of quantum systems and gives us a way to calculate expectation values and predict experimental results. Estimating the density matrix of an N-body system requires the knowledge of exponentially many numbers in terms of N. The exponentially-expensive representation of quantum states turns into practical difficulties in estimating and storing density matrices, and, moreover, raises theoretical questions about the physical meaning of quantum states. This leads to the important and natural question of whether a protocol that significantly reduces or eliminates the exponential dependence is admissible. In this work, we give an affirmative answer to the question.

Specializing to N-qubit systems as an important case study, we propose an observation-based approximate description of quantum states. The approximate description grows linearly with N (rather than exponentially in N, as for density matrices) and allow us to estimate expectation values of any observable quantity, without the need to go through the density matrix formulation, with an estimation error only dependent on the number of observations and on the observable itself, independently of N. Building the approximate description of the N-qubit state only requires repetitions of single-qubit rotations followed by single-qubit measurements. The N-independence property and the simplicity of building the approximate description has the potential for improving a wide range of quantum protocols and can be considered for implementation on today's noisy quantum computers.

► BibTeX data

@article{Paini2021estimating,
  doi = {10.22331/q-2021-03-16-413},
  url = {https://doi.org/10.22331/q-2021-03-16-413},
  title = {Estimating expectation values using approximate quantum states},
  author = {Paini, Marco and Kalev, Amir and Padilha, Dan and Ruck, Brendan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {413},
  month = mar,
  year = {2021}
}

► References

[1] G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett., 91: 147902, Oct 2003. URL https://doi.org/10.1103/PhysRevLett.91.147902.
https://doi.org/10.1103/PhysRevLett.91.147902

[2] S. Aaronson. The learnability of quantum states. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 463 (2088): 3089–3114, 2007. URL https://doi.org/10.1098/rspa.2007.0113.
https://doi.org/10.1098/rspa.2007.0113

[3] M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu. Efficient quantum state tomography. Nat. Comm., 1: 149, 2010. URL https://doi.org/10.1038/ncomms1147.
https://doi.org/10.1038/ncomms1147

[4] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Phys. Rev. Lett., 105 (15): 150401, 2010. URL https://doi.org/10.1103/PhysRevLett.105.150401.
https://doi.org/10.1103/PhysRevLett.105.150401

[5] A. Kalev, R. Kosut, and I. Deutsch. Quantum tomography protocols with positivity are compressed sensing protocols. NPJ Quantum Information, 1: 15018, 2015. URL https://doi.org/10.1038/npjqi.2015.18.
https://doi.org/10.1038/npjqi.2015.18

[6] X. Gao and L.-M. Duan. Efficient representation of quantum many-body states with deep neural networks. Nat. Comm., 8: 662, 2017. URL https://doi.org/10.1038/s41467-017-00705-2.
https://doi.org/10.1038/s41467-017-00705-2

[7] G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Melko, and G. Carleo. Neural-network quantum state tomography. Nat. Phys., 18: 447, 2017. URL https://doi.org/10.1038/s41567-018-0048-5.
https://doi.org/10.1038/s41567-018-0048-5

[8] S. Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 325–338, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5559-9. URL https://doi.org/10.1145/3188745.3188802.
https://doi.org/10.1145/3188745.3188802

[9] D. Gosset and J. Smolin. A compressed classical description of quantum states. In Wim van Dam and Laura Mancinska, editors, 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. ISBN 978-3-95977-112-2. URL https://doi.org/10.4230/LIPIcs.TQC.2019.8.
https://doi.org/10.4230/LIPIcs.TQC.2019.8

[10] M. Paini. Quantum tomography via group theory. arXiv:quant-ph/0002078, 2000. URL https://arxiv.org/pdf/quant-ph/0002078.pdf.
arXiv:quant-ph/0002078

[11] G. M. D'Ariano, L. Maccone, and M. Paini. Spin tomography. J. Opt. B: Quantum and Semiclassical Optics, 5 (1): 77–84, jan 2003. URL https://doi.org/10.1088/1464-4266/5/1/311.
https://doi.org/10.1088/1464-4266/5/1/311

[12] T. Brydges, A. Elben, P. Jurcevic, C. Vermersch, B.and Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos. Probing Rényi entanglement entropy via randomized measurements. Science, 364 (6437): 260–263, 2019. URL https://doi.org/10.1126/science.aau4963.
https://doi.org/10.1126/science.aau4963

[13] A. Elben, J. Yu, G. Zhu, M. Hafezi, F. Pollmann, P. Zoller, and B. Vermersch. Many-body topological invariants from randomized measurements in synthetic quantum matter. Science Advances, 6 (15), 2020a. URL https://doi.org/10.1126/sciadv.aaz3666.
https://doi.org/10.1126/sciadv.aaz3666

[14] A. Elben, B. Vermersch, R. van Bijnen, C. Kokail, T. Brydges, C. Maier, M. K. Joshi, R. Blatt, C. F. Roos, and P. Zoller. Cross-platform verification of intermediate scale quantum devices. Phys. Rev. Lett., 124: 010504, Jan 2020b. URL https://doi.org/10.1103/PhysRevLett.124.010504.
https://doi.org/10.1103/PhysRevLett.124.010504

[15] B. Vermersch, A. Elben, L. M. Sieberer, N. Y. Yao, and P. Zoller. Probing scrambling using statistical correlations between randomized measurements. Phys. Rev. X, 9: 021061, Jun 2019. URL https://doi.org/10.1103/PhysRevX.9.021061.
https://doi.org/10.1103/PhysRevX.9.021061

[16] R. O'Donnell and J. 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. URL https://doi.org/10.1145/2897518.2897544.
https://doi.org/10.1145/2897518.2897544

[17] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Sample-optimal tomography of quantum states. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 913–925, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. URL https://doi.org/10.1145/2897518.2897585.
https://doi.org/10.1145/2897518.2897585

[18] S. Aaronson and G. N. Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 322–333, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. URL https://doi.org/10.1145/3313276.3316378.
https://doi.org/10.1145/3313276.3316378

[19] H.-Y. Huang, R. Kueng, and J. Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, Jun 2020. ISSN 1745-2481. URL https://doi.org/10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[20] S. Cheng, J. Chen, and L. Wang. Information perspective to probabilistic modeling: Boltzmann machines versus born machines. Entropy, 20 (8), 2018. URL https://doi.org/10.3390/e20080583.
https://doi.org/10.3390/e20080583

[21] M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4 (4): 043001, nov 2019. URL https://doi.org/10.1088/2058-9565/ab4eb5.
https://doi.org/10.1088/2058-9565/ab4eb5

[22] K. E. Cahill and R. J. Glauber. Density operators for fermions. Phys. Rev. A, 59: 1538–1555, Feb 1999. URL https://doi.org/10.1103/PhysRevA.59.1538.
https://doi.org/10.1103/PhysRevA.59.1538

[23] Y. Li. Talk 5 : Averages over the unitary group. In Selected topics in Mathematical Physics : Quantum Information Theory, 2013.

[24] A. Ambainis and J. Emerson. Quantum t-designs: t-wise independence in the quantum world. In Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, CCC '07, pages 129–140, Washington, DC, USA, 2007. IEEE Computer Society. ISBN 0-7695-2780-9. URL https://doi.org/10.1109/CCC.2007.26.
https://doi.org/10.1109/CCC.2007.26

Cited by

[1] Gyungmin Cho and Dohun Kim, "Machine learning on quantum experimental data toward solving quantum many-body problems", Nature Communications 15 1, 7552 (2024).

[2] Paul K. Faehrmann, Jens Eisert, Mária Kieferová, and Richard Kueng, "Short-time simulation of quantum dynamics by Pauli measurements", Physical Review A 112 1, 012602 (2025).

[3] Stefano Mangini and Daniel Cavalcanti, "Low variance estimations of many observables with tensor networks and informationally-complete measurements", Quantum 9, 1812 (2025).

[4] Keijo Korhonen, Stefano Mangini, Joonas Malmi, Hetta Vappula, and Daniel Cavalcanti, "Improving shadow estimation with locally optimal dual frames", Physical Review A 114 1, 012428 (2026).

[5] Benjamin Collis, Saahil Patel, Daniel Koch, Massimiliano Cutugno, Laura Wessing, and Paul M. Alsing, "Physics simulation via quantum graph neural network", AVS Quantum Science 5 2, 023801 (2023).

[6] Alireza Seif, Ze-Pei Cian, Sisi Zhou, Senrui Chen, and Liang Jiang, "Shadow Distillation: Quantum Error Mitigation with Classical Shadows for Near-Term Quantum Processors", PRX Quantum 4 1, 010303 (2023).

[7] Yong Siah Teo, Seongwook Shin, Hyukgun Kwon, Seok-Hyung Lee, and Hyunseok Jeong, "Virtual distillation with noise dilution", Physical Review A 107 2, 022608 (2023).

[8] Ali Kookani, Yousef Mafi, Payman Kazemikhah, Hossein Aghababa, Kazim Fouladi, and Masoud Barati, "XpookyNet: advancement in quantum system analysis through convolutional neural networks for detection of entanglement", Quantum Machine Intelligence 6 2, 50 (2024).

[9] Nic Ezzell, Elliott M Ball, Aliza U Siddiqui, Mark M Wilde, Andrew T Sornborger, Patrick J Coles, and Zoë Holmes, "Quantum mixed state compiling", Quantum Science and Technology 8 3, 035001 (2023).

[10] Rawad Mezher, James Mills, and Elham Kashefi, "Mitigating errors by quantum verification and postselection", Physical Review A 105 5, 052608 (2022).

[11] Uman Khalid, Junaid Ur Rehman, Haejoon Jung, Trung Q. Duong, Octavia A. Dobre, and Hyundong Shin, "Quantum Property Learning for NISQ Networks: Universal Quantum Witness Machines", IEEE Transactions on Communications 73 4, 2207 (2025).

[12] Andreas Ketterer, Satoya Imai, Nikolai Wyderka, and Otfried Gühne, "Statistically significant tests of multiparticle quantum correlations based on randomized measurements", Physical Review A 106 1, L010402 (2022).

[13] Pei Zeng, "Tailoring randomized-measurement schemes for practical devices", Quantum Views 7, 74 (2023).

[14] Uman Khalid, Trung Q. Duong, and Hyundong Shin, 2024 International Conference on Quantum Communications, Networking, and Computing (QCNC) 259 (2024) ISBN:979-8-3503-6677-8.

[15] Paul K. Faehrmann, Jens Eisert, and Richard Kueng, "In the Shadow of the Hadamard Test: Using the Garbage State for Good and Further Modifications", Physical Review Letters 135 15, 150603 (2025).

[16] Jae Dong Noh, Aleksander Lasek, Jade LeSchack, and Nicole Yunger Halpern, "Kubo–Martin–Schwinger relation for energy eigenstates of SU(2)-symmetric quantum many-body systems", APL Quantum 3 2, 026103 (2026).

[17] John P. T. Stenger, Daniel Gunlycke, and C. Stephen Hellberg, "Expanding variational quantum eigensolvers to larger systems by dividing the calculations between classical and quantum hardware", Physical Review A 105 2, 022438 (2022).

[18] Andrew Zhao and Akimasa Miyake, "Group-theoretic error mitigation enabled by classical shadows and symmetries", npj Quantum Information 10 1, 57 (2024).

[19] Sophia Ohnemus, Heinz-Peter Breuer, and Andreas Ketterer, "Quantifying multiparticle entanglement with randomized measurements", Physical Review A 107 4, 042406 (2023).

[20] Gelo Noel M Tabia, Alex Yueh-Ting Shih, Jin-Yuan Zheng, and Yeong-Cherng Liang, "Almost device-independent calibration beyond Born’s rule: Bell tests for cross-talk detection", Quantum Science and Technology 10 3, 035056 (2025).

[21] Andrew Zhao, Nicholas C. Rubin, and Akimasa Miyake, "Fermionic Partial Tomography via Classical Shadows", Physical Review Letters 127 11, 110504 (2021).

[22] Takaharu Yoshida, Yuta Shingu, Chihaya Shimada, Tetsuro Nikuni, Hideaki Hakoshima, and Yuichiro Matsuzaki, "Hardware-efficient quantum annealing with error mitigation via classical shadow", Physical Review A 113 6, 062430 (2026).

[23] David Garvin, Alexei Kondratyev, Alexander Lipton, and Marco Paini, "Quantum Two-Sample Test for Investment Strategies", SSRN Electronic Journal (2024).

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

[25] Junhyung Lyle Kim, George Kollias, Amir Kalev, Ken X. Wei, and Anastasios Kyrillidis, "Fast Quantum State Reconstruction via Accelerated Non-Convex Programming", Photonics 10 2, 116 (2023).

[26] Kianna Wan, William J. Huggins, Joonho Lee, and Ryan Babbush, "Matchgate Shadows for Fermionic Quantum Simulation", Communications in Mathematical Physics 404 2, 629 (2023).

[27] Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia, "Robust Shadow Estimation", PRX Quantum 2 3, 030348 (2021).

[28] Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V. Albert, and John Preskill, "Provably efficient machine learning for quantum many-body problems", Science 377 6613, eabk3333 (2022).

[29] Ivan Henao, Raam Uzdin, and Nadav Katz, "Experimental detection of microscopic environments using thermodynamic observables", arXiv:1908.08968, (2019).

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

Could not fetch ADS cited-by data during last attempt 2026-08-09 10:27:43: Cannot retrieve data from ADS due to rate limitations.

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.