有限和优化的量子算法与下界
本文提出了优化 n 个 L-smooth、强凸函数总和的下界,并将其与先前的方法进行比较。在随机数据情况下,我们将这些复杂度结果与用于直接优化总和的最优一阶方法进行对比。研究发现需要谨慎进行准确比较,并确定新方法在机器学习场景中的帮助计算能力。
Oct, 2014
本文研究了平滑的非凸有限和优化的下界,并证明了在不同设置下找到 ε- 次优点和 ε- 近似稳定点的复杂度的严格下界,以及一些现有算法的最佳增量一阶预测器(IFO)复杂度。
Jan, 2019
我们设计了基于量子算法的子线性算法,用于分类问题和矩阵零和游戏问题的求解,其复杂度都是量级上界的平方根,相较现有技术有瓶颈的常数。我们的算法生成与传统算法完全相同的结果,推荐用于端到端应用,同时探讨了实现方式以及机器可达到的限制。
Apr, 2019
我们提出了首个在线量子算法,用于零和游戏,可以在 $\tilde O (1)$ 的时间内计算 $m \times n$ 矩阵零和游戏的 $\varepsilon$- 近似纳什均衡,与 $m$,$n$ 的经典算法相比,取得了二次的改进,同时实现了一个快速的量子线性规划求解器。
Apr, 2023
该论文提出了一个基于梯度下降的优化算法框架,发展了一种计算多元实值函数梯度的量子算法,并提高了计算梯度的复杂性以适应光滑函数的重要类别,而且可以为量子最优化算法提供更快的计算梯度方法。
Nov, 2017
本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果,其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题,并提高了期望严格学习的新下界,以达到经典 PAC 学习的已知上界。
Nov, 2004
我们通过一个非凸连续优化问题家族的研究,证明了新提出的量子哈密顿下降算法可以在多项式时间内解决这个问题,并且证明了经典优化算法需要超多项式时间来解决这样的优化问题。
Nov, 2023
我们提出了量子算法用于从非对数凹概率分布中采样,同时解决了求解大数据集中混合模型和多稳定系统时计算代价昂贵的函数评估问题。我们的量子算法在维度和精度依赖方面相对于已知的最佳经典算法展示了多项式加速。
Oct, 2023