Quantum circuits for discrete graphical models

Abstract Graphical models are useful tools for describing structured high-dimensional probability distributions. The development of efficient algorithms for generating samples thereof remains an active research topic. In this work, we provide a quantum algorithm that enables the generation of unbiased and independent samples from general discrete graphical models. To this end, we identify a coherent embedding of the graphical model based on a repeat-until-success sampling scheme which clearly identifies whether a drawn sample represents the underlying distribution. Furthermore, we show that the success probability for finding a valid sample can be lower bounded with a quantity that depends on the number of maximal cliques and the model parameter norm. Moreover, we rigorously proof that the quantum embedding conserves the key property of graphical models, i.e., factorization over the cliques of the underlying conditional independence structure. The quantum sampling algorithm also allows for maximum likelihood learning as well as maximum a posteriori state approximation for the graphical model. Finally, the proposed quantum method shows potential to realize interesting problems on near-term quantum processors. In fact, illustrative experiments demonstrate that our method can carry out sampling and parameter learning not only with idealized simulations of quantum computers but also on actual quantum hardware solely supported by simple readout error mitigation.