May, 2023

扩展的电子 Ising 机作为有效的 SAT 求解器

PDF
TL;DR本文讲述了基于 Ising 机的解决最优化问题方法。作者发现缺少了立方相互作用和高效的随机化启发式算法成为了失误的原因。最后，作者增加了一个合适的框架和一个新的方法，提高了搜索的效率，实验结果在以往硬件和软件求解最优化问题算法的基础上取得了更高的效果。
ising machinesoptimization problemssatisfiability (sat) problemscubic interactionsannealing schedule
发现论文，激发创造
  • 模拟相干 Ising 机进行退火

    在经典计算机上模拟了相干伊辛机 (CIM) 以处理实数节点耦合强度的伊辛哈密顿量，得出其比 CIM 和噪声均场退火器更高效的结论，这有助于开发一种与现有方法竞争的量子启发式经典退火算法。

    Jan, 2019

  • 应用 Ising 机解决多目标 QUBOs 问题

    本文提出一种基于平均值的自适应加权方法，用于解决多目标优化问题中的权衡问题，通过改进距离测量方法，实现多目标问题的 Pareto 前沿探索，并在对比实验中证明该方法在三个或四个目标的优化问题上的性能明显优于现有的方法。

    May, 2023

  • 经典和量子伊辛机的通用学习方案

    提出了一个基于 Ising 结构的新型机器学习模型，可以通过梯度下降进行高效训练，实验证明了 Ising 机器在不同的学习任务中的新可能性，尤其在量子机器学习领域中，量子资源被用于模型的执行和训练，提供了有希望的前景。

    Oct, 2023

  • CITS：一种基于同步伊辛树搜索算法的组合优化问题求解算法

    本文提出了一种基于模拟退火的启发式搜索算法，在搜索空间上通过展开马尔可夫链到递归深度树来寻找最优解，利用连续表示的自旋状态和正则化项以及振荡子的动力学来探索选定的树节点周围的搜索空间，并在 NP - 困难问题（MAX-CUT）上验证了该算法与半定规划、模拟退火和相干 Ising 机的比较实验中能够在较少的迭代次数内获得更优解的优越性。

    Mar, 2022

  • 用深度学习解决 Boltzmann 优化问题

    高性能计算的效率提升趋于尽头，传统的 CMOS 技术面临物理极限，Miniaturization 无法继续进行；以 Ising 模型为基础的计算系统能够接近热力学极限下的能耗，同时兼具逻辑和存储功能，潜在降低 CMOS 计算中昂贵的数据迁移造成的能源成本；本文的贡献是提出一种结合深度神经网络和随机森林的机器学习方法，用于高效解决 Ising 模型中最小化误差的优化问题，并提供一种将 Boltzmann 概率优化问题转化为监督式机器学习问题的过程。

    Jan, 2024

  • 在 Ising 机上训练多层神经网络

    该研究提出了一种用于训练量化神经网络（QNN）的 Ising 学习算法，该算法通过二进制编码网络拓扑和损失函数的降阶，实现了在 Ising 机器上训练多层前馈神经网络。该算法的空间复杂度约为 O (H^2L + HLNlogH)，通过模拟 Ising 机器在 MNIST 数据集上验证了其有效性。

    Nov, 2023

  • 利用低秩和循环矩阵约束的空间 - 光子伊辛机的高效计算

    通过开发和评估先进的分解技术，我们扩大了空间光子伊辛机 (SPIMs) 所能解决的问题范围，克服了传统 Mattis 型矩阵的局限性。我们探讨了低秩近似在优化任务中的实际收益，特别是在金融优化中，以展示 SPIMs 的实际应用。最后，我们评估了 SPIM 硬件精度所带来的计算限制，并提出优化系统性能的策略。

    Jun, 2024

  • torchmSAT：一个 GPU 加速的最大可满足性问题的近似算法

    利用机器学习技术将离散结构与组合优化算法集成，提出一种能够近似求解最大满足性问题的可微函数，设计了一种新颖的神经网络结构并借助后向传播逐步求解问题，通过利用 GPU 进行计算加速，论文实验证明这种方法在挑战性的最大满足性问题上优于两种现有求解器，并与另一种求解器在解决成本方面相当，而无需进行训练或使用底层 SAT 求解器，为基于神经网络 GPU 加速的新一代求解器铺平了道路。

    Feb, 2024

  • 将受限优化问题映射到量子退火，应用于故障诊断

    本研究提出了基于新型算法的量子退火硬件的布尔约束满足问题映射方法，可以缓解由于有限温度、稀疏连接、小量量子位和控制误差等限制所导致的问题。其中包括一种新的嵌码算法用于将 CSP 映射到硬件 Ising 模型，还提出了两种新的分解算法以用于解决直接映射到硬件不可行的问题，并使用 D-Wave 的硬件对基于电路的故障诊断方法进行了验证和应用。

    Mar, 2016

  • 利用矩阵乘法解决 MaxSAT 问题

    我们提出了一种针对神经网络加速器（如 GPU 和 TPU）运行的不完全的最大可满足性（MaxSAT）算法，该算法通过构建具有指数数量布尔赋值的平衡分布的受限玻尔兹曼机（RBM）来解决 MaxSAT 问题，使用并行马尔可夫链中的块 Gibbs 采样来随机搜索赋值空间，同时通过在 CPU 上运行基于单位传播的启发式算法对采样的赋值进行定期优化。我们的方法在 MaxSAT 的算法硬件协同设计空间中提供了一个新的设计点，并且在各年度 MaxSAT 评估竞赛的部分问题实例中显示出出色的表现。

    Nov, 2023