바로가기메뉴

본문 바로가기 주메뉴 바로가기

logo

  • P-ISSN1226-0657
  • E-ISSN2287-6081
  • KCI

ISSN : 1226-0657

Article Contents

Prev Next
e-Submission

Vol.31 No.1

Citation Share

A Degree Reduction Method for an Efficient QUBO Formulation for the Graph Coloring Problem

Journal of the Korean Society of Mathematical Education Series B: The Pure and Applied Mathematics / Journal of the Korean Society of Mathematical Education Series B: The Pure and Applied Mathematics, (P)1226-0657; (E)2287-6081
2024, v.31 no.1, pp.57-81
https://doi.org/10.7468/jksmeb.2024.31.1.57
Hyosang Kang (Daegu Gyeongbuk Institute of Scienceand Technology)
Hyunwoo Jung (Daegu Science High School)
Chaehwan Seol (Gwangju Science Academy)
Namho Hong (Daegu Science High School)
Hyunjin Lim (Daegu Science High School)
Seokhyun Um (Daegu Science High School)
Kang, H., Jung, H., Seol, C., Hong, N., Lim, H., & Um, S. (2024). A Degree Reduction Method for an Efficient QUBO Formulation for the Graph Coloring Problem. Journal of the Korean Society of Mathematical Education Series B: The Pure and Applied Mathematics, 31(1), 57-81, https://doi.org/10.7468/jksmeb.2024.31.1.57

Abstract

We introduce a new degree reduction method for homogeneous symmetric polynomials on binary variables that generalizes the conventional degree reduction methods on monomials introduced by Freedman and Ishikawa. We also design an degree reduction algorithm for general polynomials on binary variables, simulated on the graph coloring problem for random graphs, and compared the results with the conventional methods. The simulated results show that our new method produces reduced quadratic polynomials that contains less variables than the reduced quadratic polynomials produced by the conventional methods.

keywords
degree reduction, graph coloring, QUBO, quantum annealing

Journal of the Korean Society of Mathematical Education Series B: The Pure and Applied Mathematics

e-Submission OA Policy