Efficient Learning Of $t$-doped Stabilizer States With Single-copy Measurements

Nai-Hui Chia¹, Ching-Yi Lai², and Han-Hsuan Lin³

¹Department of Computer Science, Rice University, TX 77005-1892, United States
²Institute of Communications Engineering, National Yang Ming Chiao Tung University, Hsinchu 300093, Taiwan
³Department of Computer Science, National Tsing Hua University, Hsinchu 30013, Taiwan

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

In the realm of quantum state learning, researchers aim to create time-efficient algorithms for understanding states generated by quantum circuits. Previous studies achieved efficiency for states from Clifford circuits with limited non-Clifford gates, but these required challenging multi-copy measurements, hindering near-term implementation. This work presents a groundbreaking quantum algorithm that, with just single-copy measurements, efficiently learns states from Clifford circuits featuring up to $O(log(n))$ non-Clifford gates. This bridges the gap between earlier positive and negative results, offering a promising solution with practical implications for quantum computing.

► BibTeX data

@article{Chia2024efficientlearningof, doi = {10.22331/q-2024-02-12-1250}, url = {https://doi.org/10.22331/q-2024-02-12-1250}, title = {Efficient learning of {$t$}-doped stabilizer states with single-copy measurements}, author = {Chia, Nai-Hui and Lai, Ching-Yi and Lin, Han-Hsuan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1250}, month = feb, year = {2024} }

► 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

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.

Generative Data Intelligence

Efficient learning of $t$-doped stabilizer states with single-copy measurements

Abstract

Popular summary

► BibTeX data

► References

Cited by

Drake Threatened With Lawsuit Over Tupac AI Vocals

Shiba Inu Leads in Robinhood’s Crypto Performance

Latest Intelligence

DOJ Disputes Roman Storm’s Characterization of Tornado Cash Operations in New Filing

Best Players Available for Day 3 of the 2024 NFL Draft

Top 5 Crypto Presales: BDAG Leads the Pack with 30,000x ROI Potential

Forbes Unveils 20 Crypto ‘Zombies,’ Declares Ripple And XRP Among The Undead

Consob, Italy’s Watchdog, Bans Additional Forex And Cryptocurrency Trading Websites – CryptoInfoNet

Fed’s Inflation Gauge Heats Up, Rate Cuts on Hold as Bitcoin and Stocks Slide

Chat with us