  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.
