Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach

Aeho Choi; Seunghyeok Oh; Soohyun Park; Jong Kook Kim

doi:10.1109/ICOIN50884.2021.9333931

Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach

Aeho Choi, Seunghyeok Oh, Soohyun Park, Jong Kook Kim

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Advanced researches on the variational quantum algorithms are actively conducted. In particular, the quantum approximate optimization algorithm (QAOA) is one of the promising variational quantum algorithms and can be applied to various graph-based problems, and is a promising algorithm that shows good performance even in small quantum computers. As is widely known, QAOA obtains the approximate solution via the expectation value of the cost Hamiltonian on the parameterized state. Therefore, in addition to finding the optimal parameters, the proper design of the cost Hamiltonian is important. This paper designs the cost function of the combinatorial optimization problem via Boolean function and maps it to the proper cost Hamiltonian. The proposed cost Hamiltonian design method is applied to the maximum independent set (MIS) and minimum dominating set (MDS) problems.

Original language	English
Title of host publication	35th International Conference on Information Networking, ICOIN 2021
Publisher	IEEE Computer Society
Pages	469-472
Number of pages	4
ISBN (Electronic)	9781728191003
DOIs	https://doi.org/10.1109/ICOIN50884.2021.9333931
Publication status	Published - 2021 Jan 13
Externally published	Yes
Event	35th International Conference on Information Networking, ICOIN 2021 - Jeju Island, Korea, Republic of Duration: 2021 Jan 13 → 2021 Jan 16

Publication series

Name	International Conference on Information Networking
Volume	2021-January
ISSN (Print)	1976-7684

Conference

Conference	35th International Conference on Information Networking, ICOIN 2021
Country/Territory	Korea, Republic of
City	Jeju Island
Period	21/1/13 → 21/1/16

Bibliographical note

Publisher Copyright:
© 2021 IEEE.

Keywords

MDS
MIS
QAOA

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems

Access to Document

10.1109/ICOIN50884.2021.9333931

Cite this

Choi, A., Oh, S., Park, S., & Kim, J. K. (2021). Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach. In 35th International Conference on Information Networking, ICOIN 2021 (pp. 469-472). Article 9333931 (International Conference on Information Networking; Vol. 2021-January). IEEE Computer Society. https://doi.org/10.1109/ICOIN50884.2021.9333931

Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach. / Choi, Aeho; Oh, Seunghyeok; Park, Soohyun et al.
35th International Conference on Information Networking, ICOIN 2021. IEEE Computer Society, 2021. p. 469-472 9333931 (International Conference on Information Networking; Vol. 2021-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Choi, A, Oh, S, Park, S & Kim, JK 2021, Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach. in 35th International Conference on Information Networking, ICOIN 2021., 9333931, International Conference on Information Networking, vol. 2021-January, IEEE Computer Society, pp. 469-472, 35th International Conference on Information Networking, ICOIN 2021, Jeju Island, Korea, Republic of, 21/1/13. https://doi.org/10.1109/ICOIN50884.2021.9333931

@inproceedings{a86da9f284234860aa2cafa07d58b4a4,

title = "Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach",

abstract = "Advanced researches on the variational quantum algorithms are actively conducted. In particular, the quantum approximate optimization algorithm (QAOA) is one of the promising variational quantum algorithms and can be applied to various graph-based problems, and is a promising algorithm that shows good performance even in small quantum computers. As is widely known, QAOA obtains the approximate solution via the expectation value of the cost Hamiltonian on the parameterized state. Therefore, in addition to finding the optimal parameters, the proper design of the cost Hamiltonian is important. This paper designs the cost function of the combinatorial optimization problem via Boolean function and maps it to the proper cost Hamiltonian. The proposed cost Hamiltonian design method is applied to the maximum independent set (MIS) and minimum dominating set (MDS) problems.",

keywords = "MDS, MIS, QAOA",

author = "Aeho Choi and Seunghyeok Oh and Soohyun Park and Kim, {Jong Kook}",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 35th International Conference on Information Networking, ICOIN 2021 ; Conference date: 13-01-2021 Through 16-01-2021",

year = "2021",

month = jan,

day = "13",

doi = "10.1109/ICOIN50884.2021.9333931",

language = "English",

series = "International Conference on Information Networking",

publisher = "IEEE Computer Society",

pages = "469--472",

booktitle = "35th International Conference on Information Networking, ICOIN 2021",

}

TY - GEN

T1 - Proper Cost Hamiltonian Design for Combinatorial Optimization Problems

T2 - 35th International Conference on Information Networking, ICOIN 2021

AU - Choi, Aeho

AU - Oh, Seunghyeok

AU - Park, Soohyun

AU - Kim, Jong Kook

PY - 2021/1/13

Y1 - 2021/1/13

N2 - Advanced researches on the variational quantum algorithms are actively conducted. In particular, the quantum approximate optimization algorithm (QAOA) is one of the promising variational quantum algorithms and can be applied to various graph-based problems, and is a promising algorithm that shows good performance even in small quantum computers. As is widely known, QAOA obtains the approximate solution via the expectation value of the cost Hamiltonian on the parameterized state. Therefore, in addition to finding the optimal parameters, the proper design of the cost Hamiltonian is important. This paper designs the cost function of the combinatorial optimization problem via Boolean function and maps it to the proper cost Hamiltonian. The proposed cost Hamiltonian design method is applied to the maximum independent set (MIS) and minimum dominating set (MDS) problems.

AB - Advanced researches on the variational quantum algorithms are actively conducted. In particular, the quantum approximate optimization algorithm (QAOA) is one of the promising variational quantum algorithms and can be applied to various graph-based problems, and is a promising algorithm that shows good performance even in small quantum computers. As is widely known, QAOA obtains the approximate solution via the expectation value of the cost Hamiltonian on the parameterized state. Therefore, in addition to finding the optimal parameters, the proper design of the cost Hamiltonian is important. This paper designs the cost function of the combinatorial optimization problem via Boolean function and maps it to the proper cost Hamiltonian. The proposed cost Hamiltonian design method is applied to the maximum independent set (MIS) and minimum dominating set (MDS) problems.

KW - MDS

KW - MIS

KW - QAOA

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

U2 - 10.1109/ICOIN50884.2021.9333931

DO - 10.1109/ICOIN50884.2021.9333931

M3 - Conference contribution

AN - SCOPUS:85100726142

T3 - International Conference on Information Networking

SP - 469

EP - 472

BT - 35th International Conference on Information Networking, ICOIN 2021

PB - IEEE Computer Society

Y2 - 13 January 2021 through 16 January 2021

ER -

Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this