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

• URL: http://arxiv.org/abs/2208.11382v1
• Date: Wed, 24 Aug 2022 09:00:56 GMT
• Title: Quantum algorithm for Markov Random Fields structure learning by information theoretic properties
• Authors: Liming Zhao, Lin-chun Wan, Ming-Xing Luo
• Abstract summary: We propose a quantum algorithm for structure learning of an $r$-wise Markov Random Field on quantum computers. Our work demonstrates the potential merits of quantum computation over classical computation in solving some problems in machine learning.
• Score: 5.263910852465186
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Hybrid Quantum-Classical Machine Learning with String Diagrams [49.1574468325115]
  This paper develops a formal framework for describing hybrid algorithms in terms of string diagrams. A notable feature of our string diagrams is the use of functor boxes, which correspond to a quantum-classical interfaces.
  arXiv  Detail & Related papers  (2024-07-04T06:37:16Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms [0.0]
  We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
  arXiv  Detail & Related papers  (2023-04-11T02:09:13Z)
• MAQA: A Quantum Framework for Supervised Learning [2.064612766965483]
  This work proposes a universal, efficient framework that can reproduce the output of a plethora of classical supervised machine learning algorithms. The proposed framework is named Multiple Aggregator Quantum Algorithm (MAQA) due to its capability to combine multiple and diverse functions. As a second meaningful addition, we discuss the adoption of the proposed framework as hybrid quantum-classical and fault-tolerant quantum algorithm.
  arXiv  Detail & Related papers  (2023-03-20T11:18:22Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• On Hitting Times for General Quantum Markov Processes [0.0]
  We use the density-matrix formalism to define a quantum Markov chain model which directly generalizes classical walks. We show that a common tools such as hitting times can be computed with a similar formula as the one found in the classical theory.
  arXiv  Detail & Related papers  (2022-10-18T22:20:27Z)
• Quantum algorithm for structure learning of Markov Random Fields [6.174721516017139]
  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.
  arXiv  Detail & Related papers  (2021-09-02T15:22:38Z)
• Quantum Machine Learning For Classical Data [0.0]
  We study the intersection of quantum computing and supervised machine learning algorithms. In particular, we investigate what extent quantum computers can be used to accelerate supervised machine learning algorithms.
  arXiv  Detail & Related papers  (2021-05-08T12:11:44Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.