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

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.

arXiv:2208.11382•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•2 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•8 citations

Anomaly detection speed-up by quantum restricted Boltzmann machines

Lorenzo Moro, Enrico Prati

Abstract Quantum machine learning promises to revolutionize traditional machine learning by efficiently addressing hard tasks for classical computation. While claims of quantum speed-up have been announced for gate-based quantum computers and photon-based boson samplers, demonstration of an advantage by adiabatic quantum annealers (AQAs) is open. Here we quantify the computational cost and the performance of restricted Boltzmann machines (RBMs), a widely investigated machine learning model, by classical and quantum annealing. Despite the lower computational complexity of the quantum RBM being lost due to physical implementation overheads, a quantum speed-up may arise as a reduction by orders of magnitude of the computational time. By employing real-world cybersecurity datasets, we observe that the negative phase on sufficiently challenging tasks is computed up to 64 times faster by AQAs during the exploitation phase. Therefore, although a quantum speed-up highly depends on the problem’s characteristics, it emerges in existing hardware on real-world data.

Communications Physics•Sep 23, 2023•28 citations

Software techniques for training restricted Boltzmann machines on size-constrained quantum annealing hardware

Ilmo Salmenperä, Jukka K. Nurminen

Restricted Boltzmann machines are common machine learning models that can utilize quantum annealing devices in their training processes as quantum samplers. While this approach has shown promise as an alternative to classical sampling methods, the limitations of quantum annealing hardware, such as the number of qubits and the lack of connectivity between the qubits, still pose a barrier to wide-scale adoption. We propose the use of multiple software techniques such as dropout method, passive labeling, and parallelization techniques for addressing these hardware limitations. The study found that using these techniques along with quantum sampling showed comparable results to its classical counterparts in certain contexts, while in others the increased complexity of the sampling process hindered the performance of the trained models. This means that further research into the behavior of quantum sampling needs to be done to apply quantum annealing to training tasks of more complicated RBM models.

Frontiers in Computer Science•Oct 16, 2023•3 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.
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.
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.
Abstract Quantum machine learning promises to revolutionize traditional machine learning by efficiently addressing hard tasks for classical computation. While claims of quantum speed-up have been announced for gate-based quantum computers and photon-based boson samplers, demonstration of an advantage by adiabatic quantum annealers (AQAs) is open. Here we quantify the computational cost and the performance of restricted Boltzmann machines (RBMs), a widely investigated machine learning model, by classical and quantum annealing. Despite the lower computational complexity of the quantum RBM being lost due to physical implementation overheads, a quantum speed-up may arise as a reduction by orders of magnitude of the computational time. By employing real-world cybersecurity datasets, we observe that the negative phase on sufficiently challenging tasks is computed up to 64 times faster by AQAs during the exploitation phase. Therefore, although a quantum speed-up highly depends on the problem’s characteristics, it emerges in existing hardware on real-world data.
Restricted Boltzmann machines are common machine learning models that can utilize quantum annealing devices in their training processes as quantum samplers. While this approach has shown promise as an alternative to classical sampling methods, the limitations of quantum annealing hardware, such as the number of qubits and the lack of connectivity between the qubits, still pose a barrier to wide-scale adoption. We propose the use of multiple software techniques such as dropout method, passive labeling, and parallelization techniques for addressing these hardware limitations. The study found that using these techniques along with quantum sampling showed comparable results to its classical counterparts in certain contexts, while in others the increased complexity of the sampling process hindered the performance of the trained models. This means that further research into the behavior of quantum sampling needs to be done to apply quantum annealing to training tasks of more complicated RBM models.