Datasets
Standard Dataset
Symmetric degree reduction on random graphs
- Citation Author(s):
-
HyosangKang
Daegu Gyeongbuk Institute of Science and Technology - Submitted by:
- Hyosang Kang
- Last updated:
- Mon, 07/08/2024 - 15:58
- DOI:
- 10.21227/8qfp-qx18
- Data Format:
- License:
4 Views- Categories:
- Keywords:
Abstract
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.
The name of files are formatted as "data-p-[val1]-n-[val2].csv". Each file contains four columns of data. Each row is the result of two degree reduction methods, one is from our new method, called symmetric reduction, and the other is the conventional method, called monomial reduction. To generate the data in a row, we create a random p-graph of vertex [val2] with p=[val1]. Then we create a utility polynomial p of the graph coloring problem with ceil(log_2[val1]) colors of that graph. We obtain two polynomials q1 and q2 of degree 2 from p by the symmetric reduction method (q1) and monomial reduction method (q2) respectively. The first column entry is the number of variables in q1. The second column entry is the number of monomials in q1. The third column entry is the number of variables in q2. The fourth column entry is the number of monomials in q2.
