- Physical Review Journals
All JournalsPhysics Magazine

Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Enhancing Generative Models via Quantum Correlations

Xun Gao1, Eric R. Anschuetz2, Sheng-Tao Wang3,1, J. Ignacio Cirac4,5, and Mikhail D. Lukin1

  • 1Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
  • 2MIT Center for Theoretical Physics, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA
  • 3QuEra Computing Inc., Boston, Massachusetts 02135, USA
  • 4Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany
  • 5Munich Center for Quantum Science and Technology (MCQST), Schellingstraße 4, D-80799 München, Germany

PDF

Phys. Rev. X 12, 021037 – Published 13 May, 2022

DOI: https://doi.org/10.1103/PhysRevX.12.021037

Abstract

Generative modeling using samples drawn from the probability distribution constitutes a powerful approach for unsupervised machine learning. Quantum mechanical systems can produce probability distributions that exhibit quantum correlations which are difficult to capture using classical models. We show theoretically that such quantum-inspired correlations provide a powerful resource for generative modeling. In particular, we provide an unconditional proof of separation in expressive power between a class of widely used generative models, known as Bayesian networks, and its minimal quantum-inspired extension. We show that this expressivity enhancement is associated with quantum nonlocality and quantum contextuality. Furthermore, we numerically test this separation on standard machine-learning data sets and show that it holds for practical problems. The possibility of quantum-inspired enhancement demonstrated in this work not only sheds light on the design of useful quantum machine-learning protocols but also provides inspiration to draw on ideas from quantum foundations to improve purely classical algorithms.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Since the inception of machine learning, the field has been linked with that of physics; many of the most successful machine-learning models are inspired by physical systems. Recently, there has been a growing interest in how quantum physics can enhance machine-learning algorithms, and several numerical simulations and proof-of-principle experiments have suggested this possibility. However, very little has been understood about the origin of any potential advantage. Here, we use concepts from foundational quantum research to directly show what salient features of quantum physics can give rise to better performing machine-learning algorithms.

As a concrete example, we focus on a widely used class of classical machine-learning models known as Bayesian networks. These models are known to have a computationally equivalent formulation as Bayesian quantum circuits. We make a minimal extension of the Bayesian quantum circuits by adding a single quantum operation that draws inspiration from the concept of “basis enhancement” in quantum measurement theories. We show that these “quantum-inspired” models, although only minimally extended, are more expressive than the original models in the sense of computational linguistics. We are able to directly link the expressivity enhancement to quantum nonlocality and contextuality, which are some of the most fundamental and counterintuitive concepts of quantum theory. We demonstrate that these foundational quantum ideas not only explain the power of those models simulatable on classical computers but are also potential sources of advantage for models that can be run only on quantum computers. Furthermore, we show that the enhancements are present in real-world settings by numerically testing them on various standard machine-learning tasks.

This work opens a new research direction for using ideas from quantum foundations for the understanding and design of improved machine-learning algorithms for simulating quantum mechanical systems.

Article Text

