增强一个电子的Ising机器,有效地解决布尔满足性
Anshujit Sharma1, Matthew Burns2, Andrew Hahn2
1Department of Electrical and Computer Engineering, University of Rochester, Rochester, NY, 14627, USA. ashar36@ur.rochester.edu.
Scientific reports
|December 21, 2023
概括
在优化问题上,Ising机器显示出有前途的优化问题. 一个增强的Ising机器架构,具有立方相互作用和新型化,在3-SAT问题上显著优于传统的SAT解决器.
科学领域:
- 计算机科学 计算机科学
- 量子计算是一种量子计算.
- 人工智能的人工智能
背景情况:
- 传统的·诺伊曼系统面临性能限制.
- 异构机为组合优化提供了一种新的方法,特别是在像MaxCut.这样的二进制问题上.
- 布尔满足性 (SAT) 问题是计算优化的一个关键领域.
研究的目的:
- 分析Ising机器在布尔满足性 (SAT) 问题上的性能,特别是3-SAT.
- 为SAT问题确定基本的Ising机器架构的局限性.
- 提出一个增强的Ising机器架构,以提高SAT解决能力.
主要方法:
- 在3-SAT问题上分析基本的Ising机器架构.
- 缺失组件的识别:立方相互作用和高效的随机化启发式.
- 开发一个增强的Ising机器,对立方交互的架构支持.
- 引入一种新的语义意识的化时间表,以实现高效的搜索空间导航.
- 数字模拟以评估性能与最先进的解决方案相比.
主要成果:
- 与先进的常规解决器相比,基本的Ising机器架构并不能为3-SAT提供显著的加速.
- 缺乏立方相互作用和高效的随机化启发术限制了在SAT上基本的Ising机器性能.
- 增强的Ising机器具有立方相互作用和语义意识的化时间表,证明了预计的性能增长.
- 模拟表明,增强的Ising机器可以在数量级上超过基于软件,基于GPU和硬件的SAT解决方案.
结论:
- 由于架构限制,基本的Ising机器不足以加速3-SAT问题解决.
- 增加具有立方相互作用的Ising机器和一个新的化时间表对于解决复杂的SAT问题至关重要.
- 拟议的增强的Ising机器架构具有显著的潜力,可以彻底改变SAT解决方案,比现有方法提供大量的加快速度.
相关概念视频
Simplified Synchronous Machine Model
239
The Synchronous Machine Model is a fundamental tool in analyzing and ensuring the transient stability of power systems. This model simplifies the representation of a synchronous machine under balanced three-phase positive-sequence conditions, assuming constant excitation and ignoring losses and saturation. The model is pivotal for understanding the behavior of synchronous generators connected to a power grid, particularly during transient events.
In this model, each generator is connected to a...
In this model, each generator is connected to a...
239
Block Diagram Reduction
212
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
212
Relation between Mathematical Equations and Block Diagrams
362
In a spring-mass-damper system, the second-order differential equation describes the dynamic behavior of the system. When transformed into the Laplace domain under zero initial conditions, this equation can be effectively analyzed and manipulated. The transformation into the Laplace domain converts differential equations into algebraic equations, simplifying the process of isolating the output.
362
Biasing of Metal-Semiconductor Junctions
259
Biasing metal-semiconductor junctions involves applying a voltage across the junction. Specifically, the metal is connected to a voltage source, while the semiconductor is grounded. This technique is essential for controlling the direction and magnitude of current flow in electronic devices, including diodes, transistors, and photovoltaic cells.
In Schottky junctions, where the semiconductor is n-type, applying a positive voltage to the metal relative to the semiconductor reduces its Fermi...
In Schottky junctions, where the semiconductor is n-type, applying a positive voltage to the metal relative to the semiconductor reduces its Fermi...
259
Norton Equivalent Circuits
388
Norton's theorem is a fundamental concept in the field of electrical engineering that allows for the simplification of complex AC circuits. The theorem states that any two-terminal linear network can be replaced with an equivalent circuit that consists of an impedance, which is parallel with a constant current source. Figure 1 shows the AC circuit portioned into two parts: Circuit A and Circuit B, while Figure 2 depicts the circuit obtained by replacing Circuit A by its Norton equivalent...
388
Formal Charges
32.6K
In some cases, there are seemingly more than one valid Lewis structures for molecules and polyatomic ions. The concept of formal charges can be used to help predict the most appropriate Lewis structure when more than one reasonable structure exists.
32.6K


