Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2309.14196

Learning Restricted Boltzmann Machines with greedy quantum search

Liming Zhao, Agrawal, Aman, Patrick Rebentrost

Published Sep 25, 2023• 0 citations
arXivHTMLPDF

Abstract

Restricted Boltzmann Machines (RBMs) are widely used probabilistic undirected graphical models with visible and latent nodes, playing an important role in statistics and machine learning. The task of structure learning for RBMs involves inferring the underlying graph by using samples from the visible nodes. Specifically, learning the two-hop neighbors of each visible node allows for the inference of the graph structure. Prior research has addressed the structure learning problem for specific classes of RBMs, namely ferromagnetic and locally consistent RBMs. In this paper, we extend the scope to the quantum computing domain and propose corresponding quantum algorithms for this problem. Our study demonstrates that the proposed quantum algorithms yield a polynomial speedup compared to the classical algorithms for learning the structure of these two classes of RBMs.

DOI
10.48550/arxiv.2309.14196

Related papers

Quantum algorithm for Markov Random Fields structure learning by information theoretic properties

Liming Zhao, Lin‐Chun Wan, Luo, Ming-Xing

Probabilistic graphical models play a crucial role in machine learning and have wide applications in various fields. One pivotal subset is undirected graphical models, also known as Markov random fields. In this work, we investigate the structure learning methods of Markov random fields on quantum computers. We propose a quantum algorithm for structure learning of an $r$-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. The quantum algorithm provides a polynomial speed-up over the classical counterpart in terms of the number of variables. Our work demonstrates the potential merits of quantum computation over classical computation in solving some problems in machine learning.

arXiv:2208.11382•Aug 24, 2022•0 citations

Quantum algorithm for Markov random fields structure learning

Liming Zhao, Ming-Xing Luo, Lin‐Chun Wan

Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. We propose a quantum algorithm for structure learning of an r-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.

Physica Scripta•Jun 26, 2025•1 citation

Quantum algorithm for structure learning of Markov Random Fields

Liming Zhao, Siyi Yang, Patrick Rebentrost

Markov random fields (MRFs) appear in many problems in machine learning and statistics. From a computational learning theory point of view, a natural problem of learning MRFs arises: given samples from an MRF from a restricted class, learn the structure of the MRF, that is the neighbors of each node of the underlying graph. In this work, we start at a known near-optimal classical algorithm for this learning problem and develop a modified classical algorithm. This classical algorithm retains the run time and guarantee of the previous algorithm and enables the use of quantum subroutines. Adapting a previous quantum algorithm, the Quantum Sparsitron, we provide a polynomial quantum speedup in terms of the number of variables for learning the structure of an MRF, if the MRF has bounded degree.

arXiv:2109.01014•Sep 2, 2021•0 citations

Machine learning in quantum computers via general Boltzmann Machines: Generative and Discriminative training through annealing.

Siddhartha Srivastava, Veera Sundararaghavan

We present a Hybrid-Quantum-classical method for learning Boltzmann machines (BM) for generative and discriminative tasks. Boltzmann machines are undirected graphs that form the building block of many learning architectures such as Restricted Boltzmann machines (RBM's) and Deep Boltzmann machines (DBM's). They have a network of visible and hidden nodes where the former are used as the reading sites while the latter are used to manipulate the probability of the visible states. BM's are versatile machines that can be used for both learning distributions as a generative task as well as for performing classification or function approximation as a discriminative task. We show that minimizing KL-divergence works best for training BM for applications of function approximation. In our approach, we use Quantum annealers for sampling Boltzmann states. These states are used to approximate gradients in a stochastic gradient descent scheme. The approach is used to demonstrate logic circuits in the discriminative sense and a specialized two-phase distribution using generative BM.

•Feb 3, 2020•4 citations

A complete restricted Boltzmann machine on an adiabatic quantum computer

Lorenzo Rocutto, Enrico Prati

Boltzmann Machines constitute a paramount class of neural networks for unsupervised learning and recommendation systems. Their bipartite version, called Restricted Boltzmann Machine (RBM), is the most developed because of its satisfactory trade-off between computability on classical computers and computational power. Though the diffusion of RBMs is quite limited as their training remains hard. Recently, a renewed interest has emerged as Adiabatic Quantum Computers (AQCs), which suggest a potential increase of the training speed with respect to conventional hardware. Due to the limited number of connections among the qubits forming the graph of existing hardware, associating one qubit per node of the neural network implies an incomplete graph. Thanks to embedding techniques, we developed a complete graph connecting nodes constituted by virtual qubits. The complete graph outperforms previous implementations based on incomplete graphs. Despite the fact that the learning rate per epoch is still slower with respect to a classical machine, the advantage is expected by the increase of number of nodes which impacts on the classical computational time but not on the quantum hardware based computation.

International Journal of Quantum Information•Jun 1, 2021•13 citations

Provable learning of quantum states with graphical models

Liming Zhao, Naixu Guo, Ming-Xing Luo +1 more

