Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.01014

Quantum algorithm for structure learning of Markov Random Fields

Liming Zhao, Siyi Yang, Patrick Rebentrost

Published Sep 2, 2021• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2109.01014

Related papers

Quantum algorithm for Markov random fields structure learning

Liming Zhao, Ming-Xing Luo, Lin‐Chun Wan

Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. 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. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.

Physica Scripta•Jun 26, 2025•1 citation

Quantum algorithm for Markov Random Fields structure learning by information theoretic properties

Liming Zhao, Lin‐Chun Wan, Luo, Ming-Xing

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.

arXiv:2208.11382•Aug 24, 2022•0 citations

Learning Restricted Boltzmann Machines with greedy quantum search

Liming Zhao, Agrawal, Aman, Patrick Rebentrost

Restricted Boltzmann Machines (RBMs) are widely used probabilistic undirected graphical models with visible and latent nodes, playing an important role in statistics and machine learning. The task of structure learning for RBMs involves inferring the underlying graph by using samples from the visible nodes. Specifically, learning the two-hop neighbors of each visible node allows for the inference of the graph structure. Prior research has addressed the structure learning problem for specific classes of RBMs, namely ferromagnetic and locally consistent RBMs. In this paper, we extend the scope to the quantum computing domain and propose corresponding quantum algorithms for this problem. Our study demonstrates that the proposed quantum algorithms yield a polynomial speedup compared to the classical algorithms for learning the structure of these two classes of RBMs.

arXiv:2309.14196•Sep 25, 2023•0 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

•Jul 24, 2020•0 citations

Quantum algorithms for machine learning and optimization

Tongyang Li

The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.

•Jan 1, 2020•2 citations

Quantum Speedups for Bayesian Network Structure Learning

Juha Harviainen, Kseniya Rychkova, Koivisto, Mikko

The Bayesian network structure learning (BNSL) problem asks for a directed acyclic graph that maximizes a given score function. For networks with $n$ nodes, the fastest known algorithms run in time $O(2^n n^2)$ in the worst case, with no improvement in the asymptotic bound for two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a polynomial quantum speedup, that is, whether the problem can be solved by a quantum algorithm in time $O(c^n)$ for some constant $c$ less than $2$. We answer the question in the affirmative by giving two algorithms achieving $c \le 1.817$ and $c \le 1.982$ assuming the number of potential parent sets is, respectively, subexponential and $O(1.453^n)$. Both algorithms assume the availability of a quantum random access memory. We also prove that one presumably cannot lower the base $2$ for any classical algorithm, as that would refute the strong exponential time hypothesis.

arXiv:2305.19673•Työväentutkimus Vuosikirja•May 31, 2023•0 citations
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.
Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. 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. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.
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 rrr-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.
Restricted Boltzmann Machines (RBMs) are widely used probabilistic undirected graphical models with visible and latent nodes, playing an important role in statistics and machine learning. The task of structure learning for RBMs involves inferring the underlying graph by using samples from the visible nodes. Specifically, learning the two-hop neighbors of each visible node allows for the inference of the graph structure. Prior research has addressed the structure learning problem for specific classes of RBMs, namely ferromagnetic and locally consistent RBMs. In this paper, we extend the scope to the quantum computing domain and propose corresponding quantum algorithms for this problem. Our study demonstrates that the proposed quantum algorithms yield a polynomial speedup compared to the classical algorithms for learning the structure of these two classes of RBMs.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.
The Bayesian network structure learning (BNSL) problem asks for a directed acyclic graph that maximizes a given score function. For networks with nnn nodes, the fastest known algorithms run in time O(2nn2)O(2^n n^2)O(2nn2) in the worst case, with no improvement in the asymptotic bound for two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a polynomial quantum speedup, that is, whether the problem can be solved by a quantum algorithm in time O(cn)O(c^n)O(cn) for some constant ccc less than 222. We answer the question in the affirmative by giving two algorithms achieving c≤1.817c \le 1.817c≤1.817 and c≤1.982c \le 1.982c≤1.982 assuming the number of potential parent sets is, respectively, subexponential and O(1.453n)O(1.453^n)O(1.453n). Both algorithms assume the availability of a quantum random access memory. We also prove that one presumably cannot lower the base 222 for any classical algorithm, as that would refute the strong exponential time hypothesis.