Back to Search Start Over

A degree reduction method for an efficient QUBO formulation for the graph coloring problem

Authors :
Hong, Namho
Jung, Hyunwoo
Kang, Hyosang
Lim, Hyunjin
Seol, Chaehwan
Um, Seokhyun
Publication Year :
2023

Abstract

We introduce a degree reduction method for symmetric polynomials on binary variables. 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 method. The data shows that our method produces quadratic polynomial of less variables than the conventional method. The algorithm for our new degree reduction method is robust, and applies to any QUBO formulation for quantum annealing systems.

Subjects

Subjects :
Quantum Physics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2306.12081
Document Type :
Working Paper