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.
The Quantum Approximate Optimization Algorithm (QAOA) is a near-term quantum algorithm for solving combinatorial optimization problems, but its accuracy and resource requirements may scale poorly with problem size or structure, reducing its utility in practice. Approaches such as the Graph Decomposition for Optimization Algorithm (GDOA) seek to address this by iteratively reducing an input problem until it reaches a size where it can be solved using QAOA while maintaining the same optimal solution. This algorithm, however, requires solving integer programs that have exponentially many variables, and can result in suboptimal solutions, as the integer programs may contain slack terms. In this work, we propose a heuristic called the Quantum Enhanced Graph Decomposition (QEGD) algorithm. Its novelty lies in its use of QAOA as a subroutine for sparsifying a graph through local vertex-merging. The algorithm, when used to sparsify MaxCut problems that are then solved using QAOA, achieves higher approximation ratios across all tested graphs than GDOA for random 5-regular and 6-regular graphs. We then compare the time-to-solution and approximation ratio of QEGD to other QAOA variants a collection of Erdös-Rényi graphs. QEGD has higher approximation ratios on average than QAOA
2 and ParaQAOA on all tested graphs. It also results in higher average approximation ratios than DC-QAOA on sparse Erdös-Rényi graphs and comparable average approximation ratio on denser Erdös-Rényi graphs. However, its average wall-clock time is between 0.4\% and 5\% of the average DC-QAOA wall-clock time.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.