With the slowdown of improvement in conventional von Neumann systems,
increasing attention is paid to novel paradigms such as Ising machines. They
have very different approach to NP-complete optimization problems. Ising
machines have shown great potential in solving binary optimization problems
like MaxCut. In this paper, we present an analysis of these systems in
satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a
basic architecture fails to produce meaningful acceleration, thanks in no small
part to the relentless progress made in conventional SAT solvers. Nevertheless,
careful analysis attributes part of the failure to the lack of two important
components: cubic interactions and efficient randomization heuristics. To
overcome these limitations, we add proper architectural support for cubic
interaction on a state-of-the-art Ising machine. More importantly, we propose a
novel semantic-aware annealing schedule that makes the search-space navigation
much more efficient than existing annealing heuristics. With experimental
analyses, we show that such an Augmented Ising Machine for SAT (AIMS),
outperforms state-of-the-art software-based, GPU-based and conventional
hardware SAT solvers by orders of magnitude. We also demonstrate AIMS to be
relatively robust against device variation and noise.

本文讲述了基于 Ising 机的解决最优化问题方法。作者发现缺少了立方相互作用和高效的随机化启发式算法成为了失误的原因。最后，作者增加了一个合适的框架和一个新的方法，提高了搜索的效率，实验结果在以往硬件和软件求解最优化问题算法的基础上取得了更高的效果。

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

Augmented Electronic Ising Machine as an Effective SAT Solver

Parallel tempering (PT) methods are a popular class of Markov chain Monte
Carlo schemes used to sample complex high-dimensional probability
distributions. They rely on a collection of $N$ interacting auxiliary chains
targeting tempered versions of the target distribution to improve the
exploration of the state-space. We provide here a new perspective on these
highly parallel algorithms and their tuning by identifying and formalizing a
sharp divide in the behaviour and performance of reversible versus
non-reversible PT schemes. We show theoretically and empirically that a class
of non-reversible PT methods dominates its reversible counterparts and identify
distinct scaling limits for the non-reversible and reversible schemes, the
former being a piecewise-deterministic Markov process and the latter a
diffusion. These results are exploited to identify the optimal annealing
schedule for non-reversible PT and to develop an iterative scheme approximating
this schedule. We provide a wide range of numerical examples supporting our
theoretical and methodological contributions. The proposed methodology is
applicable to sample from a distribution $\pi$ with a density $L$ with respect
to a reference distribution $\pi_0$ and compute the normalizing constant. A
typical use case is when $\pi_0$ is a prior distribution, $L$ a likelihood
function and $\pi$ the corresponding posterior.

本文针对平行淬火方法，通过识别可逆和不可逆的淬火系统的性能差异和表现，理论和实践分析了非可逆平行淬火方法的优越性，并研究了不可逆和可逆淬火方案的不同扩展极限，从而确定了最佳的淬火方案。