Agnostic Tomography of Stabilizer Product States

Sabee Grewal; Vishnu Iyer; William Kretschmer; Daniel Liang

doi:10.22331/q-2026-03-13-2027

Agnostic Tomography of Stabilizer Product States

Sabee Grewal¹, Vishnu Iyer¹, William Kretschmer^1,2, and Daniel Liang^3,4

¹University of Texas at Austin, Austin, TX 78712, USA
²Simons Institute for the Theory of Computing, University of California, Berkeley, Berkeley, CA 94720, USA
³Portland State University, Portland, OR 97201, USA
⁴Rice University, Houston, TX 77005, USA

Published:	2026-03-13, volume 10, page 2027
Editor:	Tom Gur
Eprint:	arXiv:2404.03813v5
Doi:	https://doi.org/10.22331/q-2026-03-13-2027
Citation:	Quantum 10, 2027 (2026).

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

Abstract

We define a quantum learning task called $\textit{agnostic tomography}$, where given copies of an arbitrary state $\rho$ and a class of quantum states $\mathcal{C}$, the goal is to output a succinct description of a state that approximates $\rho$ at least as well as any state in $\mathcal{C}$ (up to some small error $\varepsilon$). This task generalizes ordinary quantum tomography of states in $\mathcal{C}$ and is more challenging because the learning algorithm must be robust to perturbations of $\rho$.
We give an efficient agnostic tomography algorithm for the class $\mathcal{C}$ of $n$-qubit stabilizer product states. Assuming $\rho$ has fidelity at least $\tau$ with a stabilizer product state, the algorithm runs in time $n^{O(\log(2/\tau))} / \varepsilon^2$, which is $\mathsf{poly}(n/\varepsilon)$ for any constant $\tau$.

► BibTeX data

@article{Grewal2026agnostictomography,
  doi = {10.22331/q-2026-03-13-2027},
  url = {https://doi.org/10.22331/q-2026-03-13-2027},
  title = {Agnostic {T}omography of {S}tabilizer {P}roduct {S}tates},
  author = {Grewal, Sabee and Iyer, Vishnu and Kretschmer, William and Liang, Daniel},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2027},
  month = mar,
  year = {2026}
}

► References

[1] Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM Journal on Computing 26, 1484–1509 (1997).
https://doi.org/10.1137/S0097539795293172

[2] Fernando G. S. L. Brandão and Aram W. Harrow. ``Product-state approximations to quantum states''. Communications in Mathematical Physics 342, 47–80 (2016).
https://doi.org/10.1007/s00220-016-2575-1

[3] John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, and Justin Yirka. ``Complexity Classification of Product State Problems for Local Hamiltonians''. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:32. Dagstuhl, Germany (2025). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2025.63

[4] David Perez-Garcia, Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac. ``Matrix product state representations''. Quantum Info. Comput. 7, 401–430 (2007).
https://doi.org/10.26421/QIC7.5-6-1

[5] Daniel Gottesman. ``The Heisenberg Representation of Quantum Computers'' (1998). arXiv:quant-ph/9807006.
arXiv:quant-ph/9807006

[6] Scott Aaronson and Daniel Gottesman. ``Improved Simulation of Stabilizer Circuits''. Physical Review A 70 (2004).
https://doi.org/10.1103/physreva.70.052328

[7] Frank Verstraete, Valentin Murg, and J. Ignacio Cirac. ``Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems''. Advances in Physics 57, 143–224 (2008).
https://doi.org/10.1080/14789940801912366

[8] Jiace Sun, Lixue Cheng, and Shi-Xin Zhang. ``Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications''. Quantum 9, 1782 (2025).
https://doi.org/10.22331/q-2025-06-24-1782

[9] Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. ``Efficient quantum state tomography''. Nature Communications 1, 1–7 (2010).
https://doi.org/10.1038/ncomms1147

[10] Ashley Montanaro. ``Learning stabilizer states by Bell sampling'' (2017). arXiv:1707.04012.
arXiv:1707.04012

