  Graphical models are useful tools for describing structured high-dimensional
probability distributions. Development of efficient algorithms for generating
unbiased and independent samples from graphical models remains an active
research topic. Sampling from graphical models that describe the statistics of
discrete variables is a particularly challenging problem, which is intractable
in the presence of high dimensions. In this work, we provide the first method
that allows one to provably generate unbiased and independent samples from
general discrete factor models with a quantum circuit. Our method is compatible
with multi-body interactions and its success probability does not depend on the
number of variables. To this end, we identify a novel embedding of the
graphical model into unitary operators and provide rigorous guarantees on the
resulting quantum state. Moreover, we prove a unitary Hammersley-Clifford
theorem -- showing that our quantum embedding factorizes over the cliques of
the underlying conditional independence structure. Importantly, the quantum
embedding allows for maximum likelihood learning as well as maximum a
posteriori state approximation via state-of-the-art hybrid quantum-classical
methods. Finally, the proposed quantum method can be implemented on current
quantum processors. Experiments with quantum simulation as well as actual
quantum hardware show that our method can carry out sampling and parameter
learning on quantum computers.
