On the connection between least squares, regularization, and classical shadows

Zhihui Zhu; Joseph M. Lukens; Brian T. Kirby

doi:10.22331/q-2024-08-29-1455

On the connection between least squares, regularization, and classical shadows

Zhihui Zhu¹, Joseph M. Lukens^2,3, and Brian T. Kirby^4,5

¹Department of Computer Science and Engineering, The Ohio State University, Columbus, Ohio 43210, USA
²Research Technology Office and Quantum Collaborative, Arizona State University, Tempe, Arizona 85287, USA
³Quantum Information Science Section, Oak Ridge National Laboratory, Oak Ridge, Tennessee 37831, USA
⁴DEVCOM Army Research Laboratory, Adelphi, MD 20783, USA
⁵Tulane University, New Orleans, LA 70118, USA

Published:	2024-08-29, volume 8, page 1455
Eprint:	arXiv:2310.16921v4
Doi:	https://doi.org/10.22331/q-2024-08-29-1455
Citation:	Quantum 8, 1455 (2024).

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

Updated after initial publication: This publication was updated to version v4 after the initial publication. The authors left the following comment on the arXiv:

accepted for publication in Quantum (v3); post-publication typos corrected (v4)

Abstract

Classical shadows (CS) offer a resource-efficient means to estimate quantum observables, circumventing the need for exhaustive state tomography. Here, we clarify and explore the connection between CS techniques and least squares (LS) and regularized least squares (RLS) methods commonly used in machine learning and data analysis. By formal identification of LS and RLS ``shadows'' completely analogous to those in CS---namely, point estimators calculated from the empirical frequencies of single measurements---we show that both RLS and CS can be viewed as regularizers for the underdetermined regime, replacing the pseudoinverse with invertible alternatives. Through numerical simulations, we evaluate RLS and CS from three distinct angles: the tradeoff in bias and variance, mismatch between the expected and actual measurement distributions, and the interplay between the number of measurements and number of shots per measurement.

Compared to CS, RLS attains lower variance at the expense of bias, is robust to distribution mismatch, and is more sensitive to the number of shots for a fixed number of state copies---differences that can be understood from the distinct approaches taken to regularization. Conceptually, our integration of LS, RLS, and CS under a unifying ``shadow'' umbrella aids in advancing the overall picture of CS techniques, while practically our results highlight the tradeoffs intrinsic to these measurement approaches, illuminating the circumstances under which either RLS or CS would be preferred, such as unverified randomness for the former or unbiased estimation for the latter.

Featured image: Shadow picture of quantum estimation. Measurements (POVMs) are performed on copies of a ground truth quantum state, from which shadows can be computed and averaged to produce a final estimate. The only difference between the three techniques explored lies in the shadow operation chosen.

Popular summary

Just as one can deduce the shape of a three-dimensional object by shining light at different angles and examining the shadows formed, the technique of classical shadows reconstructs quantum objects from measurements of individual slices—or shadows—of the unknown quantum system. Classical shadows have revolutionized the field of quantum estimation and may seem entirely different from traditional estimators like least squares at first glance. However, as the authors demonstrate, the least squares method also relies on shadows from individual measurements. By showing how classical shadows act as a form of regularization for least squares when very few measurements are available, the authors demystify this remarkable technique. They reveal the tradeoffs between classical shadows and regularized least squares in conventional estimation, including a significant advantage in computational efficiency for classical shadows in the limit of many measurements. These insights offer practical guidance for selecting the appropriate estimation method depending on the number of measurements and the desired balance between bias and variance.

► BibTeX data

