# Quantum algorithm for structure learning of Markov Random Fields

arXiv: https://arxiv.org/abs/2109.01014 · HTML: https://mlsanity.com/paper/2109.01014/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2021.

## Built on by (most cited first, 1 of 1)

- [On Quantum Circuits for Discrete Graphical Models](https://mlsanity.com/paper/2206.00398/) (2022)

## Abstract (arXiv)

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.