Bayesian Network Structure Learning using Quantum Annealing

Bryan O'Gorman
Alejandro Perdomo-Ortiz
Alán Aspuru-Guzik
Vadim Smelyanskiy
European Physical Journal: Special Topics, 224 (2015), pp. 163-188

Abstract

We introduce a method for the problem of learning the structure of a Bayesian network using the quantum adiabatic algorithm. We do so by introducing an efficient reformulation of a standard posterior-probability scoring function on graphs as a pseudo-Boolean function, which is equivalent to a system of 2-body Ising spins, as well as suitable penalty terms for enforcing the constraints necessary for the reformulation; our proposed method requires