Efficient learning of $t$-doped stabilizer states with single-copy measurements
1Department of Computer Science, Rice University, TX 77005-1892, United States
2Institute of Communications Engineering, National Yang Ming Chiao Tung University, Hsinchu 300093, Taiwan
3Department of Computer Science, National Tsing Hua University, Hsinchu 30013, Taiwan
| Published: | 2024-02-12, volume 8, page 1250 |
| Eprint: | arXiv:2308.07014v3 |
| Doi: | https://doi.org/10.22331/q-2024-02-12-1250 |
| Citation: | Quantum 8, 1250 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
One of the primary objectives in the field of quantum state learning is to develop algorithms that are time-efficient for learning states generated from quantum circuits. Earlier investigations have demonstrated time-efficient algorithms for states generated from Clifford circuits with at most $\log(n)$ non-Clifford gates. However, these algorithms necessitate multi-copy measurements, posing implementation challenges in the near term due to the requisite quantum memory. On the contrary, using solely single-qubit measurements in the computational basis is insufficient in learning even the output distribution of a Clifford circuit with one additional $T$ gate under reasonable post-quantum cryptographic assumptions. In this work, we introduce an efficient quantum algorithm that employs only nonadaptive single-copy measurement to learn states produced by Clifford circuits with a maximum of $O(\log n)$ non-Clifford gates, filling a gap between the previous positive and negative results.
Popular summary
► BibTeX data
► References
[1] Z. Hradil. ``Quantum-state estimation''. Physical Review A 55, R1561–R1564 (1997).
https://doi.org/10.1103/physreva.55.r1561
[2] G. Mauro D'Ariano, Matteo G.A. Paris, and Massimiliano F. Sacchi. ``Quantum tomography''. In Advances in Imaging and Electron Physics. Pages 205–308. Elsevier (2003).
https://doi.org/10.1016/s1076-5670(03)80065-4
[3] K Banaszek, M Cramer, and D Gross. ``Focus on quantum tomography''. New Journal of Physics 15, 125020 (2013).
https://doi.org/10.1088/1367-2630/15/12/125020
[4] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. ``Sample-optimal tomography of quantum states''. IEEE Transactions on Information TheoryPages 1–1 (2017).
https://doi.org/10.1109/tit.2017.2719044
[5] Ryan O'Donnell and John Wright. ``Efficient quantum tomography''. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. Pages 899–912. (2016).
https://doi.org/10.1145/2897518.2897544
[6] Kai-Min Chung and Han-Hsuan Lin. ``Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem''. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:22. (2021).
https://doi.org/10.4230/LIPIcs.TQC.2021.3
[7] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328
[8] Scott Aaronson and Daniel Gottesman. ``Identifying stabilizer states''. Talk at PIRSA, available on video (2008). url: http://pirsa.org/08080052.
http://pirsa.org/08080052
[9] Ashley Montanaro. ``Learning stabilizer states by bell sampling''. (2017). arXiv:1707.04012.
arXiv:1707.04012
[10] D. Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. Pasadena, CA (1997).
[11] P.Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan. ``A new universal and fault-tolerant quantum basis''. Information Processing Letters 75, 101–107 (2000).
https://doi.org/10.1016/S0020-0190(00)00084-3
[12] Ching-Yi Lai and Hao-Chung Cheng. ``Learning quantum circuits of some t gates''. IEEE Transactions on Information Theory 68, 3951–3964 (2022).
https://doi.org/10.1109/TIT.2022.3151760
[13] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. ``Optimal algorithms for learning quantum phase states''. (2023). arXiv:2208.07851.
arXiv:2208.07851
[14] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Efficient learning of quantum states prepared with few non-clifford gates''. (2023). arXiv:2305.13409.
arXiv:2305.13409
[15] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Learning t-doped stabilizer states''. (2023). arXiv:2305.15398.
arXiv:2305.15398
[16] Dominik Hangleiter and Michael J. Gullans. ``Bell sampling from quantum circuits''. (2023). arXiv:2306.00083.
arXiv:2306.00083
[17] M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, and R. Sweke. ``One $t$ gate makes distribution learning hard''. Phys. Rev. Lett. 130, 240602 (2023).
https://doi.org/10.1103/PhysRevLett.130.240602
[18] Richard Cleve and Daniel Gottesman. ``Efficient computations of encodings for quantum error correction''. Phys. Rev. A 56, 76–82 (1997).
https://doi.org/10.1103/PhysRevA.56.76
[19] Michel A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. Cambridge, UK (2000).
https://doi.org/10.1017/CBO9780511976667
[20] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Improved stabilizer estimation via bell difference sampling'' (2023). arXiv:2304.13915.
arXiv:2304.13915
[21] A. Winter. ``Coding theorem and strong converse for quantum channels''. IEEE Transactions on Information Theory 45, 2481–2485 (1999).
https://doi.org/10.1109/18.796385
[22] Sergey Bravyi and Dmitri Maslov. ``Hadamard-free circuits expose the structure of the clifford group''. IEEE Transactions on Information Theory 67, 4546–4563 (2021).
https://doi.org/10.1109/TIT.2021.3081415
[23] Ewout Van Den Berg. ``A simple method for sampling random clifford operators''. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 54–59. (2021).
https://doi.org/10.1109/QCE52317.2021.00021
[24] Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng. ``Fast and Robust Quantum State Tomography from Few Basis Measurements''. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:13. (2021).
https://doi.org/10.4230/LIPIcs.TQC.2021.7
[25] M. Mohseni, A. T. Rezakhani, and D. A. Lidar. ``Quantum-process tomography: Resource analysis of different strategies''. Physical Review A 77 (2008).
https://doi.org/10.1103/physreva.77.032322
[26] Man-Duen Choi. ``Completely positive linear maps on complex matrices''. Linear Algebra and its Applications 10, 285–290 (1975).
https://doi.org/10.1016/0024-3795(75)90075-0
[27] A. Jamiołkowski. ``Linear transformations which preserve trace and positive semidefiniteness of operators''. Reports on Mathematical Physics 3, 275–278 (1972).
https://doi.org/10.1016/0034-4877(72)90011-0
[28] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Efficient learning of quantum states prepared with few non-clifford gates ii: Single-copy measurements''. (2023). arXiv:2308.07175.
arXiv:2308.07175
Cited by
[1] Marcel Hinsche and Jonas Helsen, Proceedings of the 57th Annual ACM Symposium on Theory of Computing 439 (2025) ISBN:9798400715105.
[2] Liang-Liang Sun, Kishor Bharti, Xiang Zhou, Leong-Chuan Kwek, Jingyun Fan, and Sixia Yu, "Uncertainty-disturbance relations and applications", Physical Review Research 8 1, 013287 (2026).
[3] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Lower bounds on the non-Clifford cost of pseudoentanglement", Physical Review A 113 1, 012434 (2026).
[4] Beatrice Magni, Markus Heinrich, Lorenzo Leone, and Xhek Turkeshi, "Anticoncentration and state design of doped real Clifford circuits and tensor networks", Physical Review A 113 6, 062446 (2026).
[5] Yanting Teng, Rhine Samajdar, Katherine Van Kirk, Frederik Wilde, Subir Sachdev, Jens Eisert, Ryan Sweke, and Khadijeh Najafi, "Learning Topological States from Randomized Measurements Using Variational Tensor-Network Tomography", PRX Quantum 6 4, 040303 (2025).
[6] Francesco A. Mele, Antonio A. Mele, Lennart Bittel, Jens Eisert, Vittorio Giovannetti, Ludovico Lami, Lorenzo Leone, and Salvatore F. E. Oliviero, "Learning quantum states of continuous-variable systems", Nature Physics 21 12, 2002 (2025).
[7] Andi Gu, Salvatore F. E. Oliviero, and Lorenzo Leone, "Doped stabilizer states in many-body physics and where to find them", Physical Review A 110 6, 062427 (2024).
[8] Beatrice Magni, Alexios Christopoulos, Andrea De Luca, and Xhek Turkeshi, "Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudomagic States", Physical Review X 15 3, 031071 (2025).
[9] M. Hinsche, M. Ioannou, S. Jerbi, L. Leone, J. Eisert, and J. Carrasco, "Efficient Distributed Inner-Product Estimation via Pauli Sampling", PRX Quantum 6 3, 030354 (2025).
[10] Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang, Proceedings of the 57th Annual ACM Symposium on Theory of Computing 429 (2025) ISBN:9798400715105.
[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).
[12] Marcel Hinsche, Jens Eisert, and Jose Carrasco, "Abelian State Hidden Subgroup Problem: Learning Stabilizer Groups and Beyond", PRX Quantum 7 2, 020337 (2026).
[13] Janek Denzler, Santiago Varona, Tommaso Guaita, and Jose Carrasco, "Highly-entangled, highly-doped states that are efficiently cross-device verifiable", Physical Review Research 7 2, 023320 (2025).
[14] Andi Gu, Salvatore F.E. Oliviero, and Lorenzo Leone, "Magic-Induced Computational Separation in Entanglement Theory", PRX Quantum 6 2, 020324 (2025).
[15] Nai-Hui Chia, Daniel Liang, and Fang Song, "Quantum State Learning Implies Circuit Lower Bounds", arXiv:2405.10242, (2024).
[16] Yuya O. Nakagawa and Yasunori Lee, "Application of resource theory based on free Clifford+kT computation to early fault-tolerant quantum computing", arXiv:2508.14546, (2025).
[17] Aria Christensen and Andrew Zhao, "Learning fermionic linear optics with Heisenberg scaling and physical operations", arXiv:2602.05058, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 18:50:18) and SAO/NASA ADS (last updated successfully 2026-08-09 18:50:20). 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.