  Recent studies have reported that annealing machines are capable of solving
combinatorial optimization problems with high accuracy. Annealing machines can
potentially be applied to score-based Bayesian network structure learning.
However, the bit capacity of an annealing machine is currently limited. To
utilize the annealing technology, converting score-based learning problems into
quadratic unconstrained binary optimizations within the bit capacity is
necessary. In this paper, we propose an efficient conversion method with the
advanced identification of candidate parent sets and their decomposition. We
also provide an integer programming problem to find the decomposition that
minimizes the number of required bits. Experimental results on $7$ benchmark
datasets with variables from $75$ to $223$ show that our approach requires less
bits than the $100$K bit capacity of the fourth-generation Fujitsu Digital
Annealer, a fully coupled annealing machine developed with semiconductor
technology. Moreover, we demonstrate that the Digital Annealer with our
conversion method outperforms existing algorithms on score maximization. These
results highlight the utility of annealing processors in learning Bayesian
networks.