@article{Zhu2024connectionbetween,
  doi = {10.22331/q-2024-08-29-1455},
  url = {https://doi.org/10.22331/q-2024-08-29-1455},
  title = {On the connection between least squares, regularization, and classical shadows},
  author = {Zhu, Zhihui and Lukens, Joseph M. and Kirby, Brian T.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1455},
  month = aug,
  year = {2024}
}

► References

[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge, 2000).
https://doi.org/10.1017/CBO9780511976667

[2] S. Aaronson, in Proc. 50th Ann. ACM SIGACT Sym. Theor. Comput. (ACM, 2018) pp. 325–338.
https://doi.org/10.1145/3188745.3188802

[3] P. Horodecki and A. Ekert, Phys. Rev. Lett. 89, 127902 (2002).
https://doi.org/10.1103/PhysRevLett.89.127902

[4] P. Horodecki, Phys. Rev. Lett. 90, 167901 (2003).
https://doi.org/10.1103/PhysRevLett.90.167901

[5] F. Mintert and A. Buchleitner, Phys. Rev. Lett. 98, 140505 (2007).
https://doi.org/10.1103/PhysRevLett.98.140505

[6] S. J. van Enk and C. W. Beenakker, Phys. Rev. Lett. 108, 110503 (2012).
https://doi.org/10.1103/PhysRevLett.108.110503

[7] N. Wyderka, A. Ketterer, S. Imai, J. L. Bönsel, D. E. Jones, B. T. Kirby, X.-D. Yu, and O. Gühne, Phys. Rev. Lett. 131, 090201 (2023).
https://doi.org/10.1103/PhysRevLett.131.090201

[8] A. Ketterer, N. Wyderka, and O. Gühne, Phys. Rev. Lett. 122, 120505 (2019).
https://doi.org/10.1103/PhysRevLett.122.120505

[9] S. Imai, N. Wyderka, A. Ketterer, and O. Gühne, Phys. Rev. Lett. 126, 150501 (2021).
https://doi.org/10.1103/PhysRevLett.126.150501

[10] A. Ketterer, S. Imai, N. Wyderka, and O. Gühne, Phys. Rev. A 106, L010402 (2022).
https://doi.org/10.1103/PhysRevA.106.L010402

[11] Y.-C. Liang, N. Harrigan, S. D. Bartlett, and T. Rudolph, Phys. Rev. Lett. 104, 050401 (2010).
https://doi.org/10.1103/PhysRevLett.104.050401

[12] M. C. Tran, B. Dakić, F. Arnault, W. Laskowski, and T. Paterek, Phys. Rev. A 92, 050301 (2015).
https://doi.org/10.1103/PhysRevA.92.050301

[13] A. Seshadri, M. Ringbauer, J. Spainhour, T. Monz, and S. Becker, Phys. Rev. A 110, 012431 (2024).
https://doi.org/10.1103/PhysRevA.110.012431

[14] P. Cieśliński, S. Imai, J. Dziewior, O. Gühne, L. Knips, W. Laskowski, J. Meinecke, T. Paterek, and T. Vértesi, arXiv:2307.01251 (2023).
https://doi.org/10.48550/arXiv.2307.01251
arXiv:2307.01251

[15] H.-Y. Huang, R. Kueng, and J. Preskill, Nat. Phys. 16, 1050 (2020).
https://doi.org/10.1038/s41567-020-0932-7

[16] A. Acharya, S. Saha, and A. M. Sengupta, Phys. Rev. A 104, 052418 (2021).
https://doi.org/10.1103/PhysRevA.104.052418

[17] H. C. Nguyen, J. L. Bönsel, J. Steinberg, and O. Gühne, Phys. Rev. Lett. 129, 220502 (2022).
https://doi.org/10.1103/PhysRevLett.129.220502

[18] G. I. Struchalin, Y. A. Zagorovskii, E. V. Kovlakov, S. S. Straupe, and S. P. Kulik, PRX Quantum 2, 010307 (2021).
https://doi.org/10.1103/PRXQuantum.2.010307

[19] J. M. Lukens, K. J. H. Law, and R. S. Bennink, npj Quantum Inf. 7, 113 (2021).
https://doi.org/10.1038/s41534-021-00447-6

[20] A. Elben, R. Kueng, H.-Y. Huang, R. van Bijnen, C. Kokail, M. Dalmonte, P. Calabrese, B. Kraus, J. Preskill, P. Zoller, and B. Vermersch, Phys. Rev. Lett. 125, 200501 (2020).
https://doi.org/10.1103/PhysRevLett.125.200501

[21] T. Zhang, J. Sun, X.-X. Fang, X.-M. Zhang, X. Yuan, and H. Lu, Phys. Rev. Lett. 127, 200501 (2021).
https://doi.org/10.1103/PhysRevLett.127.200501

[22] R. Stricker, M. Meth, L. Postler, C. Edmunds, C. Ferrie, R. Blatt, P. Schindler, T. Monz, R. Kueng, and M. Ringbauer, PRX Quantum 3, 040310 (2022).
https://doi.org/10.1103/PRXQuantum.3.040310

[23] D. Zhu, Z. P. Cian, C. Noel, A. Risinger, D. Biswas, L. Egan, Y. Zhu, A. M. Green, C. H. Alderete, N. H. Nguyen, Q. Wang, A. Maksymov, Y. Nam, M. Cetina, N. M. Linke, M. Hafezi, and C. Monroe, Nat. Commun. 13, 6620 (2022).
https://doi.org/10.1038/s41467-022-34279-5

[24] Y. Zhou and Q. Liu, Quantum 7, 1044 (2023).
https://doi.org/10.22331/q-2023-06-29-1044

[25] H.-Y. Huang, R. Kueng, and J. Preskill, Phys. Rev. Lett. 127, 030503 (2021).
https://doi.org/10.1103/PhysRevLett.127.030503

[26] A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, Nat. Rev. Phys. 5, 9 (2023).
https://doi.org/10.1038/s42254-022-00535-2

[27] A. E. Albert, Regression and the Moore-Penrose Pseudoinverse (Academic Press, 1972).

[28] C. Schwemmer, L. Knips, D. Richart, H. Weinfurter, T. Moroder, M. Kleinmann, and O. Gühne, Phys. Rev. Lett. 114, 080403 (2015).
https://doi.org/10.1103/PhysRevLett.114.080403

[29] H. Akaike, IEEE Trans. Auto. Contr. 19, 716 (1974).
https://doi.org/10.1109/TAC.1974.1100705

[30] J. O. S. Yin and S. J. van Enk, Phys. Rev. A 83, 062110 (2011).
https://doi.org/10.1103/PhysRevA.83.062110

[31] S. J. van Enk and R. Blume-Kohout, New J. Phys. 15, 025024 (2013).
https://doi.org/10.1088/1367-2630/15/2/025024

[32] T. L. Scholten and R. Blume-Kohout, New J. Phys. 20, 023050 (2018).
https://doi.org/10.1088/1367-2630/aaa7e2

[33] H. Yano and N. Yamamoto, J. Phys. A: Math. Theor. 56, 405301 (2023).
https://doi.org/10.1088/1751-8121/acf747

[34] M. Belkin, D. Hsu, S. Ma, and S. Mandal, Proc. Natl. Acad. Sci. U.S.A. 116, 15849 (2019).
https://doi.org/10.1073/pnas.1903070116

[35] P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever, J. Stat. Mech. 2021, 124003 (2021a).
https://doi.org/10.1088/1742-5468/ac3a74

[36] Z. Yang, Y. Yu, C. You, J. Steinhardt, and Y. Ma, arXiv:2002.11328 (2020).
https://doi.org/10.48550/arXiv.2002.11328
arXiv:2002.11328

[37] S. P. Singh, A. Lucchi, T. Hofmann, and B. Schölkopf, arXiv:2203.07337 (2022).
https://doi.org/10.48550/arXiv.2203.07337
arXiv:2203.07337

[38] H. Chen, Y. Bu, and G. W. Wornell, arXiv:2306.05583 (2023).
https://doi.org/10.48550/arXiv.2306.05583
arXiv:2306.05583

[39] P. Nakkiran, arXiv:1912.07242 (2019).
https://doi.org/10.48550/arXiv.1912.07242
arXiv:1912.07242

[40] M. Belkin, D. Hsu, and J. Xu, SIAM J. Math. Data Sci. 2, 1167 (2020).
https://doi.org/10.1137/20M1336072

[41] P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler, Proc. Natl. Acad. Sci. U.S.A. 117, 30063 (2020).
https://doi.org/10.1073/pnas.1907378117

[42] R. Sonthalia, X. Li, and B. Gu, arXiv:2305.14689 (2024).
https://doi.org/10.48550/arXiv.2305.14689
arXiv:2305.14689

[43] A. Curth, A. Jeffares, and M. van der Schaar, arXiv:2310.18988 (2023).
https://doi.org/10.48550/arXiv.2310.18988
arXiv:2310.18988

[44] A. W. R. Smith, J. Gray, and M. S. Kim, PRX Quantum 2, 020348 (2021).
https://doi.org/10.1103/PRXQuantum.2.020348

[45] D. Pierangeli and C. Conti, Nat. Commun. 14, 1831 (2023).
https://doi.org/10.1038/s41467-023-37474-0

[46] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Phys. Rev. Lett. 105, 150401 (2010).
https://doi.org/10.1103/PhysRevLett.105.150401

[47] Y.-K. Liu, arXiv:1103.2816 (2011).
https://doi.org/10.48550/arXiv.1103.2816
arXiv:1103.2816

[48] R. Kueng, H. Rauhut, and U. Terstiege, Appl. Comput. Harmon. Anal. 41, 88 (2017).
https://doi.org/10.1016/j.acha.2015.07.007

[49] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, IEEE Trans. Inf. Theory 63, 5628 (2017).
https://doi.org/10.1109/TIT.2017.2719044

[50] M. Guţă, J. Kahn, R. Kueng, and J. A. Tropp, J. Phys. A: Math. Theor. 53, 204001 (2020).
https://doi.org/10.1088/1751-8121/ab8111

[51] D. S. França, F. G. Brandão, and R. Kueng, arXiv:2009.08216 (2021).
https://doi.org/10.48550/arXiv.2009.08216
arXiv:2009.08216

[52] F. Verstraete, J. J. Garcia-Ripoll, and J. I. Cirac, Phys. Rev. Lett. 93, 207204 (2004).
https://doi.org/10.1103/PhysRevLett.93.207204

[53] B. Pirvu, V. Murg, J. I. Cirac, and F. Verstraete, New J. Phys. 12, 025012 (2010).
https://doi.org/10.1088/1367-2630/12/2/025012

[54] M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Nat. Commun. 1, 149 (2010).
https://doi.org/10.1038/ncomms1147

[55] T. Baumgratz, D. Gross, M. Cramer, and M. B. Plenio, Phys. Rev. Lett. 111, 020401 (2013).
https://doi.org/10.1103/PhysRevLett.111.020401

[56] A. Lidiak, C. Jameson, Z. Qin, G. Tang, M. B. Wakin, Z. Zhu, and Z. Gong, arXiv:2207.06397 (2022).
https://doi.org/10.48550/arXiv.2207.06397
arXiv:2207.06397

[57] K. Noh, L. Jiang, and B. Fefferman, Quantum 4, 318 (2020).
https://doi.org/10.22331/q-2020-09-11-318

[58] J. Wang, Z.-Y. Han, S.-B. Wang, Z. Li, L.-Z. Mu, H. Fan, and L. Wang, Phys. Rev. A 101, 032321 (2020).
https://doi.org/10.1103/PhysRevA.101.032321

[59] J. G. Jarkovskỳ, A. Molnár, N. Schuch, and J. I. Cirac, PRX Quantum 1, 010304 (2020).
https://doi.org/10.1103/PRXQuantum.1.010304

[60] Z. Qin, C. Jameson, Z. Gong, M. B. Wakin, and Z. Zhu, arXiv:2306.09432 (2024).
https://doi.org/10.48550/arXiv.2306.09432
arXiv:2306.09432

[61] T. Opatrnỳ, D.-G. Welsch, and W. Vogel, Phys. Rev. A 56, 1788 (1997).
https://doi.org/10.1103/PhysRevA.56.1788

[62] B. Mu, H. Qi, I. R. Petersen, and G. Shi, Automatica 114, 108837 (2020).
https://doi.org/10.1016/j.automatica.2020.108837

[63] P. Nakkiran, P. Venkat, S. Kakade, and T. Ma, arXiv:2003.01897 (2021b).
https://doi.org/10.48550/arXiv.2003.01897
arXiv:2003.01897

[64] A. Zhao, N. C. Rubin, and A. Miyake, Phys. Rev. Lett. 127, 110504 (2021).
https://doi.org/10.1103/PhysRevLett.127.110504

[65] H.-Y. Hu, S. Choi, and Y.-Z. You, Phys. Rev. Research 5, 023027 (2023).
https://doi.org/10.1103/PhysRevResearch.5.023027

[66] K. Bu, D. E. Koh, R. J. Garcia, and A. Jaffe, npj Quantum Inf. 10, 6 (2024).
https://doi.org/10.1038/s41534-023-00801-w

[67] J. A. Smolin, J. M. Gambetta, and G. Smith, Phys. Rev. Lett. 108, 070502 (2012).
https://doi.org/10.1103/PhysRevLett.108.070502

[68] Other approaches to obtain a meaningful likelihood from a nonphysical estimate are possible, such as removing terms with negative probabilities. However, we have found this approach to lead to the same general conclusions and so focus on physical projection only in the main text.

[69] K. Życzkowski and H.-J. Sommers, Phys. Rev. A 71, 032313 (2005).
https://doi.org/10.1103/PhysRevA.71.032313

[70] L. Mandel and E. Wolf, Optical Coherence and Quantum Optics (Cambridge University Press, Cambridge, UK, 1995).
https://doi.org/10.1017/CBO9781139644105

[71] Y. Shih, Rep. Prog. Phys. 66, 1009 (2003).
https://doi.org/10.1088/0034-4885/66/6/203

[72] J. Helsen and M. Walter, Phys. Rev. Lett. 131, 240602 (2023).
https://doi.org/10.1103/PhysRevLett.131.240602

[73] Z. Hou, H.-S. Zhong, Y. Tian, D. Dong, B. Qi, L. Li, Y. Wang, F. Nori, G.-Y. Xiang, C.-F. Li, and G.-C. Guo, New J. Phys. 18, 083036 (2016).
https://doi.org/10.1088/1367-2630/18/8/083036

Cited by

[1] Zhen Qin, Joseph M. Lukens, Brian T. Kirby, and Zhihui Zhu, "Enhancing quantum state reconstruction with structured classical shadows", npj Quantum Information 11 1, 147 (2025).

[2] Zhihui Zhu, Joseph M. Lukens, and Brian T. Kirby, CLEO 2025 FF120_6 (2025) ISBN:978-1-957171-50-0.

[3] Yixian Qiu, Lirandë Pira, and Patrick Rebentrost, "Quantum learning with tunable loss functions", npj Quantum Information 12 1, 131 (2026).

[4] Zhenyu Cai, Adrian Chapman, Hamza Jnane, and Bálint Koczor, "Biased estimator channels for classical shadows", Physical Review A 111 3, L030402 (2025).

[5] Zhen Qin, Casey Jameson, Zhexuan Gong, Michael B. Wakin, and Zhihui Zhu, "Optimal Allocation of Pauli Measurements for Low-Rank Quantum State Tomography", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[6] Jacob Bringewatt, Henry Froland, Andreas Elben, and Niklas Mueller, "Classical shadows for sample-efficient measurements of gauge-invariant observables", Quantum 10, 2127 (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-09-09 01:05:13) and SAO/NASA ADS (last updated successfully 2026-09-09 01:05:14). 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.