Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Physics Conference Series

Exploiting adiabatic quantum computing in deep space missions

Rebecca Casati, Enrico Prati

Published Jun 1, 2025• 0 citations
Publisher

Abstract

Abstract Several fundamental questions demand space exploration, posing tremendous computational tasks to address modelling and data processing. Quantum computing has been proposed to address deep space-related problems from quantum gravity, nuclear processes and many-body field theory simulation to artificial intelligence and related space mission planning. Adiabatic quantum computers have been proposed for solving optimization problems, such as space mission scheduling. The problem of assigning jobs to resources in a scientific mission, while satisfying certain constraints, can be tackled with the help of D-Wave’s quantum annealer, which exploits the adiabatic theorem to find the minimum energy solutions of a given system, encoded as the Hamiltonian of a quadratic unconstrained binary optimization (QUBO) problem. In its simplest em-bodiement, the scheduling can be implemented as a graph coloring (GC) problem, where the goal is to assign different colors (out of a given set) to connected nodes of an input graph, while respecting given constraints. The feasibility of our methods and the performance of quantum annealers are studied on randomly generated GC instances. A second framework studied is the job shop scheduling problem (JSP) that encodes more real-like scheduling problems of interest to agencies and industries. By implementing the problems with a QUBO formulation, we are able to find the optimal solution to three JSP instances present in the literature. The biggest one is solved with a quantum computation approach here for the first time.

DOI
10.1088/1742-6596/3017/1/012042

Related papers

Iterative Quantum Annealing for Job Shop Scheduling with a Directed Graph Representation

Rebecca Casati, Thomas Giudici, Pietro Torta +1 more

A promising use of quantum computers lies in the logistics and scheduling of industrial problems, such as space mission planning, maritime management, and many others. This field is expected to provide useful applications for quantum computing at the current stage of hardware development. Quantum annealing techniques have been proposed to solve scheduling problems, along with many other optimization problems. In this work, we test quantum annealing and hybrid techniques based on the D-Wave hardware to solve scheduling problems in the framework of job shop scheduling (JSP), which consists of optimally assigning operations to certain resources, while satisfying specific constraints and minimizing the total scheduling time, known as timespan. We devised an iterative algorithm that produces valid schedules for decreasing timespan values. We implemented a refined iterative variable pruning technique, which significantly reduces the number of spin variables in the corresponding Ising model, whose low-energy configurations are sampled by using the D-Wave Hybrid Solver Service. Our novel iterative algorithm leverages a directed acyclic graph (DAG) representation of partial or complete solutions of the JSP instance, which enables an efficient update of the feasible processing time windows for each operation. This approach leads to significantly improved results compared to the standard state-of-the-art applications of quantum annealing for the JSP. Remarkably, we can often prove the absolute optimality of the obtained solution, namely that a more efficient schedule within a shorter timespan can not exist.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Quantum Computing for Scheduling Problems: A Survey

Sirine Ben Ammar, Bilel Marzouki, Olfa Belkahla Driss

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.

IEEE Afro-Mediterranean Conference on Artificial Intelligence (AMCAI)•Oct 14, 2025•0 citations

Quantum Annealing Implementation of Job-Shop Scheduling

Davide Venturelli, D. J. J. Marchand, Galo Rojo

A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.

arXiv:1506.08479•Jun 29, 2015•135 citations

Solving the Job Shop Scheduling Problem: QUBO model and Quantum Annealing

Riad Aggoune, Samuel Deleplanque

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.

•Apr 17, 2023•0 citations

Deep Space Network Scheduling Using Quantum Annealing

Alexandre Guillaume, Edwin Y. Goh, Mark D. Johnston +4 more

NASA's Deep Space Network (DSN) is responsible for communication and navigation for several NASA and international missions. The DSN comprises three complexes located in Goldstone (California, USA), Cambera (Australia) and Madrid (Spain). This distribution in longitude guarantees a full sky coverage. Each complex has one 70-meter and several 34-meter antennas. The network routinely serves a few dozens missions. The scheduling of the DSN is complex and involves humans interventions as well as automated solutions. In order to increase the level of automation, different computing paradigms have been explored. In this paper, we report on the quadratic unconstrained binary optimization (QUBO) formulation of the DSN scheduling, as well as a custom classical solver designed around some of the unique features of this scheduling problem. Thanks to a hybrid framework that extends the size of the problems that can be solved with a quantum annealer, we are able to generate a schedule from the QUBO formulation of the problem for one week's worth of user antenna requests, which represents the time period scheduled during operation. In other words, this work describes a real- world application of quantum annealing using real-world, operational data. We compare the resulting schedules' quality to solutions obtained using a mixed-integer linear programming formulation on a commercial solver. Our custom solver, based on a quantum-inspired optimization technique called Substochatic Monte-Carlo, while much faster in generating schedules, could only treat a subset of requests and hence we report its results independently.

