Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence

NP problems are closely related to practical optimization problems but often face exponential increases in computation time as problem sizes grow, prompting numerous attempts to accelerate calculations. Quantum annealing has been explored as a promising approach to solve NP problems faster than classical computers. However, it requires expressing cost functions and constraints as an energy function in QUBO format. Parameter settings for QUBO coefficients are often empirical, especially in scheduling problems, where large values may be required, demanding experience and intuition. In this study, we analyzed QUBO generation formulas for three problems classified as coloring problems in Lucas's paper: the graph coloring problem, the clique vertex cover problem, and the integer-length job scheduling problem. We identified the necessity of independent parameters for complex problems. By analyzing QUBO states and eigenvalues from modified formulas, we derived relationships between formula characteristics and optimal QUBO parameter values, along with their calculation methods. Using the quantum annealing machine D-Wave, we validated the derived parameters. Additionally, we visualized the impact of parameter changes on states and eigenvalues using small spin problems. We also demonstrated the existence of independent Ising coefficients that enhance convergence to correct states, depending on optimal parameter changes for ground-state and non-ground-state problems.