Restricted Boltzmann Machines (RBMs) are widely used probabilistic undirected
graphical models with visible and latent nodes, playing an important role in
statistics and machine learning. The task of structure learning for RBMs
involves inferring the underlying graph by using samples from the visible
nodes. Specifically, learning the two-hop neighbors of each visible node allows
for the inference of the graph structure. Prior research has addressed the
structure learning problem for specific classes of RBMs, namely ferromagnetic
and locally consistent RBMs. In this paper, we extend the scope to the quantum
computing domain and propose corresponding quantum algorithms for this problem.
Our study demonstrates that the proposed quantum algorithms yield a polynomial
speedup compared to the classical algorithms for learning the structure of
these two classes of RBMs.

我们提出了相应的量子算法来解决 Restricted Boltzmann Machines 结构学习问题，并证明这些算法相对于经典算法在这两类 RBMs 的结构学习中具有多项式加速。

使用贪婪的量子搜索学习受限玻尔兹曼机

Learning Restricted Boltzmann Machines with greedy quantum search

We present a quantum interior point method with worst case running time
$\widetilde{O}(\frac{n^{2.5}}{\xi^{2}} \mu \kappa^3 \log (1/\epsilon))$ for
SDPs and $\widetilde{O}(\frac{n^{1.5}}{\xi^{2}} \mu \kappa^3 \log
(1/\epsilon))$ for LPs, where the output of our algorithm is a pair of matrices
$(S,Y)$ that are $\epsilon$-optimal $\xi$-approximate SDP solutions. The factor
$\mu$ is at most $\sqrt{2}n$ for SDPs and $\sqrt{2n}$ for LP's, and $\kappa$ is
an upper bound on the condition number of the intermediate solution matrices.
For the case where the intermediate matrices for the interior point method are
well conditioned, our method provides a polynomial speedup over the best known
classical SDP solvers and interior point based LP solvers, which have a worst
case running time of $O(n^{6})$ and $O(n^{3.5})$ respectively. Our results
build upon recently developed techniques for quantum linear algebra and pave
the way for the development of quantum algorithms for a variety of applications
in optimization and machine learning.

提出一种量子内点法，可用于 SDPs 和 LPs，可以提供多项式速度优于最佳已知的经典 SDP 解算器和内点基 LP 解算器，为量子优化和机器学习应用的开发铺平道路。