×

Quantum hardness of learning shallow classical circuits. (English) Zbl 1516.68037

Summary: In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.
1. Hardness of PAC learning \(\mathrm{AC}^0\) and \(\mathrm{TC}^0\) under the uniform distribution. Our first result concerns the concept class \(\mathrm{TC}^0\) (resp., \(\mathrm{AC}^0)\), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., AND, OR, NOT gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (RLWE) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for \(\mathrm{TC}^0\); and if there exists no \(2^{O(d^{1/\eta})}\)-time quantum algorithm to solve RLWE with dimension \(d = O(\operatorname{polylog} n)\) (for every constant \(\eta > 2)\), then there exists no \(O(n^{ \log^{\nu} n} )\)-time quantum learning algorithm for \(\operatorname{poly}(n)\)-sized \(\mathrm{AC}^0\) circuits (for a constant \(\nu>0)\), matching the classical upper bound of N. Linial et al. [J. Assoc. Comput. Mach. 40, No. 3, 607–620 (1993; Zbl 0781.94006)], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution.
2. Hardness of learning \(\mathrm{TC}^0_2\) in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the LWE problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class \(\mathrm{TC}^0_2\), i.e., depth-2 \(\mathrm{TC}^0\) circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory” raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.

MSC:

68Q12 Quantum algorithms and complexity in the theory of computing
68Q06 Networks and circuits as models of computation; circuit complexity
68T05 Learning and adaptive systems in artificial intelligence
81P68 Quantum computation
81P94 Quantum cryptography (quantum-theoretic aspects)

Citations:

Zbl 0781.94006

Software:

