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

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.