PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Enhanced Inference in Markov Logic Networks

Peter Wittek, Christian Gogolin

arXiv:1611.08104v1stat.MLcs.AIquant-ph

TL;DR

Markov logic networks combine first-order logic with probabilistic graphical models, but approximate inference remains costly because grounding produces large networks. This paper analyzes quantum Gibbs-sampling protocols together with first-order lifting to reduce the effective inference burden. It reports an exponential improvement over classical simulated annealing in selected runtime dependence, while exponential scaling in the number of nodes remains.

Abstract

from arXiv · show

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.

I. INTRODUCTION

MLNs combine first-order logic with probabilistic graphical models, but inference remains costly because grounding creates many nodes. The paper therefore studies quantum Gibbs-sampling approaches and lifting methods for reducing this burden.

  • Exact inference is #P-complete in general, while MCMC Gibbs sampling remains computationally intensive and can suffer from the enormous number of grounded nodes.Source: §I · p. 1
  • MLNs reconcile first-order logic with probabilistic graphical models by using logical formulas as templates for generating Markov networks.Source: §I · p. 1
  • Quantum approaches have improved training of Boltzmann machines, but hardware topology restrictions make their limited clique sizes especially attractive.Source: §I · p. 1
  • This work extends quantum Gibbs-sampling analysis from Boltzmann-machine training to inference in more expressive MLNs.Source: §I · p. 1

II. PROBABILISTIC INFERENCE AND LIFTING

Probabilistic inference in MLNs is generally hard, motivating approximate sampling and the exploitation of first-order symmetries. Lifting reduces redundant grounding, although evidence can disrupt those symmetries and requires careful handling.

  • An MLN assigns weights to first-order formulas and represents a distribution over worlds according to the number of satisfied groundings.Source: §II · p. 2
  • The generated network can contain O(D^c) nodes, with clique size bounded by the maximum number of atoms in a formula.Source: §II · p. 2
  • Exact probabilistic inference is #P-complete and approximate inference is NP-hard, so MLNs commonly use belief propagation or MCMC Gibbs sampling.Source: §II · p. 2
  • Lifting exploits symmetries by grouping similar variables before grounding, reducing the complexity of the generated Markov network.Source: §II · pp. 2–3
  • Evidence can skew symmetries, so importance sampling may be needed to cluster similar components and approximate corrected probabilities.Source: §II · p. 3
  • Despite practical usefulness, belief propagation and MCMC remain very expensive, motivating more efficient inference alternatives.Source: §II · p. 3

III. QUANTUM GIBBS SAMPLING

The MLN distribution can be represented as the thermal Gibbs distribution of a k-local quantum Hamiltonian. Quantum state preparation and measurement can therefore provide a route to sampling, with complexity governed by graph locality, system size, weights, and temperature.

  • The MLN probability distribution can be sampled by preparing a physical system in a thermal Gibbs state and measuring its configuration.Source: §III · p. 3
  • MLN weights define an effective energy and inverse temperature, allowing the distribution to be rewritten using a Hamiltonian and partition function.Source: §III · p. 3
  • The Hamiltonian decomposes into local terms over grounded cliques, with locality bounded by the maximum number of atoms per formula.Source: §III · p. 3
  • Each local term has operator norm at most one, making the MLN distribution the Gibbs distribution of a k-local Hamiltonian.Source: §III · p. 3
  • Moderate weights require only relatively high effective temperature, whereas strongly suppressed assignments require cooling to low temperature.Source: §III · p. 3

IV. COMPUTATIONAL COMPLEXITY

Quantum Gibbs sampling uses preparation and measurement phases to sample MLN Gibbs distributions, with complexity governed by temperature, local structure, and system size. For MLNs with constant formula size, the approach improves runtime scaling over classical methods, especially in precision and inverse temperature.

IV. COMPUTATIONAL COMPLEXITY

  • Quantum Gibbs sampling prepares a state encoding the Gibbs distribution and then obtains samples through local measurements.The preparation state may approximate a thermal Gibbs state or a pure thermal state.Source: §IV · pp. 3–4
  • The measurement phase has complexity O(n), while preparation complexity depends on β, local dimension, Hamiltonian terms, term supports, strengths, partition function, and target error ϵ.For MLNs, the local dimension is d = 2.Source: §IV · p. 4
  • For constant maximum formula size, quantum Gibbs sampling achieves the stated complexity scaling, which depends on clique structure and number of terms rather than directly on maximal MLN degree.The maximum formula atom count bounds local-term supports, and the number of Hamiltonian terms equals the number of MLN cliques.Source: §IV · p. 4
  • The method improves runtime scaling with 1/ϵ and β and gives an exponential improvement over classical simulated annealing in n and ϵ, although exponential dependence on n remains.Classical simulated annealing scales as 1/(δ ϵ^2), with δ often in O(1/d^n).Source: §IV · p. 4
  • Earlier quantum approaches reduce dependence on Hilbert-space dimension or inverse Markov-chain gap, but many perform similarly when 1/δ ≈ d^n.Microcanonical-state methods instead have at least exponential scaling in β∥H∥.Source: §IV · p. 5
  • Special-purpose methods can be more efficient for structured Hamiltonians or high temperatures, while quantum Metropolis sampling addresses the sign problem without targeting a speedup.These methods have limited relevance to MLN inference as described.Source: §IV · p. 5

