Quantum Enhanced Inference in Markov Logic Networks
arXiv:1611.08104 · doi:10.1038/srep45672
Abstract
Markov logic networks (MLNs) reconcile two opposing schools in machine learning and artificial intelligence: causal networks, which account for uncertainty extremely well, and first-order logic, which allows for formal deduction. An MLN is essentially a first-order logic template to generate Markov networks. Inference in MLNs is probabilistic and it is often performed by approximate methods such as Markov chain Monte Carlo (MCMC) Gibbs sampling. An MLN has many regular, symmetric structures that can be exploited at both first-order level and in the generated Markov network. We analyze the graph structures that are produced by various lifting methods and investigate the extent to which quantum protocols can be used to speed up Gibbs sampling with state preparation and measurement schemes. We review different such approaches, discuss their advantages, theoretical limitations, and their appeal to implementations. We find that a straightforward application of a recent result yields exponential speedup compared to classical heuristics in approximate probabilistic inference, thereby demonstrating another example where advanced quantum resources can potentially prove useful in machine learning.
arXiv comment8 pages, 1 figure
References in corpus (33)
- Quantum Machine Learning
- Quantum Amplitude Amplification and Estimation
- An introduction to quantum machine learning
- Quantum annealing with more than one hundred qubits
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Unconditional quantum teleportation between distant solid-state qubits
- Nanophotonic quantum phase switch with a single atom
- Grover Algorithm with zero theoretical failure rate
- A Quantum Gate between a Flying Optical Photon and a Single Trapped Atom
- Quantum Metropolis Sampling
- The General Quantum Interference Principle and the Duality Computer
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
- Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
- The problem of equilibration and the computation of correlation functions on a quantum computer
- Thermalization in Nature and on a Quantum Computer
- Quantum Simulations of Classical Annealing Processes
- Application of Quantum Annealing to Training of Deep Neural Networks
- Counting Belief Propagation
- Probabilistic Theorem Proving
- Universal hyperparallel hybrid photonic quantum gates with dipole-induced transparency in the weak-coupling regime
- Speed-up via Quantum Sampling
- Bayesian Network Structure Learning Using Quantum Annealing
- Quantum speedup of classical mixing processes
- Preparing thermal states of quantum systems by dimension reduction
- Skolemization for Weighted First-Order Model Counting
- Hyper-parallel Toffoli gate on three-photon system with two degrees of freedom assisted by single-sided optical microcavities
- Quantum Speed-up for Approximating Partition Functions
- Advances in quantum machine learning
- Markov Chains on Orbits of Permutation Groups
- Quantum Simulated Annealing
- Quantum Algorithm for Preparing Thermal Gibbs States - Detailed Analysis
- Quantum state preparation by phase randomization
- Quantum Gibbs Sampling Using Szegedy Operators
Cited by in corpus (10)
- Quantum Machine Learning
- Quantum machine learning in feature Hilbert spaces
- A generative modeling approach for benchmarking and training shallow quantum circuits
- Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- Quantum-assisted Helmholtz machines: A quantum-classical deep learning framework for industrial datasets in near-term devices
- Variational inference with a quantum computer
- Machine learning \& artificial intelligence in the quantum domain
- Entanglement-based quantum deep learning
- Theory of Quantum Path Computing with Fourier Optics and Future Applications for Quantum Supremacy, Neural Networks and Nonlinear Schrödinger Equations