  Probabilistic graphical models play a crucial role in machine learning and
have wide applications in various fields. One pivotal subset is undirected
graphical models, also known as Markov random fields. In this work, we
investigate the structure learning methods of Markov random fields on quantum
computers. We propose a quantum algorithm for structure learning of an $r$-wise
Markov Random Field with a bounded degree underlying graph, based on a nearly
optimal classical greedy algorithm. The quantum algorithm provides a polynomial
speed-up over the classical counterpart in terms of the number of variables.
Our work demonstrates the potential merits of quantum computation over
classical computation in solving some problems in machine learning.
