Abstract An assignment problem is a mapping between the tasks and agents aiming for the optimal cost. In graph theory, it is represented by a bipartite graph of tasks and agents connected optimally through edges. It is a combinatorial optimization, a type of NP category that makes it hard to solve in a limited time for large inputs. Quantum approximate optimization algorithm (QAOA), a hybrid‐quantum optimization, is a possible way to solve such combinatorial problems in quantum computing. Quantum computation exploits the theory of quantum physics for accelerated computation. In this study, the assignment problem is framed to quadratic unconstrained binary optimization and the Ising model for the execution in QAOA. The details of classical to quantum conversion, modeling, circuit implementation, and various analyses are explained with an example.
Abstract An assignment problem is a mapping between the tasks and agents aiming for the optimal cost. In graph theory, it is represented by a bipartite graph of tasks and agents connected optimally through edges. It is a combinatorial optimization, a type of NP category that makes it hard to solve in a limited time for large inputs. Quantum approximate optimization algorithm (QAOA), a hybrid‐quantum optimization, is a possible way to solve such combinatorial problems in quantum computing. Quantum computation exploits the theory of quantum physics for accelerated computation. In this study, the assignment problem is framed to quadratic unconstrained binary optimization and the Ising model for the execution in QAOA. The details of classical to quantum conversion, modeling, circuit implementation, and various analyses are explained with an example.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.
Quadratic unconstrained binary optimization (QUBO) tasks are very important in chemistry, finance, job scheduling, and so on, which can be represented using graph structures, with the variables as nodes and the interaction between them as edges. Variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) and its variants, present a promising way, potentially exceeding the capabilities of classical algorithms, for addressing QUBO tasks. However, the possibility of using message-passing machines, inspired by classical graph neural networks, to enhance the power and performance of these quantum algorithms for QUBO tasks was not investigated. This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism, which demonstrates significant improvements in performance for solving QUBO problems in terms of resource efficiency and solution precision, compared to QAOA, its variants, and other quantum graph neural networks. Furthermore, in terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA, presenting a substantial advancement in the field of quantum approximate optimization.
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.
Combinatorial Optimization (CO) is one of the most important areas in the field of optimization, with practical applications found in every industry, including both the private and public sectors. In recent years, it was discovered that a mathematical formulation known as QUBO (Quadratic Unconstrained Binary Optimization) problem can embrace an exceptional variety of important CO problems found in the industry. In this work, we explore the Quantum Approximate Optimization Algorithm (QAOA) as a quantum computing approach to solve the Knapsack Problem efficiently by formulating the problem as a QUBO model. Here we implemented QAOA on a quantum emulator, leveraging quantum superposition and entanglement to explore multiple solutions simultaneously. The method offers a promising route for solving large, complex scheduling and resource allocation problems that are tough for classical algorithms, with potential applications in logistics, HPC resource scheduling, and energy optimization.
Autonomous Mobile Robots (AMRs) play an increasingly important role in flexible and reconfigurable production systems. Assigning heterogeneous tasks to multiple AMRs constitutes a combinatorial optimization problem that becomes computationally intractable as system complexity grows. This paper presents a Quadratic Unconstrained Binary Optimization (QUBO) model for AMR task assignment, integrating scheduling and resource allocation within a Hamiltonian formulation. The model is parameterized and evaluated using both exact and heuristic solvers to analyze scalability and validity across benchmark scenarios. Results demonstrate the trade-off between computational effort and solution optimality, confirming the feasibility of the QUBO representation for this problem class. The formulated model creates a basis for future implementation on quantum hardware for optimization using Quantum Annealing (QA) or the Quantum Approximate Optimization Algorithm (QAOA), thereby bridging the gap between classical optimization methods and new quantum computing paradigms.
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.