Symmetric degree reduction on random graphs

To utilize a quantum annealing system such as D-Wave's to solve a graph coloring problem, it is necessary to convert the utility polynomial into a quadratic polynomial in binary variables. This is called QUBO (quadratic unconstrained binary optimization) problem. In any degree reduction process, we need to introduce auxiliary variables, and more variables we have in the QUBO problem, less likely a quantum annealing system can find an optimal solution. The current degree reduction methods applies to monomials. We designed a new degree reduction method that applies to symmetric polynomials. We simulate the new method on random graphs and compare with the monomial-wise degree reduction methods. We created random p-graphs and their utility polynomials for various p and vertex sizes. Then we applied degree reduction methods to the polynomials. Each file contains information on numbers of variables and monomials of the reduced polynomials.