We introduce a quantum algorithm for solving structured prediction problems with a runtime that scales with the square root of the size of the label space, but scales in $\widetilde O\left(\epsilon^{-3.5}\right)$ with respect to the precision, $\epsilon$, of the solution. In doing so, we analyze a stochastic gradient algorithm for convex optimization in the presence of an additive error in the calculation of the gradients, and show that its convergence rate does not deteriorate if the additive errors are of the order $O(\sqrt\epsilon)$. Our algorithm uses quantum Gibbs sampling at temperature $\Omega (\epsilon)$ as a subroutine. Based on these theoretical observations, we propose a method for using quantum Gibbs samplers to combine feedforward neural networks with probabilistic graphical models for quantum machine learning. Numerical results using Monte Carlo simulations on an image tagging task demonstrate the benefit of the approach.
翻译:我们引入了一种量子算法, 解决结构化预测问题, 使用标签空间大小平方根的运行时间解决结构化预测问题, 但是在解决方案的精确度( $\ epsilon ⁇ - 3.5 ⁇ right) 方面, 使用 $\ epsilon ⁇ - 3.5 ⁇ right 平方根的量子算法。 在这样做的时候, 我们分析一种在计算梯度时出现添加错误的情况下, 用于配置优化的随机梯度梯度算法, 并显示如果添加错误为 $O (\ sqrt\ epsilon) 的顺序, 其趋同率不会恶化。 我们的算法使用温度 $\ omega (\ epsilon) 的量子 Gibs 取样器作为子的子路程。 基于这些理论观察, 我们提出一种方法, 来使用量子吉布采样器将进式神经网络与量子机器学习的概率图形模型结合起来。 在图像标记任务上使用 Monte Car 模拟进行计算时, 数字结果不会恶化结果 。 显示方法的好处 。