Bayesian Network Structure Learning Using Quantum Annealing
  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 $\mathcal O(n^2)$
qubits for $n$ Bayesian network variables. Furthermore, we prove lower bounds
on the necessary weighting of these penalty terms. The logical structure
resulting from the mapping has the appealing property that it is
instance-independent for a given number of Bayesian network variables, as well
as being independent of the number of data cases.
