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

한국수학교육학회지시리즈B:순수및응용수학 / 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

강효상 (대구경북과학기술원)
정현우 (대구과학고등학교)
설채환 (광주과학고등학교)
홍남호 (대구과학고등학교)
임현진 (대구과학고등학교)
엄석현 (대구과학고등학교)

강효상, 정현우, 설채환, 홍남호, 임현진, & 엄석현. (2024). . 한국수학교육학회지시리즈B:순수및응용수학, 31(1), 57-81, https://doi.org/10.7468/jksmeb.2024.31.1.57

복사

다운로드 수
조회수

PDF 다운로드

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

바로가기메뉴

논문 상세

Vol.31 No.1

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

Abstract

한국수학교육학회지시리즈B:순수및응용수학