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:2204.03526 · Quantum Information and Computation

Reconstructing Bayesian networks on a quantum annealer

Enrico Zardini, Massimo Rizzoli, Sebastiano Dissegna, Enrico Blanzieri, Davide Pastorello

Published Oct 27, 2022• 2 citations
arXivHTMLPDF

Abstract

Bayesian networks are widely used probabilistic graphical models, whose structure is hard to learn starting from the generated data. O'Gorman et al. have proposed an algorithm to encode this task, i.e., the Bayesian network structure learning (BNSL), into a form that can be solved through quantum annealing, but they have not provided an experimental evaluation of it. In this paper, we present (i) an implementation in Python of O'Gorman's algorithm, (ii) a divide et impera approach that allows addressing BNSL problems of larger sizes in order to overcome the limitations imposed by the current architectures, and (iii) their empirical evaluation. Specifically, several problems with an increasing number of variables have been used in the experiments. The results have shown the effectiveness of O'Gorman's formulation for BNSL instances of small sizes, and the superiority of the divide et impera approach on the direct execution of O'Gorman's algorithm.

DOI
10.26421/qic22.15-16-4

Related papers

Quantum Speedups for Bayesian Network Structure Learning

Juha Harviainen, Kseniya Rychkova, Koivisto, Mikko

The Bayesian network structure learning (BNSL) problem asks for a directed acyclic graph that maximizes a given score function. For networks with $n$ nodes, the fastest known algorithms run in time $O(2^n n^2)$ in the worst case, with no improvement in the asymptotic bound for two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a polynomial quantum speedup, that is, whether the problem can be solved by a quantum algorithm in time $O(c^n)$ for some constant $c$ less than $2$. We answer the question in the affirmative by giving two algorithms achieving $c \le 1.817$ and $c \le 1.982$ assuming the number of potential parent sets is, respectively, subexponential and $O(1.453^n)$. Both algorithms assume the availability of a quantum random access memory. We also prove that one presumably cannot lower the base $2$ for any classical algorithm, as that would refute the strong exponential time hypothesis.

arXiv:2305.19673•Työväentutkimus Vuosikirja•May 31, 2023•0 citations

Quantum-Inspired Optimization of Large-Scale Bayesian Networks

Jincheng Zhang

This paper investigates the application of quantum-inspired optimization techniques to the problem of inference and learning within large-scale Bayesian Networks (BNs). Traditional Bayesian Network learning and inference methods often struggle with scalability, particularly as the number of nodes and dependencies increases. We propose leveraging concepts from quantum algorithms, specifically drawing inspiration from quantum annealing and quantum Monte Carlo methods, to efficiently explore the complex search space associated with BN structure optimization and parameter estimation. The core idea is to mimic the exploration capabilities of quantum systems to accelerate the process. The proposed methodology aims to improve the efficiency of BN learning and inference, potentially unlocking new capabilities for probabilistic reasoning in complex systems. This work presents a theoretical framework and a conceptual outline for such an approach, laying the groundwork for future research and experimentation. The effectiveness of this approach is predicated on the ability to translate the inherent parallelism of quantum algorithms into an efficient optimization strategy for Bayesian Networks.

•Aug 28, 2026•0 citations

Quantum-Enhanced Optimization for Bayesian Networks

Jincheng Zhang

Quantum-enhanced optimization is a burgeoning field with the potential to revolutionize various computational tasks, particularly those involving complex data structures like Bayesian networks. This paper explores the application of quantum optimization algorithms to Bayesian network inference, aiming to enhance efficiency and accuracy. We investigate the integration of quantum annealing and quantum approximate optimization algorithms to address the inherent computational challenges associated with Bayesian network modeling. This work presents a novel methodology for leveraging quantum mechanics to accelerate the process of parameter estimation and structure exploration within Bayesian networks. The core claim is that this integration will yield significant improvements in inference performance compared to classical methods, especially for large and complex networks. This paper details the theoretical framework, experimental validation, and initial results demonstrating the feasibility and potential impact of this approach.

•Aug 31, 2026•0 citations

Quantum-Inspired Bayesian Network Structure Learning via Entangled State Sampling

Jincheng Zhang

