2021/09/02 by Liming Zhao, Zhao, Liming, Siyi Yang +3
Computer Science · #Algorithms and Data Compression #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2109.01014
openalex publication_date 2021/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.