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.
翻译:图形模型是描述结构化高维概率分布的有用工具。 开发高效算法,从图形模型中生成公正和独立的样本,这仍然是一个积极的研究课题。 从描述离散变量统计数据的图形模型中取样是一个特别具有挑战性的问题,在高维存在的情况下,这个问题是难以解决的。 在这项工作中,我们提供了第一种方法,使一个人能够以量子电路从普通离散系数模型中产生公正和独立的样本。我们的方法与多体相互作用相容,其成功概率并不取决于变量的数量。为此目的,我们确定将图形模型新嵌入单一操作器,并为由此产生的量子状态提供严格的保障。此外,我们证明一个单一的汉默斯利-克利福德定理(Hammersley-Clifford theorem)是一个非常棘手的问题,表明我们的量子嵌入系数在基本条件独立结构的晶体上。重要的是,量嵌入允许通过最有可能的学习,并且通过最先进的混合量子级法方法,其成功概率并不取决于变量的数目。 最后,我们提出的量子法方法可以在目前的量子处理器上实施。 实验,用量子模拟和量子计算机进行量子模拟试验,作为实际的量子测试。