Bayesian network structure learning aims to discover the probabilistic relationships between variables from data. Traditional methods often struggle with high-dimensional data and computational complexity. This paper proposes a novel approach to Bayesian network structure learning inspired by quantum mechanical principles, specifically, the concept of entangled states. We introduce an algorithm that simulates the sampling of entangled states to explore the space of possible network structures. The probability of a particular structure is determined by the degree of entanglement observed during the simulation. This approach offers the potential for significantly improved efficiency and accuracy, particularly when dealing with complex datasets. The key idea is to treat network structure learning as a search problem where the "entanglement" represents the degree of correlation between different parts of the search space. We define the core metrics and algorithms used in this process, emphasizing the probabilistic interpretation of the entanglement measure. This work represents a significant departure from conventional Bayesian network learning, introducing a quantum-inspired perspective to enhance structure discovery.

•Sep 1, 2026•0 citations

Adaptive Learning for Quantum Linear Regression

Costantino Carugno, Maurizio Ferrari Dacrema, Paolo Cremonesi

The recent availability of quantum annealers as cloud-based services has enabled new ways to handle machine learning problems, and several relevant algorithms have been adapted to run on these devices. In a recent work, linear regression was formulated as a quadratic binary optimization problem that can be solved via quantum annealing. Although this approach promises a computational time advantage for large datasets, the quality of the solution is limited by the necessary use of a precision vector, used to approximate the real-numbered regression coefficients in the quantum formulation. In this work, we focus on the practical challenge of improving the precision vector encoding: instead of setting an array of generic values equal for all coefficients, we allow each one to be expressed by its specific precision, which is tuned with a simple adaptive algorithm. This approach is evaluated on synthetic datasets of increasing size, and linear regression is solved using the D-Wave Advantage quantum annealer, as well as classical solvers. To the best of our knowledge, this is the largest dataset ever evaluated for linear regression on a quantum annealer. The results show that our formulation is able to deliver improved solution quality in all instances, and could better exploit the potential of current quantum devices.

arXiv:2408.02833•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•2 citations

Bayesian Networks based Hybrid Quantum-Classical Machine Learning Approach to Elucidate Gene Regulatory Pathways

Radhakrishnan Balu, Ajinkya Borle

We report a scalable hybrid quantum-classical machine learning framework to build Bayesian networks (BN) that captures the conditional dependence and causal relationships of random variables. The generation of a BN consists of finding a directed acyclic graph (DAG) and the associated joint probability distribution of the nodes consistent with a given dataset. This is a combinatorial problem of structural learning of the underlying graph, starting from a single node and building one arc at a time, that fits a given ensemble using maximum likelihood estimators (MLE). It is cast as an optimization problem that consists of a scoring step performed on a classical computer, penalties for acyclicity and number of parents allowed constraints, and a search step implemented using a quantum annealer. We have assumed uniform priors in deriving the Bayesian network that can be relaxed by formulating the problem as an estimation Dirichlet parameters. We demonstrate the utility of the framework by applying to the problem of elucidating the gene regulatory network for the MAPK/Raf pathway in human T-cells using proteomics data where the concentration of proteins, nodes of the BN, are interpreted as probabilities.

