  The design of a good algorithm to solve NP-hard combinatorial approximation
problems requires specific domain knowledge about the problems and often needs
a trial-and-error problem solving approach. Graph coloring is one of the
essential fields to provide an efficient solution for combinatorial
applications such as flight scheduling, frequency allocation in networking, and
register allocation. In particular, some optimization algorithms have been
proposed to solve the multi-coloring graph problems but most of the cases a
simple searching method would be the best approach to find an optimal solution
for graph coloring problems. However, this naive approach can increase the
computation cost exponentially as the graph size and the number of colors
increase. To mitigate such intolerable overhead, we investigate the methods to
take the advantages of quantum computing properties to find a solution for
multi-coloring graph problems in polynomial time. We utilize the variational
quantum eigensolver (VQE) technique and quantum approximate optimization
algorithm (QAOA) to find solutions for three combinatorial applications by both
transferring each problem model to the corresponding Ising model and by using
the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA
algorithms can find one of the best solutions for each application. Therefore,
our modeling approach with hybrid quantum algorithms can be applicable for
combinatorial problems in various fields to find an optimal solution in
polynomial time.
