2019/11/01 by Young-Hyun Oh, Hamed Mohammadbagherpoor, Oh, Young-Hyun +10 · 2 citations
Computer Science · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #cs.DS #quant-ph
paper · pdf · doi:10.48550/arxiv.1911.00595
openalex publication_date 2019/11/01 · arxiv created 2019/12/02 · arxiv updated 2019/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.