Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$

Daniel Liang

Department of Computer Science, University of Texas at Austin

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


Given a dataset of input states, measurements, and probabilities, is it possible to efficiently predict the measurement probabilities associated with a quantum circuit? Recent work of Caro and Datta [19] studied the problem of PAC learning quantum circuits in an information theoretic sense, leaving open questions of computational efficiency. In particular, one candidate class of circuits for which an efficient learner might have been possible was that of Clifford circuits, since the corresponding set of states generated by such circuits, called stabilizer states, are known to be efficiently PAC learnable [44]. Here we provide a negative result, showing that proper learning of CNOT circuits with 1/ poly($n$) error is hard for classical learners unless $\textsf{RP = NP}$, ruling out the possibility of strong learners under standard complexity theoretic assumptions. As the classical analogue and subset of Clifford circuits, this naturally leads to a hardness result for Clifford circuits as well. Additionally, we show that if $\textsf{RP = NP}$ then there would exist efficient proper learning algorithms for CNOT and Clifford circuits. By similar arguments, we also find that an efficient proper quantum learner for such circuits exists if and only if $\textsf{NP ⊆ RQP}$. We leave open the problem of hardness for improper learning or $\mathcal{O(1)}$ error to future work.

► BibTeX data

► References

[1] Scott Aaronson. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463 (2088): 3089–3114, 2007. 10.1098/​rspa.2007.0113.

[2] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 325–338, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/​3188745.3188802.

[3] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/​physreva.70.052328.

[4] J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O'Brien, M. A. Nielsen, and A. G. White. Ancilla-assisted quantum process tomography. Phys. Rev. Lett., 90: 193601, May 2003. 10.1103/​PhysRevLett.90.193601.

[5] Martin Anthony and Peter L. Bartlett. Function learning from interpolation. Combinatorics, Probability and Computing, 9 (3): 213–225, 2000. 10.1017/​S0963548300004247.

[6] Srinivasan Arunachalam and Ronald de Wolf. Guest column: A survey of quantum learning theory. ACM SIGACT News, 48 (2): 41–67, 2017. 10.1145/​3106700.3106710.

[7] Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/​LIPIcs.CCC.2017.25.

[8] Srinivasan Arunachalam, Alex B Grilo, and Henry Yuen. Quantum statistical query learning. arXiv preprint arXiv:2002.08240, 2020. https:/​/​​10.48550/​arXiv.2002.08240.

[9] Srinivasan Arunachalam, Alex Bredariol Grilo, and Aarthi Sundaram. Quantum hardness of learning shallow classical circuits. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/​20M1344202.

[10] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theoretical Computer Science, 560: 7–11, Dec 2014. ISSN 0304-3975. 10.1016/​j.tcs.2014.05.025.

[11] Charles H. Bennett and Stephen J. Wiesner. Communication via one- and two-particle operators on einstein-podolsky-rosen states. Phys. Rev. Lett., 69: 2881–2884, Nov 1992. 10.1103/​PhysRevLett.69.2881.

[12] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Phys. Rev. Lett., 70: 1895–1899, Mar 1993. 10.1103/​PhysRevLett.70.1895.

[13] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/​S0097539796300921.

[14] Avrim Blum. Computational Hardness of Learning. http:/​/​​ avrim/​ML07/​lect1007.pdf, 2015. URL http:/​/​​ avrim/​ML07/​lect1007.pdf. Lecture notes for CS 10-806 Foundations of Machine Learning and Data Science.

[15] Avrim L. Blum and Ronald L. Rivest. Training a 3-node neural network is np-complete. Neural Networks, 5 (1): 117–127, 1992. ISSN 0893-6080. https:/​/​​10.1016/​S0893-6080(05)80010-3.

[16] Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapnik-chervonenkis dimension. J. ACM, 36 (4): 929–965, oct 1989. ISSN 0004-5411. 10.1145/​76359.76371.

[17] Jonathan F Buss, Gudmund S Frandsen, and Jeffrey O Shallit. The computational complexity of some problems of linear algebra. Journal of Computer and System Sciences, 58 (3): 572–596, 1999. ISSN 0022-0000. https:/​/​​10.1006/​jcss.1998.1608.

[18] Matthias C. Caro. Binary classification with classical instances and quantum labels. Quantum Machine Intelligence, 3 (1), may 2021. 10.1007/​s42484-021-00043-z.

[19] Matthias C. Caro and Ishaun Datta. Pseudo-dimension of quantum circuits. Quantum Machine Intelligence, 2 (2), Nov 2020. ISSN 2524-4914. 10.1007/​s42484-020-00027-5.

[20] Hao-Chung Cheng, Min-Hsiu Hsieh, and Ping-Cheng Yeh. The learnability of unknown quantum measurements. Quantum Info. Comput., 16 (7–8): 615–656, may 2016. ISSN 1533-7146. 10.26421/​QIC16.7-8-4.

