An efficient quantum algorithm for generative machine learning

Duan 1,2 1 Center for Quantum Information, IIIS, Tsinghua University, Beijing 100084, PR China 2 Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer [1-3]. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup [4-8]. Several quantum algorithms for discriminative machine learning [9] have been found based on efficient solving of linear algebraic problems [10-15], with potential exponential speedup in runtime under the assumption of effective input from a quantum random access memory [16]. In machine learning, generative models represent another large class [9] which is widely used for both supervised and unsupervised learning [17, 18]. Here, we propose an efficient quantum algorithm for machine learning based on a quantum generative model. We prove that our proposed model is exponentially more powerful to represent probability distributions compared with classical generative models and has exponential speedup in training and inference at least for some instances under a reasonable assumption in computational complexity theory. Our result opens a new direction for quantum machine learning and offers a remarkable example in which a quantum algorithm shows exponential improvement over any classical algorithm in an important application field. Machine learning and artificial intelligence represent a very important application area which could be revolutionized by quantum computers with clever algorithms that offer exponential speedup [4, 5]. The candidate algorithms with potential exponential speedup so far rely on efficient quantum solution of linear system of equations or linear algebraic problems [12-15]. Those algorithms require quantum random access memory (QRAM) as a critical component in addition to a quantum computer. In a QRAM, the number of required quantum routers scales up exponentially with the number of qubits in those algorithms [16, 19]. This exponential overhead in resource requirement poses a significant challenge for its experimental implementation and is a caveat for fair comparison with corresponding classical algorithms [5, 20]. In this paper, we propose a quantum algorithm with potential exponential speedup for machine learning basedFigure 1: Classical and quantum generative models. A factor graph is a bipartite graph where one group of the vertices represent variables (denoted by circles) and the other group of vertices represent positive functions (denoted by squares) acting on connected variables. The corresponding probability distribution is given by the product of all these functions. Each variable connects to at most a constant number of functions which introduce correlations in the probability distribution.b,