BKZ; ring-LWE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Aaronson, Ten Semi-grand Challenges for Quantum Computing Theory, https://www.scottaaronson.com/writings/qchallenge.html, 2005.
[2] A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay, SETH-based lower bounds for subset sum and bicriteria path, in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2019, pp. 41-57. · Zbl 1431.68040
[3] J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic, Advances in Quantum Machine Learning, arXiv:1512.02900, 2015.
[4] D. Aggarwal and N. Stephens-Davidowitz, (Gap/S)ETH hardness of SVP, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2018, pp. 228-238. · Zbl 1427.68101
[5] M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 284-293. · Zbl 0962.68055
[6] A. Ambainis, L. Magnin, M. Roetteler, and J. Roland, Symmetry-assisted adversaries for quantum state generation, in Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC, 2011, pp. 167-177.
[7] D. Angluin, Queries and concept learning, Machine Learning, 2 (1987), pp. 319-342. · Zbl 1470.68050
[8] S. Arora and R. Ge, New algorithms for learning in presence of errors, in International Colloquium on Automata, Languages, and Programming, Springer, New York, 2011, pp. 403-415. · Zbl 1332.68099
[9] S. Arunachalam, S. Chakraborty, T. Lee, M. Paraashar, and R. de Wolf, Two new results about quantum exact learning, in Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, ICALP, 2019, pp. 16:1-16:15. · Zbl 07561509
[10] S. Arunachalam, A. B. Grilo, T. Gur, I. C. Oliveira, and A. Sundaram, Quantum Learning Algorithms Imply Circuit Lower Bounds, arXiv:2012.01920, 2020.
[11] S. Arunachalam and R. de Wolf, Guest column: A survey of quantum learning theory, SIGACT News, 48 (2017), pp. 41-67.
[12] A. At\i c\i and R. Servedio, Quantum algorithms for learning and testing juntas, Quantum Inf. Process., 6 (2009), pp. 323-348. · Zbl 1155.81014
[13] A. Banerjee, C. Peikert, and A. Rosen, Pseudorandom functions and lattices, in Advances in Cryptology - EUROCRYPT 2012, 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques., 2012, pp. 719-737. · Zbl 1297.68071
[14] E. Bernstein and U. V. Vazirani, Quantum complexity theory, SIAM J. Comput., 26 (1997), pp. 1411-1473. · Zbl 0895.68042
[15] A. Blum, A. Kalai, and H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, J. ACM, 50 (2003), pp. 506-519. · Zbl 1325.68114
[16] L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comput., 15 (1986), pp. 364-383. · Zbl 0602.65002
[17] D. Boneh, Ö. Dagdelen, M. Fischlin, A. Lehmann, C. Schaffner, and M. Zhandry, Random Oracles in a Quantum World, in Advances in Cryptology, ASIACRYPT 2011, 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 2011, pp. 41-69. · Zbl 1227.94033
[18] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehlé, Classical hardness of learning with errors, in Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, 2013, pp. 575-584, https://doi.org/10.1145/2488608.2488680. · Zbl 1293.68159
[19] N. H. Bshouty and J. C. Jackson, Learning DNF over the uniform distribution using a quantum example oracle, SIAM J. Comput., 28 (1999), pp. 1136–1153. · Zbl 0918.68033
[20] Y. Chen and P. Q. Nguyen, BKZ 2.0: Better lattice security estimates, in Advances in Cryptology, ASIACRYPT 2011, 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 2011, pp. 1-20, https://doi.org/10.1007/978-3-642-25385-0_1. · Zbl 1227.94037
[21] K. Chung and H. Lin, On the Sample Complexity of PAC Learning Quantum Process, arXiv:1810.10938, 2018.
[22] A. Daniely and S. Shalev-Shwartz, Complexity theoretic limitations on learning DNF’s, in Proceedings of the 29th Conference on Learning Theory, COLT’16, 2016.
[23] V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami, New results for learning noisy parities and halfspaces, in 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS’06, 2006, pp. 563-574.
[24] M. Goldmann, J. H\aastad, and A. A. Razborov, Majority gates S. general weighted threshold gates, Comput. Complexity, 2 (1992), pp. 277-300. · Zbl 0770.68054
[25] O. Goldreich and S. Goldwasser, On the limits of nonapproximability of lattice problems, J. Comput. System Sci., 60 (2000), pp. 540-563. · Zbl 0961.68122
[26] A. B. Grilo, I. Kerenidis, and T. Zijlstra, Learning with Errors is easy with quantum samples, Phys. Rev. A, 99 (2019), 032314.
[27] A. Healy and E. Viola, Constant-depth circuits for arithmetic in finite fields of characteristic two, in Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science, STACS’06, Springer-Verlag, pp. 672-683, Berlin, 2006, https://doi.org/10.1007/11672142_55. · Zbl 1137.68027
[28] W. Hesse, E. Allender, and D. A. M. Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, J. Comput. System Sci., 65 (2002), pp. 695-716. · Zbl 1059.68044
[29] J. C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, J. Comput. System Sci., 55 (1997), pp. 414-440. · Zbl 0897.68051
[30] V. Kanade, A. Rocchetto, and S. Severini, Learning DNFs Under Product Distributions via \(\mu \)-biased Quantum Fourier Sampling preprint, arXiv:1802.05690, 2018.
[31] M. J. Kearns and L. G. Valiant, Cryptographic limitations on learning boolean formulae and finite automata, J. ACM, 41 (1994), pp. 67-95. · Zbl 0807.68073
[32] I. Kerenidis, M. Laurière, F. Le Gall, and M. Rennela, Information cost of quantum communication protocols, Quantum Inf. Comput., 16 (2016), pp. 181-196.
[33] M. Kharitonov, Cryptographic hardness of distribution-specific learning, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 372-381. · Zbl 1310.94155
[34] M. Kharitonov, Cryptographic lower bounds for learnability of boolean functions on the uniform distribution, J. Comput. and System Sci., 50 (1995), pp. 600 – 610. · Zbl 0837.68096
[35] A. R. Klivans and A. A. Sherstov, Cryptographic hardness for learning intersections of halfspaces, J. Comput. System Sci., 75 (2009), pp. 1-12. · Zbl 1158.68384
[36] A. Langlois and D. Stehlé, Worst-case to average-case reductions for module lattices, Des., Codes Cryptogr., 75 (2015), pp. 565-599, https://doi.org/10.1007/s10623-014-9938-4. · Zbl 1361.94043
[37] A. K. Lenstra, H. W. Lenstra, and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), pp. 515-534, https://doi.org/10.1007/BF01457454. · Zbl 0488.12001
[38] N. Lindzey and A. Rosmanis, A Tight Lower Bound for Non-coherent Index Erasure, arXiv:1902.07336, 2019.
[39] N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transform, and learnability, J. ACM, 40 (1993), pp. 607-620. · Zbl 0781.94006
[40] V. Lyubashevsky, C. Peikert, and O. Regev, On ideal lattices and learning with errors over rings, J. ACM, 60 (2013), pp. 43:1-43:35, https://doi.org/10.1145/2535925. · Zbl 1281.68140
[41] V. Lyubashevsky, C. Peikert, and O. Regev, A toolkit for Ring-LWE cryptography, in Advances in Cryptology, EUROCRYPT 2013, T. Johansson and P. Q. Nguyen, eds., Springer, Berlin, 2013, pp. 35-54. · Zbl 1300.94082
[42] W. Maass, G. Schnitger, and E. D. Sontag, On the computational power of Sigmoid versus Boolean threshold circuits, in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 767-776.
[43] A. Maciel and D. Thérien, Threshold circuits of small majority-depth, Inform. Comput., 146 (1998), pp. 55-83. · Zbl 0916.68060
[44] M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, J. ACM, 51 (2004), pp. 231-262. · Zbl 1248.94086
[45] I. C. Oliveira and R. Santhanam, Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness, in Proceedings of the 32nd Computational Complexity Conference, CCC, 2017, pp. 18:1-18:49. · Zbl 1440.68083
[46] C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC, 2009, pp. 333-342. · Zbl 1304.94079
[47] C. Peikert, A decade of lattice cryptography, Found. Trends Theoret. Comput. Sci., 10 (2016), pp. 283-424. · Zbl 1391.94788
[48] C. Peikert, O. Regev, and N. Stephens-Davidowitz, Pseudorandomness of Ring-LWE for any ring and modulus, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 461-473, https://doi.org/10.1145/3055399.3055489. · Zbl 1370.94536
[49] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56 (2009), pp. 34:1-34:40. · Zbl 1325.68101
[50] J. H. Reif and S. R. Tate, On threshold circuits and polynomial computation, SIAM J. Comput., 21 (1992), pp. 896-908. · Zbl 0765.68057
[51] R. E. Schapire, The strength of weak learnability, Mach. Learn., 5 (1990), pp. 197-227.
[52] M. Schuld and F. Petruccione, Supervised Learning with Quantum Computers, Springer, New York, 2018. · Zbl 1411.81008
[53] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26 (1997), pp. 1484-1509. · Zbl 1005.11065
[54] K. E. Stange, Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum-Kalai-Wasserman Algorithm, preprint, arXiv:1902.07140, 2019.
[55] D. Touchette, Quantum information complexity, in Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 317-326. · Zbl 1321.94022
[56] L. Valiant, A theory of the learnable, Commun. ACM, 27 (1984), pp. 1134––1142. · Zbl 0587.68077
[57] K. A. Verbeurgt, Learning DNF under the uniform distribution in quasi-polynomial time, in Proceedings of the 3rd Annual Workshop on Computational Learning Theory, COLT’90, 1990, pp. 314-326.
[58] D. Wagner, A generalized birthday problem, in Annual International Cryptology Conference, Springer, New York, 2002, pp. 288-304. · Zbl 1026.94541
[59] M. Zhandry, How to construct quantum random functions, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, 2012, pp. 679-687.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.