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

Nai-Hui Chia1, Ching-Yi Lai2, and Han-Hsuan Lin3

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

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


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.

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

► References

[1] Z. Hradil. ``Quantum-state estimation''. Physical Review A 55, R1561–R1564 (1997).

[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).

[3] K Banaszek, M Cramer, and D Gross. ``Focus on quantum tomography''. New Journal of Physics 15, 125020 (2013).

[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).

[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).

[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).

[7] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).

[8] Scott Aaronson and Daniel Gottesman. ``Identifying stabilizer states''. Talk at PIRSA, available on video (2008). url: http:/​/​pirsa.org/​08080052.

[9] Ashley Montanaro. ``Learning stabilizer states by bell sampling''. (2017). 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).

[12] Ching-Yi Lai and Hao-Chung Cheng. ``Learning quantum circuits of some t gates''. IEEE Transactions on Information Theory 68, 3951–3964 (2022).

[13] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. ``Optimal algorithms for learning quantum phase states''. (2023). 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.

[15] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Learning t-doped stabilizer states''. (2023). arXiv:2305.15398.

[16] Dominik Hangleiter and Michael J. Gullans. ``Bell sampling from quantum circuits''. (2023). 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).

[18] Richard Cleve and Daniel Gottesman. ``Efficient computations of encodings for quantum error correction''. Phys. Rev. A 56, 76–82 (1997).

[19] Michel A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. Cambridge, UK (2000).

[20] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Improved stabilizer estimation via bell difference sampling'' (2023). arXiv:2304.13915.

[21] A. Winter. ``Coding theorem and strong converse for quantum channels''. IEEE Transactions on Information Theory 45, 2481–2485 (1999).

[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).

[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).

[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).

[25] M. Mohseni, A. T. Rezakhani, and D. A. Lidar. ``Quantum-process tomography: Resource analysis of different strategies''. Physical Review A 77 (2008).

[26] Man-Duen Choi. ``Completely positive linear maps on complex matrices''. Linear Algebra and its Applications 10, 285–290 (1975).

[27] A. Jamiołkowski. ``Linear transformations which preserve trace and positive semidefiniteness of operators''. Reports on Mathematical Physics 3, 275–278 (1972).

[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.

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-02-26 16:03:04). On SAO/NASA ADS no data on citing works was found (last attempt 2024-02-26 16:03:05).