近似子模函数最小化的量子经典算法

作者：Yassine Hamoudi,Patrick Rebentrost,Ansis Rosmanis,Miklos Santha

摘要：子模块函数是设置函数，将一些大小为n的地面集的每个子集映射到实数中并满足递减的返回属性。子模极小化是离散优化理论中的一个重要领域，因为它与数学，计算机科学和经济学的各个分支相关。目前用于精确最小化的最快强多项式算法[LSW15]在时间O~（n3⋅EO+ n4）中运行，其中EO表示评估任何集合上的函数的成本。对于范围为[-1,1]的函数，最佳ε-加法近似算法[CLSW17]在时间O~（n5 / 3 /ε2⋅EO）中运行。在本文中，我们提出了近似子模块最小化的经典和量子算法。我们的经典结果改进了[CLSW17]的算法并且在时间O~（n3 / 2 /ε2⋅EO）中运行。据我们所知，我们的量子算法首次尝试将量子计算用于子模块优化。算法在时间O〜（n5 / 4 /ε5/2⋅log（1 /ε）⋅EO）运行。量子结果的主要成分是从时间O（Tn ---√）的支持大小n的任何离散概率分布中采用高概率T独立元素进行采样的新方法。此问题的先前量子算法具有复杂度O（Tn - √）。

原文标题：Quantum and Classical Algorithms for Approximate Submodular Function Minimization

原文摘要：

地址：https://arxiv.org/abs/1907.05378