Multi-Spin-Flip Engineering in an Ising Machine

Tatsuhiko Shirai*, Nozomu Togawa

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

A merge process is proposed to engineer a multi-spin flip in an Ising machine. The merge process deforms the Hamiltonian (energy function) of the Ising model. We prove a theorem for the merge process and show that a single-spin flip in the deformed Hamiltonian is equivalent to a multi-spin flip in the original Hamiltonian. A merge process induces a transition within the subspace of feasible solutions. We propose a hybrid simulated annealing (SA) algorithm with the merge process. The hybrid algorithm outperforms the conventional SA algorithm, genetic algorithm, and tabu search in the binary quadratic knapsack problems (QKP) and the quadratic assignment problems (QAP). Finally, the hybrid merge process is used in a real Ising machine. The performance is improved in QKP and QAP instances. The merge process is generally applicable to existing Ising machine hardware because the deformed Hamiltonian keeps the format of the Ising model.

Original languageEnglish
Pages (from-to)759-771
Number of pages13
JournalIEEE Transactions on Computers
Volume72
Issue number3
DOIs
Publication statusPublished - 2023 Mar 1

Keywords

  • Combinatorial optimization problem
  • genetic algorithm
  • ising machine
  • ising model
  • simulated annealing
  • tabu search

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Multi-Spin-Flip Engineering in an Ising Machine'. Together they form a unique fingerprint.

Cite this