On the Hardness of PAC-learning Stabilizer States with Noise

Aravind Gollakota and 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.


We consider the problem of learning stabilizer states with noise in the Probably Approximately Correct (PAC) framework of Aaronson (2007) for learning quantum states. In the noiseless setting, an algorithm for this problem was recently given by Rocchetto (2018), but the noisy case was left open. Motivated by approaches to noise tolerance from classical learning theory, we introduce the Statistical Query (SQ) model for PAC-learning quantum states, and prove that algorithms in this model are indeed resilient to common forms of noise, including classification and depolarizing noise. We prove an exponential lower bound on learning stabilizer states in the SQ model. Even outside the SQ model, we prove that learning stabilizer states with noise is in general as hard as Learning Parity with Noise (LPN) using classical examples. Our results position the problem of learning stabilizer states as a natural quantum analogue of the classical problem of learning parities: easy in the noiseless setting, but seemingly intractable even with simple forms of noise.

► 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. SIAM Journal on Computing, 49 (5): STOC18–368, 2019. 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] Scott Aaronson and Sabee Grewal. Efficient learning of non-interacting fermion distributions, 2021.

[5] Scott Aaronson and Guy N Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 322–333, 2019. 10.1145/​3313276.3316378.

[6] Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning of quantum states. Journal of Statistical Mechanics: Theory and Experiment, 2019 (12): 124019, 2019. 10.1088/​1742-5468/​ab3988.

[7] Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2 (4): 343–370, 1988. 10.1023/​a:1022873112823.

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

[9] Srinivasan Arunachalam and Ronald de Wolf. Optimal quantum sample complexity of learning algorithms. The Journal of Machine Learning Research, 19 (1): 2879–2878, 2018.

[10] Srinivasan Arunachalam, Alex B Grilo, and Henry Yuen. Quantum statistical query learning. arXiv preprint arXiv:2002.08240, 2020.

[11] Srinivasan Arunachalam, Yihui Quek, and John Smolin. Private learning implies quantum stability, arXiv preprint arXiv:2102.07171, 2021.

[12] Javed A Aslam and Scott E Decatur. Specification and simulation of statistical query algorithms for efficiency and noise tolerance. Journal of Computer and System Sciences, 56 (2): 191–208, 1998. 10.1145/​225298.225351.

[13] Maria-Florina Balcan. Differential privacy and statistical query learning, 2015.

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

[15] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 253–262, 1994. 10.1145/​195058.195147.

[16] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50 (4): 506–519, 2003. 10.1145/​792538.792543.

[17] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: The SuLQ framework. In Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 128–138, 2005. 10.1145/​1065167.1065184.

[18] M. Bun, R. Livni, and S. Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389–402, Los Alamitos, CA, USA, November 2020. IEEE Computer Society. 10.1109/​focs46700.2020.00044.

[19] Hao-Chung Cheng, Min-Hsiu Hsieh, and Ping-Cheng Yeh. The learnability of unknown quantum measurements, arXiv preprint arXiv:1501.00559 2015.

[20] Andrew W Cross, Graeme Smith, and John A Smolin. Quantum learning robust against noise. Physical Review A, 92 (1): 012327, 2015. 10.1103/​physreva.92.012327.

[21] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9 (3-4): 211–407, 2014. 10.1561/​0400000042.

[22] Vitaly Feldman. A complete characterization of statistical query learning with applications to evolvability. Journal of Computer and System Sciences, 78 (5): 1444–1459, 2012. 10.1109/​focs.2009.35.

[23] Vitaly Feldman. Statistical query learning. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 2090–2095. Springer New York, New York, NY, 2016. ISBN 978-1-4939-2864-4. 10.1007/​978-1-4939-2864-4₄01.

[24] Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, 2020.

[25] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint quant-ph/​9705052, 1997.

[26] Daniel Gottesman. The Heisenberg representation of quantum computers. arXiv preprint quant-ph/​9807006, 1998.

[27] Alex B Grilo, Iordanis Kerenidis, and Timo Zijlstra. Learning-with-errors problem is easy with quantum samples. Physical Review A, 99 (3): 032314, 2019. 10.1103/​physreva.99.032314.

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

[29] M. Hamermesh. Group Theory and Its Application to Physical Problems. Addison Wesley Series in Physics. Dover Publications, 1989. ISBN 978-0-486-66181-0. 10.1119/​1.1941790.

[30] Lisa Hellerstein and Rocco A Servedio. On pac learning algorithms for rich boolean function classes. Theoretical Computer Science, 384 (1): 66–76, 2007. 10.1007/​11750321_42.

[31] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40 (3): 793–826, 2011. 10.1137/​090756090.

[32] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45 (6): 983–1006, 1998. 10.1145/​293347.293351.

[33] Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22 (4): 807–837, 1993. 10.1137/​0222052.

[34] Ching-Yi Lai and Hao-Chung Cheng. Learning quantum circuits of some T gates, arXiv:2106.12524 2021.

[35] Ashley Montanaro. Learning stabilizer states by Bell sampling, arXiv:1707.04012 2017.

[36] 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. 10.1145/​2897518.2897544.

[37] Ryan O'Donnell and John Wright. Efficient quantum tomography II. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 962–974, 2017. 10.1145/​3055399.3055454.

[38] Krzysztof Pietrzak. Cryptography from learning parity with noise. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 99–114. Springer, 2012. 10.1007/​978-3-642-27660-6_9.

[39] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer. Simulation of qubit quantum circuits via Pauli propagation. Physical Review A, 99 (6), June 2019. ISSN 2469-9934. 10.1103/​physreva.99.062337.

[40] Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557, 2020.

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

[42] Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, and Fabio Sciarrino. Experimental learning of quantum states. Science advances, 5 (3): eaau1946, 2019. 10.1126/​sciadv.aau1946.

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

[44] LG Valiant. Learning disjunction of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence-Volume 1, pages 560–566, 1985.

[45] Mithuna Yoganathan. A condition under which classical simulability implies efficient state learnability, arXiv:1907.08163 2019.

Cited by

[1] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao, "Learnability of Quantum Neural Networks", PRX Quantum 2 4, 040337 (2021).

[2] Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, and Ryan Sweke, "Learnability of the output distributions of local quantum circuits", arXiv:2110.05517.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-28 18:31:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-28 18:31:05).