A. Can We Hope for Something Better?

Quantum methods substantially reduce approximate Gibbs-sampling complexity, but general efficient inference remains unlikely at low temperatures because it would imply efficient solutions to hard satisfiability problems.

A. Can We Hope for Something Better?

  • Quantum Gibbs sampling still scales exponentially with the number of groundings and diverges as β approaches infinity.The remaining n dependence concerns all possible groundings of the atoms.Source: A. Can We Hope for Something Better? · p. 5
  • A general efficient quantum inference algorithm for high-weight MLNs is considered unlikely because it would imply efficient algorithms for satisfiability problems more general than 3-SAT.The passage relates this boundary to NP-completeness via the Cook–Levin theorem [42].Source: A. Can We Hope for Something Better? · p. 5
  • The log(1/ϵ) complexity scaling is optimal for Hamiltonian simulation and therefore for Gibbs-sampling methods based on it.The high-temperature regime is different because more efficient Gibbs-sampling methods exist.Source: A. Can We Hope for Something Better? · p. 5

B. Computing the Partition Function with First-Order Lifting

First-order lifting reduces MLN network size before Gibbs sampling by exploiting decomposers, isolated variables, singleton atoms, and other structural symmetries. The resulting procedure computes the partition function through recursive simplification and post-processing.

B. Computing the Partition Function with First-Order Lifting

  • First-order lifting can save potentially exponentially many groundings by simplifying the compact MLN representation before sampling.The procedure runs Gibbs sampling on the smaller network and uses bookkeeping values to recover the partition function.Source: B. Computing the Partition Function… · p. 5
  • The lifted-sampling algorithm recursively handles fully grounded networks, decomposers, isolated variables, singleton atoms, and selected ground atoms.A normal-form network with domains of size one can be passed directly to the Gibbs sampler.Source: B. Computing the Partition Function… · pp. 5–6
  • Decomposers identify logical variables that occur once per atom in consistent predicate positions, allowing substitution by a shared constant and exponentiation over the domain size.The decomposer can be detected in linear time.Source: B. Computing the Partition Function… · p. 5
  • Isolated variables and singleton atoms are removed after evaluating their relevant groundings, with combinatorial or weighted multipliers preserving the partition function.For singleton atoms, the network is conditioned on assignments containing exactly i true groundings and summed using w(i) and p(i).Source: B. Computing the Partition Function… · pp. 5–6
  • When no structural heuristic applies, the method fully grounds an atom, normalizes the result, and continues with the remaining expressions.This provides the fallback step in the recursive procedure.Source: B. Computing the Partition Function… · p. 6

C. Probabilistic Inference Given Evidence

Evidence can be incorporated either by clamping Hamiltonian terms or by constructing reduced local truth tables. Reduced tables remove evidenced atoms and cannot increase the quantum sampling cost, while clustering heuristics can further reduce the network.

C. Probabilistic Inference Given Evidence

  • Strong local clamping terms can enforce evidence with few Hamiltonian-simulation changes, but finite clamping strength introduces error and very strong terms can worsen runtime.This approach modifies the Hamiltonian directly.Source: C. Probabilistic Inference Given… · p. 6
  • Reduced truth tables construct Hamiltonian terms only for grounded atoms without evidence, decreasing maximal weight, term count, and site count.The resulting Gibbs-sampling problem is always at most as computationally costly as the original.Source: C. Probabilistic Inference Given… · p. 6
  • Classical clustering heuristics replace similar partially clamped groundings by cluster centers, reducing network size from O(D^c) to O(r^c) and thereby reducing n.Evidence can skew first-order symmetries and otherwise lead to complete grounding.Source: C. Probabilistic Inference Given… · p. 6

V. CONCLUSIONS AND FUTURE WORK

The paper analyzes quantum Gibbs sampling for MLN inference, including structural complexity, lifting-based network reduction, and evidence effects. It also discusses implementation prospects and the limitations imposed by current quantum hardware.

V. CONCLUSIONS AND FUTURE WORK

  • A term in the quantum Gibbs sampling complexity reduces exponentially, although the overall complexity remains exponential in the number of nodes.The analysis examines the protocol under structural properties of MLNs and argues theoretical limits.Source: §V · p. 6
  • A lifted first-order algorithm reduces the complexity of the MLN-generated network while allowing either classical MCMC or quantum Gibbs sampling in place of a proposal distribution.The algorithm mirrors lifted importance sampling but substitutes sampling methods for the proposal distribution.Source: §V · p. 6
  • The study also examines how evidence affects quantum Gibbs sampling protocols.Source: §V · p. 6
  • The considered protocols require a universal quantum computer, leaving them mainly of academic interest given current implementation hurdles.Quantum annealing devices offer an alternative, but their distributions, biases, temperature estimation, and connectivity require attention.Source: §V · p. 6
  • Quantum annealing devices face restricted connectivity for arbitrary graph structures, although recent methods can embed arbitrary graphs at quadratic worst-case spin cost.Source: §V · p. 7
Loading 1611.08104v1…