IEEE Transactions on Quantum Engineering•Jan 1, 2022•16 citations

Solving Scheduling Problems with Quantum Computing: a Study on Flexible Open Shop

Marco Baioletti, Angelo Oddi, Riccardo Rasconi

Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•3 citations
Abstract Several fundamental questions demand space exploration, posing tremendous computational tasks to address modelling and data processing. Quantum computing has been proposed to address deep space-related problems from quantum gravity, nuclear processes and many-body field theory simulation to artificial intelligence and related space mission planning. Adiabatic quantum computers have been proposed for solving optimization problems, such as space mission scheduling. The problem of assigning jobs to resources in a scientific mission, while satisfying certain constraints, can be tackled with the help of D-Wave’s quantum annealer, which exploits the adiabatic theorem to find the minimum energy solutions of a given system, encoded as the Hamiltonian of a quadratic unconstrained binary optimization (QUBO) problem. In its simplest em-bodiement, the scheduling can be implemented as a graph coloring (GC) problem, where the goal is to assign different colors (out of a given set) to connected nodes of an input graph, while respecting given constraints. The feasibility of our methods and the performance of quantum annealers are studied on randomly generated GC instances. A second framework studied is the job shop scheduling problem (JSP) that encodes more real-like scheduling problems of interest to agencies and industries. By implementing the problems with a QUBO formulation, we are able to find the optimal solution to three JSP instances present in the literature. The biggest one is solved with a quantum computation approach here for the first time.
A promising use of quantum computers lies in the logistics and scheduling of industrial problems, such as space mission planning, maritime management, and many others. This field is expected to provide useful applications for quantum computing at the current stage of hardware development. Quantum annealing techniques have been proposed to solve scheduling problems, along with many other optimization problems. In this work, we test quantum annealing and hybrid techniques based on the D-Wave hardware to solve scheduling problems in the framework of job shop scheduling (JSP), which consists of optimally assigning operations to certain resources, while satisfying specific constraints and minimizing the total scheduling time, known as timespan. We devised an iterative algorithm that produces valid schedules for decreasing timespan values. We implemented a refined iterative variable pruning technique, which significantly reduces the number of spin variables in the corresponding Ising model, whose low-energy configurations are sampled by using the D-Wave Hybrid Solver Service. Our novel iterative algorithm leverages a directed acyclic graph (DAG) representation of partial or complete solutions of the JSP instance, which enables an efficient update of the feasible processing time windows for each operation. This approach leads to significantly improved results compared to the standard state-of-the-art applications of quantum annealing for the JSP. Remarkably, we can often prove the absolute optimality of the obtained solution, namely that a more efficient schedule within a shorter timespan can not exist.
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.
A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.
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.
NASA's Deep Space Network (DSN) is responsible for communication and navigation for several NASA and international missions. The DSN comprises three complexes located in Goldstone (California, USA), Cambera (Australia) and Madrid (Spain). This distribution in longitude guarantees a full sky coverage. Each complex has one 70-meter and several 34-meter antennas. The network routinely serves a few dozens missions. The scheduling of the DSN is complex and involves humans interventions as well as automated solutions. In order to increase the level of automation, different computing paradigms have been explored. In this paper, we report on the quadratic unconstrained binary optimization (QUBO) formulation of the DSN scheduling, as well as a custom classical solver designed around some of the unique features of this scheduling problem. Thanks to a hybrid framework that extends the size of the problems that can be solved with a quantum annealer, we are able to generate a schedule from the QUBO formulation of the problem for one week's worth of user antenna requests, which represents the time period scheduled during operation. In other words, this work describes a real- world application of quantum annealing using real-world, operational data. We compare the resulting schedules' quality to solutions obtained using a mixed-integer linear programming formulation on a commercial solver. Our custom solver, based on a quantum-inspired optimization technique called Substochatic Monte-Carlo, while much faster in generating schedules, could only treat a subset of requests and hence we report its results independently.
Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.