Design of quantum approximate optimization algorithm for graph multi coloring problem

Gunsik Min; Jun Heo

doi:10.1109/ICTC58733.2023.10393331

Design of quantum approximate optimization algorithm for graph multi coloring problem

Gunsik Min, Jun Heo

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

Abstract

We propose a technique to solve the problem of graph multi coloring, which is a problem corresponding to channel allocation problem, with the quantum approximate optimization algorithm(QAOA). QAOA is an algorithm that solve an optimization problem. Among the optimization problems, this algorithm is specialized as solving the quadratic unconstrained binary optimization(QUBO) problems. It is designed to find approximate solutions to combinatorial optimization problems by leveraging quantum resources. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph or applying algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations.

Original language	English
Title of host publication	ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence
Subtitle of host publication	Exploring the Frontiers of ICT Innovation
Publisher	IEEE Computer Society
Pages	517-519
Number of pages	3
ISBN (Electronic)	9798350313277
DOIs	https://doi.org/10.1109/ICTC58733.2023.10393331
Publication status	Published - 2023
Event	14th International Conference on Information and Communication Technology Convergence, ICTC 2023 - Jeju Island, Korea, Republic of Duration: 2023 Oct 11 → 2023 Oct 13

Publication series

Name	International Conference on ICT Convergence
ISSN (Print)	2162-1233
ISSN (Electronic)	2162-1241

Conference

Conference	14th International Conference on Information and Communication Technology Convergence, ICTC 2023
Country/Territory	Korea, Republic of
City	Jeju Island
Period	23/10/11 → 23/10/13

Bibliographical note

Publisher Copyright:
© 2023 IEEE.

ASJC Scopus subject areas

Information Systems
Computer Networks and Communications

Access to Document

10.1109/ICTC58733.2023.10393331

Cite this

Min, G., & Heo, J. (2023). Design of quantum approximate optimization algorithm for graph multi coloring problem. In ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence: Exploring the Frontiers of ICT Innovation (pp. 517-519). (International Conference on ICT Convergence). IEEE Computer Society. https://doi.org/10.1109/ICTC58733.2023.10393331

Design of quantum approximate optimization algorithm for graph multi coloring problem. / Min, Gunsik; Heo, Jun.
ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence: Exploring the Frontiers of ICT Innovation. IEEE Computer Society, 2023. p. 517-519 (International Conference on ICT Convergence).

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

Min, G & Heo, J 2023, Design of quantum approximate optimization algorithm for graph multi coloring problem. in ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence: Exploring the Frontiers of ICT Innovation. International Conference on ICT Convergence, IEEE Computer Society, pp. 517-519, 14th International Conference on Information and Communication Technology Convergence, ICTC 2023, Jeju Island, Korea, Republic of, 23/10/11. https://doi.org/10.1109/ICTC58733.2023.10393331

Min G, Heo J. Design of quantum approximate optimization algorithm for graph multi coloring problem. In ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence: Exploring the Frontiers of ICT Innovation. IEEE Computer Society. 2023. p. 517-519. (International Conference on ICT Convergence). doi: 10.1109/ICTC58733.2023.10393331

@inproceedings{5de11b04443c4b61b1de3ead504492ff,

title = "Design of quantum approximate optimization algorithm for graph multi coloring problem",

abstract = "We propose a technique to solve the problem of graph multi coloring, which is a problem corresponding to channel allocation problem, with the quantum approximate optimization algorithm(QAOA). QAOA is an algorithm that solve an optimization problem. Among the optimization problems, this algorithm is specialized as solving the quadratic unconstrained binary optimization(QUBO) problems. It is designed to find approximate solutions to combinatorial optimization problems by leveraging quantum resources. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph or applying algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations.",

author = "Gunsik Min and Jun Heo",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 14th International Conference on Information and Communication Technology Convergence, ICTC 2023 ; Conference date: 11-10-2023 Through 13-10-2023",

year = "2023",

doi = "10.1109/ICTC58733.2023.10393331",

language = "English",

series = "International Conference on ICT Convergence",

publisher = "IEEE Computer Society",

pages = "517--519",

booktitle = "ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence",

}

TY - GEN

T1 - Design of quantum approximate optimization algorithm for graph multi coloring problem

AU - Min, Gunsik

AU - Heo, Jun

PY - 2023

Y1 - 2023

N2 - We propose a technique to solve the problem of graph multi coloring, which is a problem corresponding to channel allocation problem, with the quantum approximate optimization algorithm(QAOA). QAOA is an algorithm that solve an optimization problem. Among the optimization problems, this algorithm is specialized as solving the quadratic unconstrained binary optimization(QUBO) problems. It is designed to find approximate solutions to combinatorial optimization problems by leveraging quantum resources. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph or applying algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations.

AB - We propose a technique to solve the problem of graph multi coloring, which is a problem corresponding to channel allocation problem, with the quantum approximate optimization algorithm(QAOA). QAOA is an algorithm that solve an optimization problem. Among the optimization problems, this algorithm is specialized as solving the quadratic unconstrained binary optimization(QUBO) problems. It is designed to find approximate solutions to combinatorial optimization problems by leveraging quantum resources. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph or applying algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations.

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

U2 - 10.1109/ICTC58733.2023.10393331

DO - 10.1109/ICTC58733.2023.10393331

M3 - Conference contribution

AN - SCOPUS:85184594677

T3 - International Conference on ICT Convergence

SP - 517

EP - 519

BT - ICTC 2023 - 14th International Conference on Information and Communication Technology Convergence

PB - IEEE Computer Society

T2 - 14th International Conference on Information and Communication Technology Convergence, ICTC 2023

Y2 - 11 October 2023 through 13 October 2023

ER -

Design of quantum approximate optimization algorithm for graph multi coloring problem

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this