Abstract Quantum algorithms have the potential to solve combinatorial optimization problems faster than classical algorithms. A particular example for combinatorial optimization problems are scheduling problems. This work provides summarizes quantum or quantum-inspired algorithms for scheduling problems, providing an overview of 20 years of research. We categorize the approaches by problem type and algorithm type. A condensation of the reviewed literature to the main ideas and details about the considered problem size, solvers and evaluation metrics enables a quick comparison with and placement into the current state of research for future works. We further critically assess the comparability of the reviewed literature and present crucial metrics for future comparison.
Abstract Quantum algorithms have the potential to solve combinatorial optimization problems faster than classical algorithms. A particular example for combinatorial optimization problems are scheduling problems. This work provides summarizes quantum or quantum-inspired algorithms for scheduling problems, providing an overview of 20 years of research. We categorize the approaches by problem type and algorithm type. A condensation of the reviewed literature to the main ideas and details about the considered problem size, solvers and evaluation metrics enables a quick comparison with and placement into the current state of research for future works. We further critically assess the comparability of the reviewed literature and present crucial metrics for future comparison.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.
A new paradigm in computing, quantum computing has the ability to solve computational problems that were previously considered impossible for classical computers. Optimization problems are fundamental to many disciplines, including operations research, finance, machine learning, and logistics; this article investigates how quantum computing methods can be used to solve these problems. In order to conduct calculations in a way that is radically distinct from classical computers, quantum computers utilize quantum mechanical phenomena like entanglement and superposition. Because of this, quantum algorithms might potentially achieve exponential speedups over classical algorithms for specific optimization tasks by simultaneously exploring large solution spaces. A number of well-known quantum algorithms have been reviewed in this abstract, including Grover's algorithm and quantum annealing methods created by D-Wave Systems, among others. These algorithms aim to solve a wide variety of optimization problems, such as scheduling issues, optimization of portfolios, and combinatorial optimization. Their computational complexity, theoretical foundations, and real-world applications on existing and future quantum hardware are covered in detail.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them -- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks: genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximate optimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digital annealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizes both tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealing through the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications to job-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. The consistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallow achievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubit count, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classical heuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic, online scheduling as the field's clearest open problems.
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.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them-- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks:genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximateoptimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digitalannealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizesboth tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealingthrough the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications tojob-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. Theconsistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallowachievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubitcount, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classicalheuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic,online scheduling as the field's clearest open problems.
The twenty-first century has been the era of data. Algorithms are crucial in tasks ranging from simple document searches to complex batching and scheduling jobs. Optimization techniques are often applied to enhance algorithms and achieve better results. As Moore rightly predicted, the exponential increase in transistors has led to a point where classical computers can no longer solve specific problems within a human timeframe. This paved the way for the development of quantum computers, which utilize quantum phenomena to solve problems. Quantum optimization techniques and algorithms have been designed to leverage the quantum advantage for improved optimization. This research compares and presents the results of quantum optimization techniques applied to classic combinatorial algorithms.