一种基于量子启发式思想的经典推荐系统算法
本文提出了一种量子算法,通过对 $m imes n$ 偏好矩阵的高效近似采样,设计一种有效的量子程序来将一个给定向量投影到一个给定矩阵的行空间上,从而在矩阵维度的对数级别时间内为个性化推荐系统提供了一个机器学习案例。
Mar, 2016
研究量子启发式算法在推荐系统和线性方程组方面的实际性能优化,证明这些算法可以应用于低秩矩阵问题的实际情境下表现良好,但当输入矩阵的秩或条件数增加时,他们的性能会明显降低。
May, 2019
本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法:提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。
Nov, 2018
介绍了一个基于奇异值估算子程序的量子算法,可解决线性方程组问题,其运行时间与矩阵 A 的条件数、Frobenius 范数和精度参数有关。当应用于具有范数受到限制的密集矩阵时,所提出的算法的运行时间受到限制,其运行时间比已知的量子线性系统算法提高了平方级别。
Apr, 2017
我们设计了基于量子算法的子线性算法,用于分类问题和矩阵零和游戏问题的求解,其复杂度都是量级上界的平方根,相较现有技术有瓶颈的常数。我们的算法生成与传统算法完全相同的结果,推荐用于端到端应用,同时探讨了实现方式以及机器可达到的限制。
Apr, 2019
我们给出了在 QRAM 模型中,对于经典 k - 均值聚类问题的量子逼近方案(即对于每个 ε>0,具有(1+ε)- 逼近),其运行时间只有数据点数量的对数多项式依赖。具体而言,对于存储在 QRAM 数据结构中的包含 N 个在 R^d 中的点的数据集 V,我们的量子算法以时间 Γ(O)((2^(Γ(O)(k/ε)))η^2d) 运行,并且以高概率输出一个包含 k 个中心的集合 C,其中 cost (V, C) ≤ (1+ε)・cost (V, C_OPT)。这是第一个具有对 k - 均值问题具有(1+ε)可证逼近保证且具有多项式对数运行时间的量子算法。此外,与先前的无监督学习方法不同,我们的量子算法不需要量子线性代数子程序,并且其运行时间与出现在这些过程中的参数(例如条件数)无关。
Aug, 2023
本文提出了一个第三阶张量的量子奇异值分解算法和一个基于其的推荐系统和张量补全算法,该算法在复杂度方面有指数级优势并且可以根据用户的上下文情况提供变化的推荐。
Oct, 2019
本文提出一种量子支持向量机分类器模型,实现有监督分类并取得了明显的量子加速,要求仅具备经典数据访问能力。在构造的数据集中,基于普遍认为的离散对数问题的困难性假设,该量子分类器实现的分类效果均优于无法逆多项式地超越瞎猜的经典学习器。这个模型可以通过一个容错的量子计算机来估算内积核函数,并且将数据映射为一个量子特征空间。此外,该分类器对由有限采样误差产生的内积核函数的加性误差具有一定的鲁棒性。
Oct, 2020
本研究提出了一种插值算法,该算法能够在两个特殊情况之间插值,并解决矩阵游戏问题。我们同时提供经典算法和量子算法,用于近似 Carathéodore 问题和 lq-margin 支持向量机。
Dec, 2020