2022/08/24 by Liming Zhao, Zhao, Liming, Lin-chun Wan +3
Computer Science · #Bayesian Modeling and Causal Inference #Error Correcting Code Techniques #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2208.11382
openalex publication_date 2022/08/24 · openalex created_date 2022/08/27 · openalex updated_date 2026/07/28
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.