[11] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates''. Quantum 9, 1907 (2025).
https://doi.org/10.22331/q-2025-11-06-1907

[12] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Learning t-doped stabilizer states''. Quantum 8, 1361 (2024).
https://doi.org/10.22331/q-2024-05-27-1361

[13] Dominik Hangleiter and Michael J. Gullans. ``Bell sampling from quantum circuits''. Phys. Rev. Lett. 133, 020601 (2024).
https://doi.org/10.1103/PhysRevLett.133.020601

[14] Scott Aaronson and Sabee Grewal. ``Efficient Tomography of Non-Interacting-Fermion States''. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:18. (2023).
https://doi.org/10.4230/LIPIcs.TQC.2023.12

[15] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. ``Optimal Algorithms for Learning Quantum Phase States''. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:24. (2023).
https://doi.org/10.4230/LIPIcs.TQC.2023.3

[16] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. ``Learning shallow quantum circuits''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1343–1351. STOC 2024New York, NY, USA (2024). Association for Computing Machinery.
https://doi.org/10.1145/3618260.3649722

[17] Konrad Banaszek, Marcus Cramer, and David Gross. ``Focus on quantum tomography''. New Journal of Physics 15, 125020 (2013).
https://doi.org/10.1088/1367-2630/15/12/125020

[18] Ryan O'Donnell and John Wright. ``Efficient quantum tomography II''. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Page 962–974. STOC 2017New York, NY, USA (2017). Association for Computing Machinery.
https://doi.org/10.1145/3055399.3055454

[19] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Improved stabilizer estimation via Bell difference sampling''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1352–1363. STOC 2024New York, NY, USA (2024). Association for Computing Machinery.
https://doi.org/10.1145/3618260.3649738

[20] Costin Bădescu and Ryan O'Donnell. ``Improved Quantum Data Analysis''. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Page 1398–1411. STOC 2021. Association for Computing Machinery (2021).
https://doi.org/10.1145/3406325.3451109

[21] Anurag Anshu and Srinivasan Arunachalam. ``A survey on the complexity of learning quantum states''. Nature Reviews Physics 6, 59–69 (2024).
https://doi.org/10.1038/s42254-023-00662-4

[22] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

[23] Yingkai Ouyang and Marco Tomamichel. ``Learning quantum graph states with product measurements''. In 2022 IEEE International Symposium on Information Theory (ISIT). Pages 2963–2968. (2022).
https://doi.org/10.1109/ISIT50566.2022.9834440

[24] Aravind Gollakota and Daniel Liang. ``On the Hardness of PAC-learning Stabilizer States with Noise''. Quantum 6, 640 (2022).
https://doi.org/10.22331/q-2022-02-02-640

[25] Alexander Poremba, Yihui Quek, and Peter Shor. ``The Learning Stabilizers with Noise Problem''. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1–108:19. Dagstuhl, Germany (2026). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2026.108

[26] Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan. ``Average-Case Complexity of Quantum Stabilizer Decoding'' (2025). arXiv:2509.20697.
arXiv:2509.20697

[27] Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, and Ewin Tang. ``Learning the closest product state''. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Page 1212–1221. STOC '25New York, NY, USA (2025). Association for Computing Machinery.
https://doi.org/10.1145/3717823.3718207

[28] Scott Aaronson. ``Shadow Tomography of Quantum States''. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Page 325–338. STOC 2018. Association for Computing Machinery (2018).
https://doi.org/10.1145/3188745.3188802

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

[30] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. ``High-temperature Gibbs states are unentangled and efficiently preparable''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1027–1036. (2024).
https://doi.org/10.1109/FOCS61266.2024.00068

[31] Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang. ``Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation''. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Page 429–438. STOC '25New York, NY, USA (2025). Association for Computing Machinery.
https://doi.org/10.1145/3717823.3718191

[32] Alvan Arulandu, Ilias Diakonikolas, Daniel Kane, and Jerry Li. ``Agnostic Product Mixed State Tomography via Robust Statistics'' (2025). arXiv:2510.08472.
arXiv:2510.08472

