  Markov random fields (MRFs) appear in many problems in machine learning and
statistics. From a computational learning theory point of view, a natural
problem of learning MRFs arises: given samples from an MRF from a restricted
class, learn the structure of the MRF, that is the neighbors of each node of
the underlying graph. In this work, we start at a known near-optimal classical
algorithm for this learning problem and develop a modified classical algorithm.
This classical algorithm retains the run time and guarantee of the previous
algorithm and enables the use of quantum subroutines. Adapting a previous
quantum algorithm, the Quantum Sparsitron, we provide a polynomial quantum
speedup in terms of the number of variables for learning the structure of an
MRF, if the MRF has bounded degree.
