Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.
Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.
Abstract Combinatorial optimization problems are pervasive across various real-world industries, yet solving them remains classically intractable due to their nondeterministic polynomial (NP)-hard nature. This paper presents an iterative quantum algorithm based on full quantum gradient descent (QGD) to solve the exact cover problem, a fundamental NP-complete problem serving as a representative scenario of airline tail assignment. We formulate the practical optimization task into a set partitioning framework and subsequently map it onto the ground-state search of an Ising Hamiltonian. By employing a QGD-driven iterative mechanism, the proposed algorithm can evolve the initial state in a quantum register towards a high-fidelity approximation of the Ising ground state within only a few iterations. Numerical simulations validate the algorithm’s effectiveness across various problem scales, encompassing both sparsely and nearly fully connected graph configurations. Results demonstrate that the algorithm achieves high precision with a relatively few number of iterative steps. Compared to existing approaches, this work bypasses complex classical optimization loops and requires significantly less pre-computation overhead, thereby offering a promising and scalable pathway for solving combinatorial optimization problems on future universal quantum computing platforms.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.
Combinatorial optimization problems are foundational in computational science, yet their NP-complete nature renders them classically intractable as problem scales increase. Many such problems can be successfully mapped onto the ground-state search of an Ising Hamiltonian. In this work, we propose a full-quantum iterative algorithm based on the quantum gradient descent (QGD) framework, implemented via the linear combination of unitaries, to solve the standard exact cover problem. By reformulating discrete logical constraints into a quadratic unconstrained binary optimization model, the algorithm evolves an initial uniform superposition state directly within the Hilbert space toward the ground-state subspace. Numerical simulations on instances ranging from different qubits demonstrate that the algorithm achieves high-fidelity convergence with a logarithmic scaling of iteration depth relative to solution precision. Notably, our results reveal that the QGD framework effectively preserves the symmetry of the solution space, allowing for the simultaneous identification of the entire set of optimal results in the presence of ground-state degeneracy. By bypassing complex classical-quantum optimization loops and the associated barren plateau problem, this work provides a robust and scalable full-quantum pathway for resolving high-dimensional logic constraints on future universal quantum computing platforms.
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.
We propose a machine learning based approach to accelerate quantum approximate optimization algorithm (QAOA) implementation which is a promising quantum-classical hybrid algorithm to prove the so-called quantum supremacy. In QAOA, a parametric quantum circuit and a classical optimizer iterates in a closed loop to solve hard combinatorial optimization problems. The performance of QAOA improves with increasing number of stages (depth) in the quantum circuit. However, two new parameters are introduced with each added stage for the classical optimizer increasing the number of optimization loop iterations. We note a correlation among parameters of the lower-depth and the higher-depth QAOA implementations and, exploit it by developing a machine learning model to predict the gate parameters close to the optimal values. As a result, the optimization loop converges in a fewer number of iterations. We choose graph MaxCut problem as a prototype to solve using QAOA. We perform a feature extraction routine using 100 different QAOA instances and develop a training data-set with 13, 860 optimal parameters. We present our analysis for 4 flavors of regression models and 4 flavors of classical optimizers. Finally, we show that the proposed approach can curtail the number of optimization iterations by on average 44.9% (up to 65.7%) from an analysis performed with 264 flavors of graphs.
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.