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.
 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.
 Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/physreva.70.052328.
 Scott Aaronson and Sabee Grewal. Efficient learning of non-interacting fermion distributions, 2021.
 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.
 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.
 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.
 Srinivasan Arunachalam and Ronald de Wolf. Optimal quantum sample complexity of learning algorithms. The Journal of Machine Learning Research, 19 (1): 2879–2878, 2018.
 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.
 Maria-Florina Balcan. Differential privacy and statistical query learning, 2015.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 LG Valiant. Learning disjunction of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence-Volume 1, pages 560–566, 1985.
 Eric R. Anschuetz and Bobak T. Kiani, "Quantum variational algorithms are swamped with traps", Nature Communications 13 1, 7760 (2022).
 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", Physical Review Letters 130 24, 240602 (2023).
 Niklas Pirnay, Anna Pappa, and Jean-Pierre Seifert, "Learning classical readout quantum PUFs based on single-qubit gates", Quantum Machine Intelligence 4 2, 14 (2022).
 Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao, "Learnability of Quantum Neural Networks", PRX Quantum 2 4, 040337 (2021).
 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, (2021).
The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 18:46:14) and SAO/NASA ADS (last updated successfully 2023-11-29 18:46:15). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.