[21] Isaac L. Chuang and M. A. Nielsen. Prescription for experimental determination of the dynamics of a quantum black box. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/​09500349708231894.

[22] Kai-Min Chung and Han-Hsuan Lin. Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem. In Min-Hsiu Hsieh, editor, 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, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-198-6. 10.4230/​LIPIcs.TQC.2021.3.

[23] Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf's. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 815–830, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR. URL https:/​/​​v49/​daniely16.html.

[24] Steven T Flammia, David Gross, Yi-Kai Liu, and Jens Eisert. Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators. New Journal of Physics, 14 (9): 095022, sep 2012. 10.1088/​1367-2630/​14/​9/​095022.

[25] Paul W. Goldberg and Mark R. Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18: 131–148, 1995. 10.1007/​BF00993408.

[26] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction, 1997.

[27] Daniel Gottesman. The heisenberg representation of quantum computers, 1998.

[28] Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39 (2): 742–765, 2009. 10.1137/​070685798.

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, pages 1–1, 2017. ISSN 1557-9654. 10.1109/​tit.2017.2719044.

[30] Nika Haghtalab. Lecture 9: Hardness of Learning. https:/​/​​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf, 2020. URL https:/​/​​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf. Lecture notes for CS6781 - Theoretical Foundations of Machine Learning.

[31] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, oct 2020. 10.1038/​s41567-020-0932-7.

[32] Jonathan Katz. Notes on Complexity Theory Lecture 3. https:/​/​​ jkatz/​complexity/​f11/​lecture3.pdf, 2011. URL https:/​/​​ jkatz/​complexity/​f11/​lecture3.pdf. Lecture notes for CS 652 — Complexity Theory.

[33] Michael Kharitonov. Cryptographic hardness of distribution-specific learning. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, page 372–381, New York, NY, USA, 1993. Association for Computing Machinery. ISBN 0897915917. 10.1145/​167088.167197.

[34] J. Kleinberg and E. Tardos. Algorithm Design. Pearson Education, 2022. ISBN 9780132131087. URL https:/​/​​books?id=GORecgAACAAJ.

[35] Adam Klivans. The PAC Learning Model. https:/​/​​ klivans/​f06lec2.pdf, 2005. URL https:/​/​​ klivans/​f06lec2.pdf. Lecture notes for CS 395T Computational Learning Theory.

[36] Robert Koenig and John A. Smolin. How to efficiently select an arbitrary clifford group element. Journal of Mathematical Physics, 55 (12): 122202, Dec 2014. ISSN 1089-7658. 10.1063/​1.4903507.

[37] Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs, 2015.

[38] Ching-Yi Lai and Hao-Chung Cheng. Learning quantum circuits of some t gates. IEEE Transactions on Information Theory, pages 1–1, 2022. 10.1109/​TIT.2022.3151760.

[39] Richard A. Low. Learning and testing algorithms for the clifford group. Phys. Rev. A, 80: 052314, Nov 2009. 10.1103/​PhysRevA.80.052314.

[40] Ashley Montanaro. Learning stabilizer states by Bell sampling, 2017.

[41] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1145/​2897518.2897544.

[42] Ryan O'Donnell and John Wright. Efficient quantum tomography ii. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 962–974, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345286. 10.1145/​3055399.3055454.

[43] Yihui Quek, Srinivasan Arunachalam, and John A Smolin. Private learning implies quantum stability. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 20503–20515. Curran Associates, Inc., 2021. URL https:/​/​​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.

[44] Andrea Rocchetto. Stabiliser states are efficiently PAC-learnable. Quantum Information & Computation, 18 (7-8): 541–552, 2018. 10.26421/​qic18.7-8-1.

[45] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41 (2): 303–332, 1999. 10.1137/​S0036144598347011.

[46] Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/​S0097539796298637.

[47] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27 (11): 1134–1142, 1984. 10.1145/​1968.1972.

[48] 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. 10.1109/​QCE52317.2021.00021.

[49] Mithuna Yoganathan. A condition under which classical simulability implies efficient state learnability, 2019.

[50] Huangjun Zhu. Multiqubit clifford groups are unitary 3-designs. Phys. Rev. A, 96: 062336, Dec 2017. 10.1103/​PhysRevA.96.062336.

Cited by

[1] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, "Learning efficient decoders for quasichaotic quantum scramblers", Physical Review A 109 2, 022429 (2024).

[2] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", Nature Reviews Physics 6 1, 59 (2024).

[3] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, "Learning efficient decoders for quasi-chaotic quantum scramblers", arXiv:2212.11338, (2022).

[4] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder, "Optimal algorithms for learning quantum phase states", arXiv:2208.07851, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-02 12:44:11) and SAO/NASA ADS (last updated successfully 2024-03-02 12:44:12). The list may be incomplete as not all publishers provide suitable and complete citation data.