1Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, D-14195 Berlin, Germany
2Department of Electrical Engineering and Computer Science, TU Berlin, D-10587 Berlin, Germany
3FhG SIT, D-64295 Darmstadt, Germany
4Helmholtz Center Berlin, D-14109 Berlin, Germany
5Department of Mathematics and Computer Science, Freie Universität Berlin, D-14195 Berlin, Germany
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete probability distributions which, under the decisional Diffie-Hellman assumption, is provably not efficiently PAC learnable by a classical generative modelling algorithm, but for which we construct an efficient quantum learner. This class of distributions therefore provides a concrete example of a generative modelling problem for which quantum learners exhibit a provable advantage over classical learning algorithms. In addition, we discuss techniques for proving classical generative modelling hardness results, as well as the relationship between the PAC learnability of Boolean functions and the PAC learnability of discrete probability distributions.
► BibTeX data
► References
[1] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https://doi.org/10.1145/1968.1972
[2] M. J. Kearns, U. V. Vazirani, and U. Vazirani. An introduction to computational learning theory. MIT press, 1994a. 10.7551/mitpress/3897.001.0001.
https://doi.org/10.7551/mitpress/3897.001.0001
[3] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. 10.1017/CBO9781107298019.
https://doi.org/10.1017/CBO9781107298019
[4] S. Arunachalam and R. de Wolf. Guest column: A survey of quantum learning theory. ACM SIGACT News, 48 (2): 41–67, 2017. 10.1145/3106700.3106710.
https://doi.org/10.1145/3106700.3106710
[5] C. Ciliberto, A. Rocchetto, A. Rudi, and L. Wossnig. Statistical limits of supervised quantum learning. Physical Review A, 102 (4), Oct 2020. 10.1103/physreva.102.042414.
https://doi.org/10.1103/physreva.102.042414
[6] V. Dunjko and H. J. Briegel. Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Rep. Prog. Phys., 81 (7): 074001, 2018. 10.1088/1361-6633/aab406.
https://doi.org/10.1088/1361-6633/aab406
[7] M. Schuld and F. Petruccione. Supervised learning with quantum computers. Springer, 2018. 10.1007/978-3-319-96424-9.
https://doi.org/10.1007/978-3-319-96424-9
[8] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, 2017. 10.1038/nature23474.
https://doi.org/10.1038/nature23474
[9] N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing, 28 (3): 1136–1153, 1998. 10.1145/225298.225312.
https://doi.org/10.1145/225298.225312
[10] C. L. Canonne. A short note on learning discrete distributions. arXiv preprint arXiv:2002.11457, 2020a.
arXiv:2002.11457
[11] S. Kamath, A. Orlitsky, D. Pichapati, and A. T. Suresh. On learning distributions from their samples. In P. Grünwald, E. Hazan, and S. Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1066–1100, Paris, France, 03–06 Jul 2015. PMLR. URL http://proceedings.mlr.press/v40/Kamath15.html.
http://proceedings.mlr.press/v40/Kamath15.html
[12] I. Diakonikolas. Learning structured distributions. Handbook of Big Data, 267, 2016. 10.1201/b19567.
https://doi.org/10.1201/b19567
[13] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672–2680, 2014.
[14] D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
arXiv:1312.6114
[15] I. Kobyzev, S. Prince, and M. Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1–16, 2020. 10.1109/tpami.2020.2992934.
https://doi.org/10.1109/tpami.2020.2992934
[16] B. Coyle, D. Mills, V. Danos, and E. Kashefi. The Born supremacy: quantum advantage and training of an Ising Born machine. npj Quantum Information, 6: 60, 2020. 10.1038/s41534-020-00288-9.
https://doi.org/10.1038/s41534-020-00288-9
[17] J.-G. Liu and L. Wang. Differentiable learning of quantum circuit Born machines. Phys. Rev. A, 98 (6): 062324, 2018. 10.1103/PhysRevA.98.062324.
https://doi.org/10.1103/PhysRevA.98.062324
[18] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. Leyton-Ortega, Y. Nam, and A. Perdomo-Ortiz. A generative modeling approach for benchmarking and training shallow quantum circuits. npj Quantum Information, 5 (1), May 2019. 10.1038/s41534-019-0157-8.
https://doi.org/10.1038/s41534-019-0157-8
[19] X. Gao, Z. Zhang, and L. Duan. A quantum machine learning algorithm based on generative models. Science Advances, 4 (12): eaat9004, 2018. 10.1126/sciadv.aat9004.
https://doi.org/10.1126/sciadv.aat9004
[20] P.-L. Dallaire-Demers and N. Killoran. Quantum generative adversarial networks. Phys. Rev. A, 98, 2018. 10.1103/physreva.98.012324.
https://doi.org/10.1103/physreva.98.012324
[21] L. Hu, S.-H. Wu, W. Cai, Y. Ma, X. Mu, Y. Xu, H. Wang, Y. Song, D.-L. Deng, C.-L. Zou, and L. Sun. Quantum generative adversarial learning in a superconducting quantum circuit. Science Advances, 5 (1): eaav2761, 2019. 10.1126/sciadv.aav2761.
https://doi.org/10.1126/sciadv.aav2761
[22] S. Lloyd and C. Weedbrook. Quantum generative adversarial learning. Phys. Rev. Lett., 121 (4): 040502, 2018. 10.1103/PhysRevLett.121.040502.
https://doi.org/10.1103/PhysRevLett.121.040502
[23] S. Chakrabarti, H. Yiming, T. Li, S. Feizi, and X. Wu. Quantum Wasserstein generative adversarial networks. In Advances in Neural Information Processing Systems, pages 6781–6792, 2019.
[24] G. Verdon, J. Marks, S. Nanda, S. Leichenauer, and J. Hidary. Quantum Hamiltonian-ased models and the variational quantum thermalizer algorithm, 2019. arXiv preprint arXiv:1910.02071.
arXiv:1910.02071
[25] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery. 10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682
[26] M. J. Bremner, A. Montanaro, and D. J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, Aug 2016. 10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501
[27] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[28] D. Boneh. The decision Diffie-Hellman problem. In International Algorithmic Number Theory Symposium, pages 48–63. Springer, 1998. 10.1007/BFb0054851.
https://doi.org/10.1007/BFb0054851
[29] M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. E. Schapire, and L. Sellie. On the learnability of discrete distributions. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC ’94, pages 273–282, New York, NY, USA, 1994b. ACM. 10.1145/195058.195155.
https://doi.org/10.1145/195058.195155
[30] M. Mosca and C. Zalka. Exact quantum fourier transforms and discrete logarithm algorithms. International Journal of Quantum Information, 2 (01): 91–100, 2004. 10.1142/S0219749904000109.
https://doi.org/10.1142/S0219749904000109
[31] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. ACM, 33 (4): 792–807, August 1986. 10.1145/6490.6503.
https://doi.org/10.1145/6490.6503
[32] E. L. Lehmann and J. P. Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006. 10.1111/j.1467-985X.2007.00473_10.x.
https://doi.org/10.1111/j.1467-985X.2007.00473_10.x
[33] O. Goldreich. Foundations of cryptography: volume 1, basic tools. Cambridge University Press, 2007. 10.1017/CBO9780511546891.
https://doi.org/10.1017/CBO9780511546891
[34] J. Katz and Y. Lindell. Introduction to Modern Cryptography (Chapman & Hall/Crc Cryptography and Network Security Series). Chapman & Hall/CRC, 2007. 10.1201/b17668.
https://doi.org/10.1201/b17668
[35] M. Zhandry. How to construct quantum random functions. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS ’12, pages 679–687. IEEE Computer Society, 2012. 10.1109/FOCS.2012.37.
https://doi.org/10.1109/FOCS.2012.37
[36] A. Bogdanov and A. Rosen. Pseudorandom functions: Three decades later. In Tutorials on the Foundations of Cryptography, pages 79–158. Springer, 2017. 10.1007/978-3-319-57048-8_3.
https://doi.org/10.1007/978-3-319-57048-8_3
[37] M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM journal on Computing, 13 (4): 850–864, 1984. 10.1109/SFCS.1982.72.
https://doi.org/10.1109/SFCS.1982.72
[38] M. Naor and O. Reingold. Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM (JACM), 51 (2): 231–262, 2004. 10.1145/972639.972643.
https://doi.org/10.1145/972639.972643
[39] R. R. Farashahi, B. Schoenmakers, and A. Sidorenko. Efficient pseudorandom generators based on the ddh assumption. In International Workshop on Public Key Cryptography, pages 426–441. Springer, 2007. 10.1007/978-3-540-71677-8_28.
https://doi.org/10.1007/978-3-540-71677-8_28
[40] C. L. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys. Theory of Computing Library, 2020b. 10.4086/toc.gs.2020.009.
https://doi.org/10.4086/toc.gs.2020.009
[41] G. Valiant and P. Valiant. A clt and tight lower bounds for estimating entropy. In Electronic Colloquium on Computational Complexity (ECCC), volume 17, page 9. Citeseer, 2010.
[42] G. Valiant and P. Valiant. The power of linear estimators. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 403–412. IEEE, 2011. 10.1109/FOCS.2011.81.
https://doi.org/10.1109/FOCS.2011.81
[43] G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. SIAM J. Comput., 46 (1): 429–455, 2017. 10.1137/151002526.
https://doi.org/10.1137/151002526
[44] D. Hangleiter, M. Kliesch, J. Eisert, and C. Gogolin. Sample complexity of device-independently certified quantum supremacy. Phys. Rev. Lett., 122: 210502, 2019. 10.1103/PhysRevLett.122.210502.
https://doi.org/10.1103/PhysRevLett.122.210502
[45] Y. Liu, S. Arunachalam, and K. Temme. A rigorous and robust quantum speed-up in supervised machine learning. arXiv preprint arXiv:2010.02174, 2020.
arXiv:2010.02174
[46] K. 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.
https://doi.org/10.1007/978-3-642-27660-6_9
[47] A. W. Cross, G. Smith, and J. A. Smolin. Quantum learning robust against noise. Phys. Rev. A, 92 (1): 012327, 2015. 10.1103/physreva.92.012327.
https://doi.org/10.1103/physreva.92.012327
[48] A. B. Grilo, I. Kerenidis, and T. Zijlstra. Learning-with-errors problem is easy with quantum samples. Phys. Rev. A, 99: 032314, 2019. 10.1103/physreva.99.032314.
https://doi.org/10.1103/physreva.99.032314
[49] D. Riste, M. P. da Silva, C. A. Ryan, A. W. Cross, A. D. Córcoles, J. A. Smolin, J. M. Gambetta, J. M. Chow, and B. R. Johnson. Demonstration of quantum advantage in machine learning. npj Quantum Inf., 3 (1): 1–5, 2017. 10.1038/s41534-017-0017-3.
https://doi.org/10.1038/s41534-017-0017-3
[50] M. Kearns and L. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41 (1): 67–95, 1994. 10.1145/174644.174647.
https://doi.org/10.1145/174644.174647
[51] R. A. Servedio and S. J. Gortler. Equivalences and separations between quantum and classical learnability. SIAM J. Comp., 33 (5): 1067–1092, 2004. 10.1137/S0097539704412910.
https://doi.org/10.1137/S0097539704412910
[52] K. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Proceedings of the third annual workshop on Computational learning theory, pages 314–326, 1990. 10.1016/B978-1-55860-146-8.50027-8.
https://doi.org/10.1016/B978-1-55860-146-8.50027-8
[53] M. 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. 10.1145/167088.167197.
https://doi.org/10.1145/167088.167197
[54] M. Kharitonov. Cryptographic lower bounds for learnability of boolean functions on the uniform distribution. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT ’92, page 29–36, New York, NY, USA, 1992. Association for Computing Machinery. 10.1145/130385.130388.
https://doi.org/10.1145/130385.130388
[55] V. Arvind and N. V. Vinodchandran. The complexity of exactly learning algebraic concepts. In International Workshop on Algorithmic Learning Theory, pages 100–112. Springer, 1996. 10.1007/3-540-61863-5_38.
https://doi.org/10.1007/3-540-61863-5_38
[56] D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth. Equivalence of models for polynomial learnability. Information and Computation, 95 (2): 129–161, 1991. 10.1016/0890-5401(91)90042-Z.
https://doi.org/10.1016/0890-5401(91)90042-Z
[57] R. Board and L. Pitt. On the necessity of occam algorithms. Theoretical Computer Science, 100 (1): 157–184, 1992. 10.1145/100216.100223.
https://doi.org/10.1145/100216.100223
[58] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36 (4): 929–965, 1989. 10.1145/76359.76371.
https://doi.org/10.1145/76359.76371
[59] X. Gao, S.-T. Wang, and L.-M. Duan. Quantum supremacy for simulating a translation-invariant ising spin model. Phys. Rev. Lett., 118: 040502, Jan 2017. 10.1103/PhysRevLett.118.040502.
https://doi.org/10.1103/PhysRevLett.118.040502
[60] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing a quantum speedup. Phys. Rev. X, 8: 021010, 2018. 10.1103/PhysRevX.8.021010.
https://doi.org/10.1103/PhysRevX.8.021010
[61] J. Miller, S. Sanders, and A. Miyake. Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Phys. Rev. A, 96 (6): 062320, December 2017. 10.1103/PhysRevA.96.062320.
https://doi.org/10.1103/PhysRevA.96.062320
[62] M. Hayashi and Y. Takeuchi. Verifying commuting quantum computations via fidelity estimation of weighted graph states. New J. Phys., 21 (9): 093060, 2019. 10.1088/1367-2630/ab3d88.
https://doi.org/10.1088/1367-2630/ab3d88
Cited by
[1] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme, “A rigorous and robust quantum speed-up in supervised machine learning”, arXiv:2010.02174.
[2] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean, “Power of data in quantum machine learning”, arXiv:2011.01938.
[3] Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis, and Alexis Toumi, “Foundations for Near-Term Quantum Natural Language Processing”, arXiv:2012.03755.
[4] Daniel Herr, Benjamin Obert, and Matthias Rosenkranz, “Anomaly detection with variational quantum generative adversarial networks”, arXiv:2010.10492.
[5] Manuel S. Rudolph, Ntwali Bashige Toussaint, Amara Katabarwa, Sonika Johri, Borja Peropadre, and Alejandro Perdomo-Ortiz, “Generation of High-Resolution Handwritten Digits with an Ion-Trap Quantum Computer”, arXiv:2012.03924.
[6] Brian Coyle, Maxwell Henderson, Justin Chan Jin Le, Niraj Kumar, Marco Paini, and Elham Kashefi, “Quantum versus Classical Generative Modelling in Finance”, arXiv:2008.00691.
[7] Stefano Mangini, Francesco Tacchino, Dario Gerace, Daniele Bajoni, and Chiara Macchiavello, “Quantum computing models for artificial neural networks”, arXiv:2102.03879.
[8] Murphy Yuezhen Niu, Andrew M. Dai, Li Li, Augustus Odena, Zhengli Zhao, Vadim Smelyanskyi, Hartmut Neven, and Sergio Boixo, “Learnability and Complexity of Quantum Samples”, arXiv:2010.11983.
[9] Ieva Čepaitė, Brian Coyle, and Elham Kashefi, “A Continuous Variable Born Machine”, arXiv:2011.00904.
[10] Marcello Benedetti, Brian Coyle, Mattia Fiorentini, Michael Lubasch, and Matthias Rosenkranz, “Variational inference with a quantum computer”, arXiv:2103.06720.
The above citations are from SAO/NASA ADS (last updated successfully 2021-03-23 10:02:58). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-03-23 10:02:49: Could not fetch cited-by data for 10.22331/q-2021-03-23-417 from Crossref. This is normal if the DOI was registered recently.
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.
Coinsmart. Beste Bitcoin-Börse in Europa
Source: https://quantum-journal.org/papers/q-2021-03-23-417/