[33] Chirag Wadhwa, Laura Lewis, Elham Kashefi, and Mina Doosti. ``Agnostic process tomography''. PRX Quantum 6, 040371 (2025).
https://doi.org/10.1103/q2nb-zg9m

[34] Jop Briët and Davi Castro-Silva. ``A near-optimal quadratic Goldreich-Levin algorithm'' (2025). arXiv:2505.13134.
arXiv:2505.13134

[35] Oded Goldreich and Leonid A. Levin. ``A hard-core predicate for all one-way functions''. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing. Page 25–32. STOC '89New York, NY, USA (1989). Association for Computing Machinery.
https://doi.org/10.1145/73007.73010

[36] Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, and Tom Gur. ``Algorithmic polynomial Freiman-Ruzsa theorems'' (2025). arXiv:2509.02338.
arXiv:2509.02338

[37] Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, and Michael de Oliveira. ``Learning depth-3 circuits via quantum agnostic boosting'' (2025). arXiv:2509.14461.
arXiv:2509.14461

[38] Clément L. Canonne. ``A short note on learning discrete distributions'' (2020). arXiv:2002.11457.
arXiv:2002.11457

[39] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. ``Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator''. The Annals of Mathematical Statistics 27, 642–669 (1956).
https://doi.org/10.1214/aoms/1177728174

[40] David Gross, Sepehr Nezami, and Michael Walter. ``Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations''. Communications in Mathematical Physics 385, 1325–1393 (2021).
https://doi.org/10.1007/s00220-021-04118-7

[41] Koenraad M R Audenaert and Martin B Plenio. ``Entanglement on mixed stabilizer states: normal forms and reduction procedures''. New Journal of Physics 7, 170 (2005).
https://doi.org/10.1088/1367-2630/7/1/170

Cited by

[1] Chirag Wadhwa, Laura Lewis, Elham Kashefi, and Mina Doosti, "Agnostic Process Tomography", PRX Quantum 6 4, 040371 (2025).

[2] Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang, "Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation", arXiv:2408.06967, (2024).

[3] Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, and Ewin Tang, "Learning the closest product state", arXiv:2411.04283, (2024).

[4] Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, and Michael de Oliveira, "Learning depth-3 circuits via quantum agnostic boosting", arXiv:2509.14461, (2025).

[5] Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, and Miklos Santha, "Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits", arXiv:2405.06357, (2024).

[6] Sitan Chen, Weiyuan Gong, Jonas Haferkamp, and Yihui Quek, "Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood", arXiv:2505.22743, (2025).

[7] Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, and Yuhan Liu, "Adversarially robust quantum state learning and testing", arXiv:2508.13959, (2025).

[8] Vishnu Iyer, "Mildly-Interacting Fermionic Unitaries are Efficiently Learnable", arXiv:2504.11318, (2025).

[9] Marco Fanizza, Vishnu Iyer, Junseo Lee, Antonio A. Mele, and Francesco A. Mele, "Efficient learning of bosonic Gaussian unitaries", arXiv:2510.05531, (2025).

[10] Srinivasan Arunachalam and Arkopal Dutt, "Learning stabilizer structure of quantum states", arXiv:2510.05890, (2025).

[11] Timothy Skaras and Paul Ginsparg, "Process tomography for Clifford unitaries", Physical Review A 113 1, 012414 (2026).

[12] Sabee Grewal and Daniel Liang, "Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity", arXiv:2510.00168, (2025).

[13] Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, and Miklos Santha, "Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more", arXiv:2510.06848, (2025).

[14] Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Chia-Ying Lin, Yuhan Liu, Aadil Oufkir, and Yu-Ching Shen, "Shadow Tomography Against Adversaries", arXiv:2512.05451, (2025).

[15] Alvan Arulandu, Ilias Diakonikolas, Daniel Kane, and Jerry Li, "Agnostic Product Mixed State Tomography via Robust Statistics", arXiv:2510.08472, (2025).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-19 14:50: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 2026-08-19 14:50:04).

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.