We introduce two quantum algorithms for solving structured prediction problems. We show that a stochastic subgradient descent method that uses the quantum minimum finding algorithm and takes its probabilistic failure into account solves the structured prediction problem with a runtime that scales with the square root of the size of the label space, and in $\widetilde O\left(1/\epsilon\right)$ with respect to the precision, $\epsilon$, of the solution. Motivated by robust inference techniques in machine learning, we introduce another quantum algorithm that solves a smooth approximation of the structured prediction problem with a similar quantum speedup in the size of the label space and a similar scaling in the precision parameter. 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)$. This 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. Our numerical results using Monte Carlo simulations on an image tagging task demonstrate the benefit of the approach.
翻译:我们引入了两种量子算法来解决结构性预测问题。 我们展示了一种随机的亚梯级下沉法,这种方法使用量子最小查找算法,并将概率性故障考虑在内,用标签空间大小平方根的平方根运行时间,解决结构化预测问题,在计算梯度时出现添加错误时,用美元( 1/\ epsilon\ right) 来分析二次曲线优化的系统化梯度算法,并显示如果添加错误是按 $( qrt\ epsilon) 的顺序来计算,其趋同率不会恶化。 这种算法在温度 $\ Omega (\ epsilon) 中用类似的量子加速法解决结构预测问题,在标签空间的大小和精确参数的类似缩放时,解决结构化的预测问题。 在这样做时,我们分析了在计算梯度的计算中出现一个添加错误时, 美元( $( sqrt) levelloonlon) 运算法, 使用一个模型, 以模拟数字模型模型模型来展示我们数字模型的硬度图像模型, 。