Quantum Speedups for Bayesian Network Structure Learning
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 \leq 1.817$ and $c \leq
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.
Juha Harviainen Kseniya Rychkova Mikko Koivisto