Experimental evaluations of parallel tempering on an ising machine

Yosuke Mukasa; Shu Tanaka; Nozomu Togawa

doi:10.2197/IPSJTSLDM.14.27

Experimental evaluations of parallel tempering on an ising machine

Yosuke Mukasa, Shu Tanaka, Nozomu Togawa

Department of Applied Physics and Physico-Informatics

Research output: Contribution to journal › Article › peer-review

Abstract

Ising machines have recently attracted much attention because they are expected to solve combinatorial optimization problems efficiently. We focus on an Ising machine whose algorithm is based on parallel tempering (PT), and experimentally evaluate the performance of the Ising machine for MIN-CUT problems. Experimental results show that the Ising machine outperforms a famous graph partitioning solver in terms of the quality of solution and the time-to-target-solution.

Original language	English
Pages (from-to)	27-29
Number of pages	3
Journal	IPSJ Transactions on System LSI Design Methodology
Volume	14
DOIs	https://doi.org/10.2197/IPSJTSLDM.14.27
Publication status	Published - 2021

Keywords

Combinatorial optimization problem
Ising machines
Ising model
Parallel tempering
Quadratic unconstrained binary optimization

ASJC Scopus subject areas

Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.2197/IPSJTSLDM.14.27

Cite this

@article{2c30758021f54f36b7f68a2ad4452799,

title = "Experimental evaluations of parallel tempering on an ising machine",

abstract = "Ising machines have recently attracted much attention because they are expected to solve combinatorial optimization problems efficiently. We focus on an Ising machine whose algorithm is based on parallel tempering (PT), and experimentally evaluate the performance of the Ising machine for MIN-CUT problems. Experimental results show that the Ising machine outperforms a famous graph partitioning solver in terms of the quality of solution and the time-to-target-solution.",

keywords = "Combinatorial optimization problem, Ising machines, Ising model, Parallel tempering, Quadratic unconstrained binary optimization",

author = "Yosuke Mukasa and Shu Tanaka and Nozomu Togawa",

note = "Funding Information: Acknowledgments This work was supported in part by JST CREST Grant Number JPMJCR19K4, Japan. S. T. was also partially supported by JSPS KAKENHI Grant Number 19H01553. Publisher Copyright: c 2021 Information Processing Society of Japan",

year = "2021",

doi = "10.2197/IPSJTSLDM.14.27",

language = "English",

volume = "14",

pages = "27--29",

journal = "IPSJ Transactions on System LSI Design Methodology",

issn = "1882-6687",

publisher = "Information Processing Society of Japan",

}

TY - JOUR

T1 - Experimental evaluations of parallel tempering on an ising machine

AU - Mukasa, Yosuke

AU - Tanaka, Shu

AU - Togawa, Nozomu

N1 - Funding Information: Acknowledgments This work was supported in part by JST CREST Grant Number JPMJCR19K4, Japan. S. T. was also partially supported by JSPS KAKENHI Grant Number 19H01553. Publisher Copyright: c 2021 Information Processing Society of Japan

PY - 2021

Y1 - 2021

N2 - Ising machines have recently attracted much attention because they are expected to solve combinatorial optimization problems efficiently. We focus on an Ising machine whose algorithm is based on parallel tempering (PT), and experimentally evaluate the performance of the Ising machine for MIN-CUT problems. Experimental results show that the Ising machine outperforms a famous graph partitioning solver in terms of the quality of solution and the time-to-target-solution.

AB - Ising machines have recently attracted much attention because they are expected to solve combinatorial optimization problems efficiently. We focus on an Ising machine whose algorithm is based on parallel tempering (PT), and experimentally evaluate the performance of the Ising machine for MIN-CUT problems. Experimental results show that the Ising machine outperforms a famous graph partitioning solver in terms of the quality of solution and the time-to-target-solution.

KW - Combinatorial optimization problem

KW - Ising machines

KW - Ising model

KW - Parallel tempering

KW - Quadratic unconstrained binary optimization

UR - http://www.scopus.com/inward/record.url?scp=85113411132&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85113411132&partnerID=8YFLogxK

U2 - 10.2197/IPSJTSLDM.14.27

DO - 10.2197/IPSJTSLDM.14.27

M3 - Article

AN - SCOPUS:85113411132

SN - 1882-6687

VL - 14

SP - 27

EP - 29

JO - IPSJ Transactions on System LSI Design Methodology

JF - IPSJ Transactions on System LSI Design Methodology

ER -

Experimental evaluations of parallel tempering on an ising machine

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this