Reconstructing Bayesian networks on a
quantum
annealer
(pp1320-1350)
Enrico
Zardini, Massimo Rizzoli, Sebastiano Dissegna,
Enrico
Blanzieri, and Davide Pastorello
doi:
https://doi.org/10.26421/QIC22.15-16-4
Abstracts:
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.
Key words:
Bayesian Network
Structure Learning, Quantum Annealing, Quantum Software, Empirical
Evaluation |