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:2305.19673 · Työväentutkimus Vuosikirja

Quantum Speedups for Bayesian Network Structure Learning

Juha Harviainen, Kseniya Rychkova, Koivisto, Mikko

Published May 31, 2023• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2305.19673

Related papers

Can graph properties have exponential quantum speedup?

Andrew M. Childs, Daochen Wang

Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

arXiv:2001.10520•Jan 28, 2020•2 citations

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

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 Speedups for Polynomial-Time Dynamic Programming Algorithms

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista +2 more

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem $\mathcal P$ and an instance $I$ of $\mathcal P$, such a speedup can be expressed in terms of the average degree $δ$ of the dependency digraph $G_{\mathcal{P}}(I)$ of $I$, determined by a recursive formulation of $\mathcal P$. The nodes of this graph are the subproblems of $\mathcal P$ induced by $I$ and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in $\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)$ time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted $n$-vertex digraph with $m$ edges that runs in $\tilde{O}(n\sqrt{nm})$ time, which improves the best known classical upper bound when $m \in Ω(n^{1.4})$.

arXiv:2507.00823•Jul 1, 2025•0 citations

Quantum inference on Bayesian networks

Guang Hao Low, Theodore J. Yoder, Isaac L. Chuang

Performing exact inference on Bayesian networks is known to be $#P$-hard. Typically approximate inference techniques are used instead to sample from the distribution on query variables given the values $e$ of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on $n$ variables with at most $m$ parents per node in time $O(nmP{(e)}^{\ensuremath{-}1})$, depending critically on $P(e)$, the probability that the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $O(n{2}^{m}P{(e)}^{\ensuremath{-}\frac{1}{2}})$ time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized---we count primitive operations and require no blackbox oracle queries.

arXiv:1402.7359•Physical Review A•Jun 13, 2014•109 citations

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Caroppo, Susanna, Da Lozzo, Giordano, Giuseppe Di Battista +2 more

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).

•Jan 1, 2025•0 citations
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.
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity RRR of any graph property P\mathcal{P}P has R(P)=O(Q(P)6)R(\mathcal{P}) = O(Q(\mathcal{P})^{6})R(P)=O(Q(P)6), where QQQ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l)R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})R(P)=O(Q(P)3l) for any lll-uniform hypergraph property P\mathcal{P}P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
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.
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.
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P\mathcal PP and an instance III of P\mathcal PP, such a speedup can be expressed in terms of the average degree δδδ of the dependency digraph GP(I)G_{\mathcal{P}}(I)GP​(I) of III, determined by a recursive formulation of P\mathcal PP. The nodes of this graph are the subproblems of P\mathcal PP induced by III and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in O~(∣V(GP(I))∣δ)\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)O~(∣V(GP​(I))∣δ​) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted nnn-vertex digraph with mmm edges that runs in O~(nnm)\tilde{O}(n\sqrt{nm})O~(nnm​) time, which improves the best known classical upper bound when m∈Ω(n1.4)m \in Ω(n^{1.4})m∈Ω(n1.4).
Performing exact inference on Bayesian networks is known to be $#P$-hard. Typically approximate inference techniques are used instead to sample from the distribution on query variables given the values eee of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on nnn variables with at most mmm parents per node in time $O(nmP{(e)}^{\ensuremath{-}1})$, depending critically on P(e)P(e)P(e), the probability that the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $O(n{2}^{m}P{(e)}^{\ensuremath{-}\frac{1}{2}})$ time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized---we count primitive operations and require no blackbox oracle queries.
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).