在大尺度图中用连贯的Ising机器找到独立的集合
Hiroki Takesue1, Kensuke Inaba1, Toshimori Honjo1
1NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
使用退化的光学参数振荡器 (DOPO) 脉冲的连贯性异位机 (CIM) 能够有效地解决大型最大独立集问题. 这些物理系统在许多节点的复杂优化任务中优于数字计算机.
科学领域:
- 量子计算和优化 量子计算和优化
- 计算模型的物理实现.
背景情况:
- 异位机,用于组合优化的物理系统,在数字计算机上提供潜在的计算优势.
- 在各种现实世界的优化场景中,最大独立集问题至关重要.
研究的目的:
- 为了证明一个连贯的Ising机器 (CIM) 使用退化的光学参数振荡器 (DOPO) 脉冲来解决大规模的最大独立集问题的能力.
- 将CIM的性能与数字计算机上的优化模拟回火算法进行比较.
主要方法:
- 通过DOPO脉冲和铁磁合辅助脉冲之间的相互作用,为每个Ising旋转实现稳定的外部场.
- 使用CIM找到密集图的独立集合.
主要成果:
- CIM成功地确定了包含多达4万个节点的密集图的独立集.
- 与基于CPU的模拟回火相比,CIM在超过数千个节点的图形大小方面表现出优异的性能,特别是在找到近似解决方案所需的时间方面.
结论:
- 基于DOPO脉冲的连贯机对于解决大规模最大独立集问题是有效的.
- 对于特定复杂的优化任务,CIMs是数字计算的有希望的替代方案,为大型问题实例提供了显著的加快速度.
更多相关视频
05:12ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
Published on: January 16, 2019
09:01A Method for Investigating Age-related Differences in the Functional Connectivity of Cognitive Control Networks Associated with Dimensional Change Card Sort Performance
Published on: May 7, 2014
相关概念视频
Sequence Networks of Rotating Machines
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Lattice Centering and Coordination Number
Types of Unit Cells
Imagine taking a large number of identical...
Vector Algebra: Graphical Method
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
Machines: Problem Solving II
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Machines: Problem Solving I
The toggle clamp system is a machine structure consisting of movable, pin-connected multi-force members that form a stabilized system to transmit forces. The...