arXiv:1901.10557•Jan 23, 2019•2 citations
Bayesian networks are widely used probabilistic graphical models, whose structure is hard to learn starting from the generated data. O'Gorman et al. have proposed an algorithm to encode this task, i.e., the Bayesian network structure learning (BNSL), into a form that can be solved through quantum annealing, but they have not provided an experimental evaluation of it. In this paper, we present (i) an implementation in Python of O'Gorman's algorithm, (ii) a divide et impera approach that allows addressing BNSL problems of larger sizes in order to overcome the limitations imposed by the current architectures, and (iii) their empirical evaluation. Specifically, several problems with an increasing number of variables have been used in the experiments. The results have shown the effectiveness of O'Gorman's formulation for BNSL instances of small sizes, and the superiority of the divide et impera approach on the direct execution of O'Gorman's algorithm.
The Bayesian network structure learning (BNSL) problem asks for a directed acyclic graph that maximizes a given score function. For networks with nnn nodes, the fastest known algorithms run in time O(2nn2)O(2^n n^2)O(2nn2) in the worst case, with no improvement in the asymptotic bound for two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a polynomial quantum speedup, that is, whether the problem can be solved by a quantum algorithm in time O(cn)O(c^n)O(cn) for some constant ccc less than 222. We answer the question in the affirmative by giving two algorithms achieving c≤1.817c \le 1.817c≤1.817 and c≤1.982c \le 1.982c≤1.982 assuming the number of potential parent sets is, respectively, subexponential and O(1.453n)O(1.453^n)O(1.453n). Both algorithms assume the availability of a quantum random access memory. We also prove that one presumably cannot lower the base 222 for any classical algorithm, as that would refute the strong exponential time hypothesis.
This paper investigates the application of quantum-inspired optimization techniques to the problem of inference and learning within large-scale Bayesian Networks (BNs). Traditional Bayesian Network learning and inference methods often struggle with scalability, particularly as the number of nodes and dependencies increases. We propose leveraging concepts from quantum algorithms, specifically drawing inspiration from quantum annealing and quantum Monte Carlo methods, to efficiently explore the complex search space associated with BN structure optimization and parameter estimation. The core idea is to mimic the exploration capabilities of quantum systems to accelerate the process. The proposed methodology aims to improve the efficiency of BN learning and inference, potentially unlocking new capabilities for probabilistic reasoning in complex systems. This work presents a theoretical framework and a conceptual outline for such an approach, laying the groundwork for future research and experimentation. The effectiveness of this approach is predicated on the ability to translate the inherent parallelism of quantum algorithms into an efficient optimization strategy for Bayesian Networks.
Quantum-enhanced optimization is a burgeoning field with the potential to revolutionize various computational tasks, particularly those involving complex data structures like Bayesian networks. This paper explores the application of quantum optimization algorithms to Bayesian network inference, aiming to enhance efficiency and accuracy. We investigate the integration of quantum annealing and quantum approximate optimization algorithms to address the inherent computational challenges associated with Bayesian network modeling. This work presents a novel methodology for leveraging quantum mechanics to accelerate the process of parameter estimation and structure exploration within Bayesian networks. The core claim is that this integration will yield significant improvements in inference performance compared to classical methods, especially for large and complex networks. This paper details the theoretical framework, experimental validation, and initial results demonstrating the feasibility and potential impact of this approach.
Bayesian network structure learning aims to discover the probabilistic relationships between variables from data. Traditional methods often struggle with high-dimensional data and computational complexity. This paper proposes a novel approach to Bayesian network structure learning inspired by quantum mechanical principles, specifically, the concept of entangled states. We introduce an algorithm that simulates the sampling of entangled states to explore the space of possible network structures. The probability of a particular structure is determined by the degree of entanglement observed during the simulation. This approach offers the potential for significantly improved efficiency and accuracy, particularly when dealing with complex datasets. The key idea is to treat network structure learning as a search problem where the "entanglement" represents the degree of correlation between different parts of the search space. We define the core metrics and algorithms used in this process, emphasizing the probabilistic interpretation of the entanglement measure. This work represents a significant departure from conventional Bayesian network learning, introducing a quantum-inspired perspective to enhance structure discovery.
The recent availability of quantum annealers as cloud-based services has enabled new ways to handle machine learning problems, and several relevant algorithms have been adapted to run on these devices. In a recent work, linear regression was formulated as a quadratic binary optimization problem that can be solved via quantum annealing. Although this approach promises a computational time advantage for large datasets, the quality of the solution is limited by the necessary use of a precision vector, used to approximate the real-numbered regression coefficients in the quantum formulation. In this work, we focus on the practical challenge of improving the precision vector encoding: instead of setting an array of generic values equal for all coefficients, we allow each one to be expressed by its specific precision, which is tuned with a simple adaptive algorithm. This approach is evaluated on synthetic datasets of increasing size, and linear regression is solved using the D-Wave Advantage quantum annealer, as well as classical solvers. To the best of our knowledge, this is the largest dataset ever evaluated for linear regression on a quantum annealer. The results show that our formulation is able to deliver improved solution quality in all instances, and could better exploit the potential of current quantum devices.
We report a scalable hybrid quantum-classical machine learning framework to build Bayesian networks (BN) that captures the conditional dependence and causal relationships of random variables. The generation of a BN consists of finding a directed acyclic graph (DAG) and the associated joint probability distribution of the nodes consistent with a given dataset. This is a combinatorial problem of structural learning of the underlying graph, starting from a single node and building one arc at a time, that fits a given ensemble using maximum likelihood estimators (MLE). It is cast as an optimization problem that consists of a scoring step performed on a classical computer, penalties for acyclicity and number of parents allowed constraints, and a search step implemented using a quantum annealer. We have assumed uniform priors in deriving the Bayesian network that can be relaxed by formulating the problem as an estimation Dirichlet parameters. We demonstrate the utility of the framework by applying to the problem of elucidating the gene regulatory network for the MAPK/Raf pathway in human T-cells using proteomics data where the concentration of proteins, nodes of the BN, are interpreted as probabilities.