论文标题
小型量子计算机和大型经典数据集
Small quantum computers and large classical data sets
论文作者
论文摘要
我们为涉及大型经典数据集X和模型Y的问题引入了混合经典量子算法，以使量子计算机具有对Y的叠加访问权限，但不能访问Y。这些算法使用数据减少技术来构建一个称为X的加权子集，称为X核心，每种模型损失大致相同。可以单独由古典计算机或通过交互式协议来构造核心，其中使用量子计算机的输出来帮助确定要使用的X的哪些元素。通过使用量子计算机执行Grover搜索或拒绝采样，这会产生量子加速度，以实现最大似然估计，贝叶斯推理和鞍点优化。具体应用程序包括K-均值聚类，后勤回归，零和游戏和提升。
We introduce hybrid classical-quantum algorithms for problems involving a large classical data set X and a space of models Y such that a quantum computer has superposition access to Y but not X. These algorithms use data reduction techniques to construct a weighted subset of X called a coreset that yields approximately the same loss for each model. The coreset can be constructed by the classical computer alone, or via an interactive protocol in which the outputs of the quantum computer are used to help decide which elements of X to use. By using the quantum computer to perform Grover search or rejection sampling, this yields quantum speedups for maximum likelihood estimation, Bayesian inference and saddle-point optimization. Concrete applications include k-means clustering, logistical regression, zero-sum games and boosting.
