XiaoMi-AI文件搜索系统
World File Search SystemQAOA
3-SAT 的 Grover-QAOA：二次加速，一般
摘要 SAT 问题是计算复杂性理论中具有根本重要性的典型 NP 完全问题，在科学和工程领域有许多应用；因此，它长期以来一直是经典算法和量子算法的重要基准。这项研究通过数值证据证明了 Grover 量子近似优化算法 (G-QAOA) 比随机抽样在寻找 3-SAT (All-SAT) 和 Max-SAT 问题的所有解方面具有二次加速。与 Grover 算法相比，G-QAOA 占用的资源更少，更适合解决这些问题，并且在对所有解进行抽样的能力方面超越了传统的 QAOA。我们通过对数千个随机 3-SAT 实例进行多轮 G-QAOA 的经典模拟来展示这些优势。我们还观察到 IonQ Aria 量子计算机上 G-QAOA 在小型实例方面的优势，发现当前硬件足以确定和采样所有解决方案。有趣的是，在每一轮 G-QAOA 中使用相同角度对的单角度对约束大大降低了优化 G-QAOA 角度的传统计算开销，同时保持了其二次加速。我们还发现了角度的参数聚类。单角度对协议和参数聚类显著减少了对 G-QAOA 角度进行传统优化的障碍。
量子近似优化算法（QAOA）
Farhi 等人 [ 17 ] 证明，在某些条件（难以满足）下，QAOA 可以找到组合优化问题的近似解。该算法的潜力和挑战引起了许多研究人员的注意，其中包括 [ 6 ， 29 ， 44 ] 等。QAOA 的灵感来自量子绝热算法 (QAA)，该算法旨在找到 Hermitian 矩阵的最小特征值，该特征值称为基态能量 [ 17 ， 19 ， 20 ]。QAA 从一个 Hermitian 矩阵（具有已知基态）开始，在追踪基态的同时逐渐演化为另一个具有未知基态的 Hermitian 矩阵。QAA 的演化时间可能是指数级的，因此计算成本很高 [ 17 ]。此外，QAA 的成功概率通常不是运行时间的单调函数，而 QAOA 具有最优参数的性能会随着迭代次数（称为级别）的增加而提高 [ 17 ]。
使用 QAOA 进行分类的特征选择
摘要 — 特征选择在机器学习中非常重要，它可用于降低分类、排名和预测问题的维数。删除冗余和噪声特征可以提高训练模型的准确性和可扩展性。但是，特征选择是一项计算量大的任务，其解决方案空间会以组合方式增长。在这项工作中，我们特别考虑了二次特征选择问题，该问题可以用量子近似优化算法 (QAOA) 来解决，该算法已用于组合优化。首先，我们用 QUBO 公式表示特征选择问题，然后将其映射到 Ising 自旋哈密顿量。然后我们应用 QAOA 来找到该哈密顿量的基态，这对应于特征的最佳选择。在我们的实验中，我们考虑了七个不同的真实世界数据集，维数高达 21，并在量子模拟器和 7 量子比特 IBM (ibm–perth) 量子计算机上（对于小型数据集）运行 QAOA。我们使用选定的特征集来训练分类模型并评估其准确性。我们的分析表明，使用 QAOA 解决特征选择问题是可能的，并且目前可用的量子设备可以得到有效利用。未来的研究可以测试更广泛的分类模型，并通过探索性能更好的优化器来提高 QAOA 的有效性。索引术语 —QAOA、特征选择、QUBO、分类
QAOA、VQE、NISQ
模型梯度下降 [Sung et al '20]：围绕当前参数拟合二次模型并最小化它（BayesMGD [Stanisic et al '21]：使用贝叶斯规则来维持模型中的不确定性；解析下降 [Koczor and Benjamin
QAOA 图结构对 MaxCut 的影响
量子近似优化算法 (QAOA) 是一种利用量子计算解决组合优化问题的有前途的方法。MaxCut 问题上的 QAOA 已在具有特定结构的图上得到了广泛的研究，然而，对于该算法在任意图上的一般性能知之甚少。在本文中，我们研究了对于所有具有最多八个顶点的连通非同构图，不同图特征与 MaxCut 问题上深度最多为 3 的 QAOA 性能之间的关系。QAOA 成功的一些很好的预测因素与图对称性、奇数环和密度有关。例如，在八个顶点的图上，经过三次 QAOA 迭代后，对于不包含奇数环的图选择最优解的平均概率为 60.6%，而包含奇数环的图为 48.2%。这些研究生成的数据在一个可公开访问的数据库中共享，以作为 QAOA 计算和实验的基准。了解结构和性能之间的关系可用于识别可能表现出量子优势的组合问题类别。