{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T01:52:21Z","timestamp":1781833941463,"version":"3.54.5"},"reference-count":28,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["FET-2243659"],"award-info":[{"award-number":["FET-2243659"]}]},{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE- SC0024301"],"award-info":[{"award-number":["DE- SC0024301"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"crossref","award":["Google Scholar Award"],"award-info":[{"award-number":["Google Scholar Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science and Technology Council (NSTC) in Taiwan","award":["11-2628-E-A49-024-MY2"],"award-info":[{"award-number":["11-2628-E-A49-024-MY2"]}]},{"name":"National Science and Technology Council (NSTC) in Taiwan","award":["112-2119- M-A49-007"],"award-info":[{"award-number":["112-2119- M-A49-007"]}]},{"name":"National Science and Technology Council (NSTC) in Taiwan","award":["112-2119-M-001-007"],"award-info":[{"award-number":["112-2119-M-001-007"]}]},{"name":"National Science and Technology Council (NSTC) in Taiwan","award":["111-2119-M-001-004"],"award-info":[{"award-number":["111-2119-M-001-004"]}]},{"name":"National Science and Technology Council (NSTC) in Taiwan","award":["110- 2222-E-007-002-MY3"],"award-info":[{"award-number":["110- 2222-E-007-002-MY3"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math> 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<\/mml:mi><\/mml:math> 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<\/mml:mi>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math> non-Clifford gates, filling a gap between the previous positive and negative results.<\/jats:p>","DOI":"10.22331\/q-2024-02-12-1250","type":"journal-article","created":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T15:24:55Z","timestamp":1707751495000},"page":"1250","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":14,"title":["Efficient learning of t<\/mml:mi><\/mml:math>-doped stabilizer states with single-copy measurements"],"prefix":"10.22331","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4138-7956","authenticated-orcid":false,"given":"Nai-Hui","family":"Chia","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rice University, TX 77005-1892, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1970-8167","authenticated-orcid":false,"given":"Ching-Yi","family":"Lai","sequence":"additional","affiliation":[{"name":"Institute of Communications Engineering, National Yang Ming Chiao Tung University, Hsinchu 300093, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5126-0174","authenticated-orcid":false,"given":"Han-Hsuan","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National Tsing Hua University, Hsinchu 30013, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2024,2,12]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Z. Hradil. ``Quantum-state estimation''. Physical Review A 55, R1561\u2013R1564 (1997).","DOI":"10.1103\/physreva.55.r1561"},{"key":"1","doi-asserted-by":"publisher","unstructured":"G. Mauro D'Ariano, Matteo G.A. Paris, and Massimiliano F. Sacchi. ``Quantum tomography''. In Advances in Imaging and Electron Physics. Pages 205\u2013308. Elsevier (2003).","DOI":"10.1016\/s1076-5670(03)80065-4"},{"key":"2","doi-asserted-by":"publisher","unstructured":"K Banaszek, M Cramer, and D Gross. ``Focus on quantum tomography''. New Journal of Physics 15, 125020 (2013).","DOI":"10.1088\/1367-2630\/15\/12\/125020"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. ``Sample-optimal tomography of quantum states''. IEEE Transactions on Information TheoryPages 1\u20131 (2017).","DOI":"10.1109\/tit.2017.2719044"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Ryan O'Donnell and John Wright. ``Efficient quantum tomography''. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. Pages 899\u2013912. (2016).","DOI":"10.1145\/2897518.2897544"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u20133:22. (2021).","DOI":"10.4230\/LIPIcs.TQC.2021.3"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"7","unstructured":"Scott Aaronson and Daniel Gottesman. ``Identifying stabilizer states''. Talk at PIRSA, available on video (2008). url: http:\/\/pirsa.org\/08080052."},{"key":"8","unstructured":"Ashley Montanaro. ``Learning stabilizer states by bell sampling''. (2017). arXiv:1707.04012."},{"key":"9","unstructured":"D. Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. Pasadena, CA (1997)."},{"key":"10","doi-asserted-by":"publisher","unstructured":"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\u2013107 (2000).","DOI":"10.1016\/S0020-0190(00)00084-3"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Ching-Yi Lai and Hao-Chung Cheng. ``Learning quantum circuits of some t gates''. IEEE Transactions on Information Theory 68, 3951\u20133964 (2022).","DOI":"10.1109\/TIT.2022.3151760"},{"key":"12","unstructured":"Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. ``Optimal algorithms for learning quantum phase states''. (2023). arXiv:2208.07851."},{"key":"13","unstructured":"Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Efficient learning of quantum states prepared with few non-clifford gates''. (2023). arXiv:2305.13409."},{"key":"14","unstructured":"Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Learning t-doped stabilizer states''. (2023). arXiv:2305.15398."},{"key":"15","unstructured":"Dominik Hangleiter and Michael J. Gullans. ``Bell sampling from quantum circuits''. (2023). arXiv:2306.00083."},{"key":"16","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.130.240602"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Richard Cleve and Daniel Gottesman. ``Efficient computations of encodings for quantum error correction''. Phys. Rev. A 56, 76\u201382 (1997).","DOI":"10.1103\/PhysRevA.56.76"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Michel A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. Cambridge, UK (2000).","DOI":"10.1017\/CBO9780511976667"},{"key":"19","unstructured":"Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Improved stabilizer estimation via bell difference sampling'' (2023). arXiv:2304.13915."},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. Winter. ``Coding theorem and strong converse for quantum channels''. IEEE Transactions on Information Theory 45, 2481\u20132485 (1999).","DOI":"10.1109\/18.796385"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and Dmitri Maslov. ``Hadamard-free circuits expose the structure of the clifford group''. IEEE Transactions on Information Theory 67, 4546\u20134563 (2021).","DOI":"10.1109\/TIT.2021.3081415"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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\u201359. (2021).","DOI":"10.1109\/QCE52317.2021.00021"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Daniel Stilck Fran\u00e7a, Fernando G.S L. Brand\u00e3o, 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\u20137:13. (2021).","DOI":"10.4230\/LIPIcs.TQC.2021.7"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. Mohseni, A. T. Rezakhani, and D. A. Lidar. ``Quantum-process tomography: Resource analysis of different strategies''. Physical Review A 77 (2008).","DOI":"10.1103\/physreva.77.032322"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Man-Duen Choi. ``Completely positive linear maps on complex matrices''. Linear Algebra and its Applications 10, 285\u2013290 (1975).","DOI":"10.1016\/0024-3795(75)90075-0"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A. Jamio\u0142kowski. ``Linear transformations which preserve trace and positive semidefiniteness of operators''. Reports on Mathematical Physics 3, 275\u2013278 (1972).","DOI":"10.1016\/0034-4877(72)90011-0"},{"key":"27","unstructured":"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."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-02-12-1250\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T15:25:13Z","timestamp":1707751513000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-02-12-1250\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,12]]},"references-count":28,"URL":"https:\/\/doi.org\/10.22331\/q-2024-02-12-1250","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,12]]},"article-number":"1250"}}