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.
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.
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.
In recent years, quantum computing has emerged as a rapidly advancing interdisciplinary field, attracting growing attention from both academia and industry owing to its fundamentally novel approach to information processing and its potential to achieve computational capabilities beyond the reach of classical systems. This paper presents a structured review of quantum computing approaches applied to scheduling problems, which are among the most challenging NP-hard optimization problems. We first introduce fundamental principles of quantum computing, including gate-based models, quantum annealing, and hybrid frameworks. We then explore how various scheduling problems such as job-shop, flow-shop, and project scheduling-are encoded into quantum models, particularly using QUBO formulations suitable for current quantum devices. Finally, we discuss key limitations such as hardware constraints and model scalability, and we identify research directions to advance quantumenhanced scheduling methods. By grounding theory in empirical case studies and highlighting near-term deployable solutions, this study bridges the gap between quantum algorithm development and practical scheduling demands, offering a roadmap for researchers and practitioners in quantum optimization.
Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
Combinatorial optimization is a foundation of numerous scientific, industrial, and social decision-making questions, but its usefulness is mostly restricted by the exponential complexity of the problem of classical computability. The quantum annealing (QA) has become one of the leading analogue quantum systems to address such problems, whereby optimization problems are converted into physical energy structures and quantum fluctuations are utilized to perform systematic exploration. It provides a critical, synthesized, and comprehensive review of quantum annealing as applied to combinatorial optimization, including the theoretical basis, hardware designs, algorithm methods, issues of embedding and encoding, benchmarking procedures, applications, and integration with quantum algorithms based on gates and solvers on a classical computer. We build a comprehensive taxonomy between adiabatic dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to state-of-the-art flux-qubit annealers, new architectures, and hybrid quantum classical pipelines. We show that the overhead of embedding and encoding and the benchmarking approach taken are the most significant factors in determining scalability and performance, but not the raw number of qubits. Transportation, energy systems, robotics, finance, pharmacological discovery, and machine learning are just some examples of the domain-specific case studies that use QA with minimal empirical utility as a hybrid refinement engine and not an independent solver. Moreover, we introduce a stringent evaluation of the existing benchmarking culture, clarify the causal links between QA and QAOA as well as between VQE and structural predicaments, and reveal the institutional roots of the existing restrictions. We conclude by identifying a research roadmap in the future, focusing on the annealing hardness characterization, Stoquastic control manipulation, embedding rules automation, architecture design, and development of principled quantum advantage. It creates a benchmark reference to those in the field and research and deployment of scalable, reliable, and application-relevant quantum optimization
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.