The complete learning of any unknown many-body systems requires a number of samples exponentially in the particle number. Several works consider subclasses of physical meaningful states such as stabilizer states or high-temperature Gibbs states that can be learned in polynomial sample complexity. Others consider to learn states under special assumptions, such as PAC learning and shadow tomography. In this work, we consider learning many-body systems that can be approximately represented by restricted Boltzmann machines (RBMs). We exhibit robustness results for efficient provable two-hop neighborhood learning method for ferromagnetic and locally consistent RBMs. We consider the L p norm as a distance measure, including both total variation distance and max-norm distance in the limit. We show that various quantum states can be learned with a sample complexity exponentially better than the naive state tomography. Our results establish a broader theoretical framework for the efficient learning of complex quantum many-body systems.

arXiv:2309.09235•Physical Review Research•Dec 8, 2025•0 citations
Restricted Boltzmann Machines (RBMs) are widely used probabilistic undirected graphical models with visible and latent nodes, playing an important role in statistics and machine learning. The task of structure learning for RBMs involves inferring the underlying graph by using samples from the visible nodes. Specifically, learning the two-hop neighbors of each visible node allows for the inference of the graph structure. Prior research has addressed the structure learning problem for specific classes of RBMs, namely ferromagnetic and locally consistent RBMs. In this paper, we extend the scope to the quantum computing domain and propose corresponding quantum algorithms for this problem. Our study demonstrates that the proposed quantum algorithms yield a polynomial speedup compared to the classical algorithms for learning the structure of these two classes of RBMs.
Probabilistic graphical models play a crucial role in machine learning and have wide applications in various fields. One pivotal subset is undirected graphical models, also known as Markov random fields. In this work, we investigate the structure learning methods of Markov random fields on quantum computers. We propose a quantum algorithm for structure learning of an rrr-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. The quantum algorithm provides a polynomial speed-up over the classical counterpart in terms of the number of variables. Our work demonstrates the potential merits of quantum computation over classical computation in solving some problems in machine learning.
Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. We propose a quantum algorithm for structure learning of an r-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.
Markov random fields (MRFs) appear in many problems in machine learning and statistics. From a computational learning theory point of view, a natural problem of learning MRFs arises: given samples from an MRF from a restricted class, learn the structure of the MRF, that is the neighbors of each node of the underlying graph. In this work, we start at a known near-optimal classical algorithm for this learning problem and develop a modified classical algorithm. This classical algorithm retains the run time and guarantee of the previous algorithm and enables the use of quantum subroutines. Adapting a previous quantum algorithm, the Quantum Sparsitron, we provide a polynomial quantum speedup in terms of the number of variables for learning the structure of an MRF, if the MRF has bounded degree.
We present a Hybrid-Quantum-classical method for learning Boltzmann machines (BM) for generative and discriminative tasks. Boltzmann machines are undirected graphs that form the building block of many learning architectures such as Restricted Boltzmann machines (RBM's) and Deep Boltzmann machines (DBM's). They have a network of visible and hidden nodes where the former are used as the reading sites while the latter are used to manipulate the probability of the visible states. BM's are versatile machines that can be used for both learning distributions as a generative task as well as for performing classification or function approximation as a discriminative task. We show that minimizing KL-divergence works best for training BM for applications of function approximation. In our approach, we use Quantum annealers for sampling Boltzmann states. These states are used to approximate gradients in a stochastic gradient descent scheme. The approach is used to demonstrate logic circuits in the discriminative sense and a specialized two-phase distribution using generative BM.
Boltzmann Machines constitute a paramount class of neural networks for unsupervised learning and recommendation systems. Their bipartite version, called Restricted Boltzmann Machine (RBM), is the most developed because of its satisfactory trade-off between computability on classical computers and computational power. Though the diffusion of RBMs is quite limited as their training remains hard. Recently, a renewed interest has emerged as Adiabatic Quantum Computers (AQCs), which suggest a potential increase of the training speed with respect to conventional hardware. Due to the limited number of connections among the qubits forming the graph of existing hardware, associating one qubit per node of the neural network implies an incomplete graph. Thanks to embedding techniques, we developed a complete graph connecting nodes constituted by virtual qubits. The complete graph outperforms previous implementations based on incomplete graphs. Despite the fact that the learning rate per epoch is still slower with respect to a classical machine, the advantage is expected by the increase of number of nodes which impacts on the classical computational time but not on the quantum hardware based computation.
The complete learning of any unknown many-body systems requires a number of samples exponentially in the particle number. Several works consider subclasses of physical meaningful states such as stabilizer states or high-temperature Gibbs states that can be learned in polynomial sample complexity. Others consider to learn states under special assumptions, such as PAC learning and shadow tomography. In this work, we consider learning many-body systems that can be approximately represented by restricted Boltzmann machines (RBMs). We exhibit robustness results for efficient provable two-hop neighborhood learning method for ferromagnetic and locally consistent RBMs. We consider the L p norm as a distance measure, including both total variation distance and max-norm distance in the limit. We show that various quantum states can be learned with a sample complexity exponentially better than the naive state tomography. Our results establish a broader theoretical framework for the efficient learning of complex quantum many-body systems.