References (98)

  1. S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, Cambridge, England, 2014).
  2. C. M. Bishop, Pattern Recognition and Machine Learning (Springer, New York, 2006).
  3. I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning (MIT Press, Cambridge, MA, 2016).
  4. F. Arute et al., Quantum Supremacy Using a Programmable Superconducting Processor, Nature (London) 574, 505 (2019).
  5. H.-S. Zhong et al., Quantum Computational Advantage Using Photons, Science 370, 1460 (2020).
  6. Y. Wu et al., Strong Quantum Computational Advantage Using a Superconducting Quantum Processor, Phys. Rev. Lett. 127, 180501 (2021).
  7. Q. Zhu et al., Quantum Computational Advantage via 60-Qubit 24-Cycle Random Circuit Sampling, Science bulletin 67, 280 (2021).
  8. M. Schuld, I. Sinayskiy, and F. Petruccione, An Introduction to Quantum Machine Learning, Contemp. Phys. 56, 172 (2015).
  9. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum Machine Learning, Nature (London) 549, 195 (2017).
  10. M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko, Quantum Boltzmann Machine, Phys. Rev. X 8, 021050 (2018).
  11. A. Perdomo-Ortiz, M. Benedetti, J. Realpe-Gómez, and R. Biswas, Opportunities and Challenges for Quantum-Assisted Machine Learning in Near-Term Quantum Computers, Quantum Sci. Technol. 3, 030502 (2018).
  12. V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Supervised Learning with Quantum-Enhanced Feature Spaces, Nature (London) 567, 209 (2019).
  13. 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 Inf. 5, 45 (2019).
  14. J. Alcazar, V. Leyton-Ortega, and A. Perdomo-Ortiz, Classical Versus Quantum Models in Machine Learning: Insights from a Finance Application, Mach. Learn. 1, 035003 (2020).
  15. M. Schuld and N. Killoran, Quantum Machine Learning in Feature Hilbert Spaces, Phys. Rev. Lett. 122, 040504 (2019).
  16. X. Gao, Z.-Y. Zhang, and L.-M. Duan, A Quantum Machine Learning Algorithm Based on Generative Models, Sci. Adv. 4, eaat9004 (2018).
  17. B. Coyle, D. Mills, V. Danos, and E. Kashefi, The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine, npj Quantum Inf. 6, 60 (2020).
  18. Y. Du, M.-H. Hsieh, T. Liu, and D. Tao, Expressive Power of Parametrized Quantum Circuits, Phys. Rev. Research 2, 033125 (2020).
  19. R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, On the Quantum Versus Classical Learnability of Discrete Distributions, Quantum 5, 417 (2021).
  20. A. Einstein, B. Podolsky, and N. Rosen, Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?, Phys. Rev. 47, 777 (1935).
  21. J. S. Bell, On the Einstein Podolsky Rosen Paradox, Phys. Phys. Fiz. 1, 195 (1964).
  22. J. S. Bell, On the Problem of Hidden Variables in Quantum Mechanics, Rev. Mod. Phys. 38, 447 (1966).
  23. S. Kochen and E. P. Specker, The Problem of Hidden Variables in Quantum Mechanics, in The Logico-Algebraic Approach to Quantum Mechanics (Springer, New York, 1975), pp. 298–328.
  24. J. Anders and D. E. Browne, Computational Power of Correlations, Phys. Rev. Lett. 102, 050502 (2009).
  25. H. Buhrman, R. Cleve, S. Massar, and R. De Wolf, Nonlocality and Communication Complexity, Rev. Mod. Phys. 82, 665 (2010).
  26. M. Howard, J. Wallman, V. Veitch, and J. Emerson, Contextuality Supplies the “Magic” for Quantum Computation, Nature (London) 510, 351 (2014).
  27. J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, Contextuality as a Resource for Models of Quantum Computation with Qubits, Phys. Rev. Lett. 119, 120505 (2017).
  28. M. Frembs, S. Roberts, and S. D. Bartlett, Contextuality as a Resource for Measurement-Based Quantum Computation beyond Qubits, New J. Phys. 20, 103011 (2018).
  29. D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Matrix Product State Representations, Quantum Inf. Comput. 7, 401 (2007).
  30. U. Schollwöck, The Density-Matrix Renormalization Group in the Age of Matrix Product States, Ann. Phys. (Amsterdam) 326, 96 (2011).
  31. E. Stoudenmire and D. J. Schwab, Supervised Learning with Tensor Networks, in Advances in Neural Information Processing Systems, edited by D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Curran Associates, Inc., 2016), Vol. 29, pp. 4799–4807, https://proceedings.neurips.cc/paper/2016/file/5314b9674c86e3f9d1ba25ef9bb32895-Paper.pdf
  32. Z.-Y. Han, J. Wang, H. Fan, L. Wang, and P. Zhang, Unsupervised Generative Modeling Using Matrix Product States, Phys. Rev. X 8, 031012 (2018).
  33. Y. Liu, X. Zhang, M. Lewenstein, and S.-J. Ran, Learning Architectures Based on Quantum Entanglement: A Simple Matrix Product State Algorithm for Image Recognition, Stat, 1050, 16 (2018).
  34. I. Glasser, N. Pancotti, and J. I. Cirac, From Probabilistic Graphical Models to Generalized Tensor Networks for Supervised Learning, IEEE Access 8, 68169 (2020).
  35. D. Niedermayer, An Introduction to Bayesian Networks and Their Contemporary Applications, in Innovations in Bayesian Networks (Springer, New York, 2008), pp. 117–130.
  36. G. H. Low, T. J. Yoder, and I. L. Chuang, Quantum Inference on Bayesian Networks, Phys. Rev. A 89, 062315 (2014).
  37. C. Manning and H. Schutze, Foundations of Statistical Natural Language Processing (MIT Press, Cambridge, MA, 1999).
  38. D. M. Greenberger, M. A. Horne, A. Shimony, and A. Zeilinger, Bell’s Theorem without Inequalities, Am. J. Phys. 58, 1131 (1990).
  39. N. Harrigan, T. Rudolph, and S. Aaronson, Representing Probabilistic Data via Ontological Models, arXiv:0709.1149.
  40. A. Karanjai, J. J. Wallman, and S. D. Bartlett, Contextuality Bounds the Efficiency of Classical Simulation of Quantum Processes, arXiv:1802.07744.
  41. R. W. Spekkens, Contextuality for Preparations, Transformations, and Unsharp Measurements, Phys. Rev. A 71, 052108 (2005).
  42. N. D. Mermin, Hidden Variables and the Two Theorems of John Bell, Rev. Mod. Phys. 65, 803 (1993).
  43. A. Peres, Two Simple Proofs of the Kochen-Specker Theorem, J. Phys. A 24, L175 (1991).
  44. D. Gottesman, Ph.D. thesis, California Institute of Technology, 1997.
  45. N. S. Müller, M. Studer, and G. Ritschard, Classification de Parcours de vie à l’Aide de l’Optimal Matching, in XIVe Rencontre de la Société Francophone de Classification (SFC 2007), pp. 157–160.
  46. G. Ritschard, R. Bürgin, and M. Studer, Exploratory Mining of Life Event Histories, in Contemporary Issues in Exploratory Data Mining in the Behavioral Sciences (Routledge, New York, 2013), pp. 243–276.
  47. D. Dua and C. Graff, UCI Machine Learning Repository (2017), http://archive.ics.uci.edu/ml.
  48. I. Glasser, R. Sweke, N. Pancotti, J. Eisert, and I. Cirac, Expressive Power of Tensor-Network Factorizations for Probabilistic Modeling, in Advances in Neural Information Processing Systems 32, edited by H. Wallach et al. (Curran Associates, 2019), Vol. 32, pp. 1498–1510, https://proceedings.neurips.cc/paper/2019/file/b86e8d03fe992d1b0e19656875ee557c-Paper.pdf.
  49. H. Jaeger, Observable Operator Models for Discrete Stochastic Time Series, Neural Comput. 12, 1371 (2000).
  50. M.-J. Zhao and H. Jaeger, Norm-Observable Operator Models, Neural Comput. 22, 1927 (2010).
  51. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren Plateaus in Quantum Neural Network Training Landscapes, Nat. Commun. 9, 4812 (2018).
  52. M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost-Function-Dependent Barren Plateaus in Shallow Quantum Neural Networks, Nat. Commun. 12, 1791 (2021).
  53. C. O. Marrero, M. Kieferová, and N. Wiebe, Entanglement Induced Barren Plateaus, arXiv:2010.15968.
  54. T. L. Patti, K. Najafi, X. Gao, and S. F. Yelin, Entanglement Devised Barren Plateau Mitigation, Phys. Rev. Research 3, 033090 (2021).
  55. Z. Holmes, A. Arrasmith, B. Yan, P. J. Coles, A. Albrecht, and A. T. Sornborger, Barren Plateaus Preclude Learning Scramblers, Phys. Rev. Lett. 126, 190501 (2021).
  56. E. R. Anschuetz, Critical Points in Hamiltonian Agnostic Variational Quantum Algorithms, arXiv:2109.06957.
  57. K. Poland, K.Beer, and T. J. Osborne, No Free Lunch for Quantum Machine Learning, arXiv:2003.14103.
  58. M. S. Rudolph et al., Generation of High-Resolution Handwritten Digits with an Ion-Trap Quantum Computer, arXiv:2012.03924.
  59. D. Poulin, A. Qarry, R. Somma, and F. Verstraete, Quantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space, Phys. Rev. Lett. 106, 170501 (2011).
  60. R. Orús, A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States, Ann. Phys. (Amsterdam) 349, 117 (2014).
  61. J. C. Bridgeman and C. T. Chubb, Hand-Waving and Interpretive Dance: An Introductory Course on Tensor Networks, J. Phys. A 50, 223001 (2017).
  62. F. Verstraete, V. Murg, and J. I. Cirac, Matrix Product States, Projected Entangled Pair States, and Variational Renormalization Group Methods for Quantum Spin Systems, Adv. Phys. 57, 143 (2008).
  63. G. Vidal, Entanglement Renormalization, Phys. Rev. Lett. 99, 220405 (2007).
  64. F. Verstraete and J. I. Cirac, Renormalization Algorithms for Quantum-Many Body Systems in Two and Higher Dimensions, arXiv:cond-mat/0407066.
  65. J. H. Martin and D. Jurafsky, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition (Pearson/Prentice Hall, Englewood Cliffs, NJ, 2009).
  66. G. E. Hinton, Deep Belief Networks, Scholarpedia 4, 5947 (2009).
  67. V. Bergholm, J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, Quantum Circuits with Uniformly Controlled One-Qubit Gates, Phys. Rev. A 71, 052330 (2005).
  68. S. Kullback and R. A. Leibler, On Information and Sufficiency, Ann. Math. Stat. 22, 79 (1951).
  69. N. D. Mermin, Extreme Quantum Entanglement in a Superposition of Macroscopically Distinct States, Phys. Rev. Lett. 65, 1838 (1990).
  70. R. Raussendorf and H. J. Briegel, One-Way Quantum Computer, Phys. Rev. Lett. 86, 5188 (2001).
  71. J. Barrett, C. M. Caves, B. Eastin, M. B. Elliott, and S. Pironio, Modeling Pauli Measurements on Graph States with Nearest-Neighbor Classical Communication, Phys. Rev. A 75, 012103 (2007).
  72. S. Bravyi, D. Gosset, and R. Koenig, Quantum Advantage with Shallow Circuits, Science 362, 308 (2018).
  73. A. Peres, Incompatible Results of Quantum Measurements, Phys. Lett. A 151, 107 (1990).
  74. N. D. Mermin, Simple Unified Form for the Major No-Hidden-Variables Theorems, Phys. Rev. Lett. 65, 3373 (1990).
  75. P. Aravind, A Simple Demonstration of Bell’s Theorem Involving Two Observers and No Probabilities or Inequalities, arXiv:quant-ph/0206070.
  76. S. Aaronson and D. Gottesman, Improved Simulation of Stabilizer Circuits, Phys. Rev. A 70, 052328 (2004).
  77. K. B. Petersen and M. S. Pedersen, The Matrix Cookbook (2012), http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=3274, Version 20121115.
  78. L. E. Baum, T. Petrie, G. Soules, and N. Weiss, A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains, Ann. Math. Stat. 41, 164 (1970).
  79. D. M. Chickering, Learning Bayesian Networks Is NP-Complete, in Learning from Data (Springer, New York, 1996), pp. 121–130.
  80. P. Dagum and M. Luby, Approximating Probabilistic Inference in Bayesian Belief Networks Is NP-Hard, Artif. Intell. 60, 141 (1993).
  81. D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques (MIT Press, Cambridge, MA, 2009).
  82. T. E. Abrudan, J. Eriksson, and V. Koivunen, Steepest Descent Algorithms for Optimization under Unitary Matrix Constraint, IEEE Trans. Signal Proc. 56, 1134 (2008).
  83. D. E. Rumelhart, G. E. Hinton, and R. J. Williams, Learning Representations by Back-Propagating Errors, Nature (London) 323, 533 (1986).
  84. B. Coecke, G. de Felice, K. Meichanetzidis, and A. Toumi, Foundations for Near-Term Quantum Natural Language Processing, arXiv:2012.03755.
  85. C. Guo, Z. Jie, W. Lu, and D. Poletti, Matrix Product Operators for Sequence to Sequence Learning, Phys. Rev. E 98, 042114 (2018)
  86. E. M. Stoudenmire, Learning Relevant Features of Data with Multi-Scale Tensor Networks, Quantum Sci. Technol. 3, 034003 (2018).
  87. K. Temme and F. Verstraete, Stochastic Matrix Product States, Phys. Rev. Lett. 104, 210502 (2010).
  88. L. Isenhower, M. Saffman, and K. Mølmer, Multibit Ck NOT Quantum Gates via Rydberg Blockade, Quantum Inf. Process. 10, 755 (2011).
  89. P. Høyer and R. Špalek, Quantum Fan-out Is Powerful, Theory Comput. 1, 81 (2005).
  90. S. Arora and B. Barak, Computational Complexity: A Modern Approach (Cambridge University Press, Cambridge, England, 2009).
  91. A. W. Harrow and A. Montanaro, Quantum Computational Supremacy, Nature (London) 549, 203 (2017).
  92. X. Gao, S.-T. Wang, and L.-M. Duan, Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model, Phys. Rev. Lett. 118, 040502 (2017).
  93. L. Stockmeyer, On Approximation Algorithms for #P, SIAM J. Comput. 14, 849 (1985).
  94. R. M. Karp and R. Lipton, Turing Machines that Take Advice, Enseign. Math. 28, 191 (1982).
  95. S. Aaronson, A. Cojocaru, A. Gheorghiu, and E. Kashefi, On the Implausibility of Classical Client Blind Quantum Computing, arXiv:1704.08482.
  96. H. Larochelle and Y. Bengio, Classification Using Discriminative Restricted Boltzmann Machines, in Proceedings of the 25th International Conference on Machine Learning (Association for Computing Machinery, New York, 2008), pp. 536–543, 10.1145/1390156.1390224.
  97. M. Nest, Classical Simulation of Quantum Computation, the Gottesman-Knill Theorem, and Slightly Beyond, Quantum Inf. Comput. 10, 0258 (2010).
  98. M. Krishna, Ph.D. thesis, University of Kerala, 2009 (http://hdl.handle.net/10603/94513).

Outline

Information

Phys. Rev. X 12, 021037– Published 13 May, 2022
  • Received 23 January 2021
  • Revised 17 February 2022
  • Accepted 17 March 2022
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation