Aug, 2019

用于估算凸体积的量子算法

PDF
TL;DR本研究提出一种基于 Chebyshev cooling 并利用量子随机游走技术的量子算法，用于估算多维凸包的体积，比已知的经典算法要更快，同时还证明了量子算法所需的查询次数。
quantum algorithmvolume estimationconvex bodychebyshev coolingsimulated annealing
发现论文，激发创造
  • 体积和高斯体积的高斯冷却和 O*(n^3) 算法

    我们提出了一种基于随机化算法的方法，用于估计具有会员 Oracle 的圆满凸体的体积。我们还提供了一种有改进的高斯分布采样算法，并分析了采样复杂性。

    Sep, 2014

  • 计算高斯体积的三次算法

    本研究提出了应用于凸集内标准高斯分布抽样及高斯度量估计的随机算法，并证明它们在一般性成员查询模型下的可行性，其采样的时间复杂度为每个样本均摊 $O^*(n^2)$，比现有最先进算法快 $n$ 倍。在等周问题、平滑退火、避免变换到各向同性和快速随机行走等方面实现了改进。

    Jun, 2013

  • 高维几何物体的并集和交集体积近似

    本研究探讨高维几何对象的求并集体积问题。本文给出了一个快速的 FPRAS 算法，可以有效地逼近 Klee's measure problem 和 hypervolume indicator，并能够逼近由弱成员资格证明给出的凸体的并集体积。同时，作者还探讨了高维几何对象的交集计算问题，并证明了其 #P 难度。

    Sep, 2008

  • 有限和优化的量子算法与下界

    通过量子计算，我们提出了一个具有改进复杂性的量子算法来解决有限和优化问题，使得我们可以找到一个 ε- 最优解点。

    Jun, 2024

  • k-Means 的量子逼近方案

    我们给出了在 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

  • 论最大体积单纯形和子行列式

    本论文提出了一种多项式时间复杂度下可以近似求解凸包中体积最大值的算法，近似比可以达到 $O (log d)^{d/2}$。此外，本文也展示了此问题的不可近似性，除非 $P=NP$。类似的结果也适用于矩阵行列式的最大值问题。

    Jun, 2014

  • Gibbs 采样和撞击时间估计的量子算法

    本研究介绍了两种针对随机过程的量子算法，分别用于热吉布斯态的准备和马尔可夫链的命中时间估计，并使用哈密顿模拟、谱间隙放大和线性方程组解法等工具进行实现。

    Mar, 2016

  • 量子信道容量的高效逼近

    本文提出基于凸规划对离散输入字母和有限维输出的经典量子通道容量的迭代估算方法，得到 Holevo 容量的近似值，并且可将其扩展到有界连续输入和有限维输出的通道。

    Jul, 2014

  • 非对数凹分布的随机量子取样与分割函数估计

    我们提出了量子算法用于从非对数凹概率分布中采样，同时解决了求解大数据集中混合模型和多稳定系统时计算代价昂贵的函数评估问题。我们的量子算法在维度和精度依赖方面相对于已知的最佳经典算法展示了多项式加速。

    Oct, 2023

  • 一种更快的切平面方法及其对组合优化和凸优化的影响

    通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。

    Aug, 2015