A challenging, week-long antenna scheduling problem (12 antennas, 30 missions to track) was solved using three techniques: formulated as a QUBO problem and solved on the D-Wave hybrid (quantum-classical) solver, formulated as a MILP problem and conventionally solved, and formulated as a DeepRL problem in which an agent learns a policy to deconflict the schedule. All three techniques were able to solve overscheduled problems for multiple weeks with competitive results for the satisfied time fraction for each mission (actual / requested). The quantum hybrid approach showed promise for scaling to larger problems with shorter running times.
A challenging, week-long antenna scheduling problem (12 antennas, 30 missions to track) was solved using three techniques: formulated as a QUBO problem and solved on the D-Wave hybrid (quantum-classical) solver, formulated as a MILP problem and conventionally solved, and formulated as a DeepRL problem in which an agent learns a policy to deconflict the schedule. All three techniques were able to solve overscheduled problems for multiple weeks with competitive results for the satisfied time fraction for each mission (actual / requested). The quantum hybrid approach showed promise for scaling to larger problems with shorter running times.
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.
The purpose of this research is to show the capabilities that quantum computing has to offer for AI. Therefore, the scheduling problem was chosen in order to demonstrate and compare the classical reinforcement learning (CRL) agent with the quantum computing reinforcement learning (QC-RL) agent. This constrained combinatorial optimization problem involves scheduling an oil field with several drilling rigs which are limited in capacity, area limitations, mandatory maintenance periods, weather restrictions and a mobilization costs which is considered along with well priorities and deadlines. Deep reinforcement learning (DRL) can learn adaptive scheduling policies, but value-based agents such as Deep Q-Networks (DQN) are known to exhibit high variance across random initializations. This paper investigates whether a hybrid quantum-classical value function can improve this reliability. We formulate realistic multi-rig drilling scheduling as a Markov Decision Process with action masking over an eight-constraint simulator (24 wells, 6 rigs, 3 areas, 80-day horizon) and compare a classical DQN against a hybrid Quantum DQN in which the value network’s core is a variational quantum circuit via a 4-qubit ZFeatureMap encoding followed by a RealAmplitudes ansatz with 12 trainable quantum parameters, executed using a PyTorch-Qiskit interface. Both agents share an identical training and evaluation protocol (3 seeds × 30 episodes, greedy evaluation) to ensure a controlled comparison. Under greedy evaluation, the hybrid Quantum DQN completes 22.3/24 wells on average versus 17/24 for the classical DQN, achieves an 12.87% higher mean reward (9.12M vs 8.08M), and most significantly reduces the across-seed reward standard deviation by roughly 6.8× (0.202M vs 1.38M). These results indicate that the structurally constrained quantum value function acts as an implicit regularizer, yielding scheduling policies that are markedly more consistent across initializations than a substantially larger classical network. This simulated quantum computing experiment demonstrates the potential for quantum computing in the field of AI.
Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.
Airline and space mission scheduling present complex combinatorial optimization challenges, requiring sophisticated coordination of multiple resources under stringent operational constraints. This paper introduces a novel hybrid quantum-classical framework for scheduling optimization, the Quantum Scheduling Optimization Algorithm (QSOA), addressing crew assignment, gate allocation, and trajectory planning through advanced quantum machine learning techniques. We formulate the scheduling problems as stochastic multi-objective optimization and propose three integrated solution approaches: (1) hybrid quantum optimization via QAOA with constraint-aware loss functions and problem decomposition strategies, (2) classical-quantum integration using graph partitioning and variational circuit optimization, and (3) comprehensive baselines including mixed-integer programming, genetic algorithms, and reinforcement learning formulations. For multi-objective handling, we develop Pareto-optimal sampling techniques combining quantum superposition with classical post-processing for constraint repair and solution refinement. Our experimental evaluation on realistic airline crew scheduling benchmarks and space mission simulators demonstrates significant improvements: the hybrid QSOA achieves 19.2\% cost reduction in airline scheduling compared to classical heuristics, while quantum methods provide competitive solutions for moderate-sized space mission subproblems with 15-18\% improvement in multi-objective trade-offs. The framework shows promise for scalable deployment in real-world transportation networks, with practical implications for next-generation scheduling optimization in complex operational environments.
Quantum computers can potentially solve large-scale combinatorial problems very efficiently when the problems are first converted into the quadratic unconstrained binary optimization (QUBO) format. Scheduling in fifth generation (5G) base stations is a practical combinatorial problem that cannot be solved optimally in real-time using classical computing. We formulate the downlink (DL) multiple-input multiple-output (MIMO) scheduling at 5G base stations as QUBO and analyze the QUBO formulation scalability with respect to the key system parameters. The single-user MIMO (SU-MIMO) QUBO formulation looks promising because the number of QUBO variables grows linearly while the problem search space grows exponentially with increasing number of users. Based on the simulation results, the suboptimal greedy algorithm for the SU-MIMO performs well with a high number of users and low bandwidth. A hybrid approach, where either a quantum solver or a suboptimal low-complexity classical algorithm is selected based on the system parameters, seems sensible in practice. This work paves the way for future quantum and quantum-inspired implementations of scheduling in cellular systems.
Earth imaging satellites are a crucial part of our everyday lives that enable global tracking of industrial activities. Use cases span many applications, from weather forecasting to digital maps, carbon footprint tracking, and vegetation monitoring. However, there are limitations; satellites are difficult to manufacture, expensive to maintain, and tricky to launch into orbit. Therefore, satellites must be employed efficiently. This poses a challenge known as the satellite mission planning problem, which could be computationally prohibitive to solve on large scales. However, close-to-optimal algorithms, such as greedy reinforcement learning and optimization algorithms, can often provide satisfactory resolutions. This paper introduces a set of quantum algorithms to solve the mission planning problem and demonstrate an advantage over the classical algorithms implemented thus far. The problem is formulated as maximizing the number of high-priority tasks completed on real datasets containing thousands of tasks and multiple satellites. This work demonstrates that through solution-chaining and clustering, optimization and machine learning algorithms offer the greatest potential for optimal solutions. This paper notably illustrates that a hybridized quantum-enhanced reinforcement learning agent can achieve a completion percentage of 98.5% over high-priority tasks, significantly improving over the baseline greedy methods with a completion rate of 75.8%. The results presented in this work pave the way to quantum-enabled solutions in the space industry and, more generally, future mission planning problems across industries.