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.
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.
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.
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.
In this study, we explore Quantum Annealing (QA) as a new method for determining the optimal observation schedule for the radar MARSIS onboard the Mars Express mission, with the aim of obtaining a high-quality coverage of the South Pole of Mars. The MARSIS observation plan is greatly influenced by space weather and it is constrained by the limited hardware of the Mars Express spacecraft. In this work, we build upon previous research on classical optimization algorithms and present a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation, tailored for execution on the D-Wave quantum annealer. We test the solution of the QUBO formulation through QA on small-scale instances of the problem, derived from real data provided by the MARSIS operation center. We also study the effects of the penalties introduced in the QUBO and compare QA with classical algorithms, drawing some conclusion on the current applicability of this new technology.
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.
Quantum annealing (QA) offers a physics-inspired approach for such subproblems by mapping them onto an Ising Hamiltonian, which is algebraically equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) model executable on quantum annealers or hybrid solvers. However, their practical employment in wireless systems critically depends on the specific problem formulation, on the particular variable encoding, constraint handling, solver selection, hardware embedding, and fair benchmarking. This paper develops wireless-oriented QUBO modeling guidelines for QA-assisted resource allocation. We first present a beginner-friendly toy example in which a terrestrial-aerial resource-allocation problem with a fractional signal-to-interference-plus-noise ratio (SINR) maximization objective is reformulated into a two-bit QUBO via Boolean interpolation, converted into an Ising representation, and decoded back into a wireless scheduling decision. The same scheduling is applicable to UAV, aircraft, satellite, and terrestrial links in SAGIN systems. We then review the QA foundations and solver ecosystems, including binary quadratic, discrete quadratic, constrained quadratic, and hybrid models from the perspective of NG wireless optimization. Furthermore, we discuss both binary and discrete encoding, penalty-based constraint conversion, embedding overhead, solution decoding, and feasibility verification. A QUBO Compatibility Index is introduced as a lightweight diagnostic metric for assessing the associated QUBO formulation readiness, rather than a predictor of runtime or solution quality. Finally, a case study on max-min uplink power control in cell-free massive MIMO illustrates how a fairness-oriented wireless problem can be discretized, constrained, converted into the concept of a QUBO, and evaluated against classical baselines. A host of key challenges and future directions are also discussed.
The increasing number of Low Earth Orbit (LEO) satellites, driven by lower manufacturing and launch costs, is proving invaluable for Earth observation missions and low-latency internet connectivity. However, as the number of satellites increases, the number of communication links to maintain also rises, making the management of this vast network increasingly challenging and highlighting the need for clustering satellites into efficient groups as a promising solution. This paper formulates the clustering of LEO satellites as a coalition structure generation (CSG) problem and leverages quantum annealing to solve it. We represent the satellite network as a graph and obtain the optimal partitions using a hybrid quantum-classical algorithm called GCS-Q. The algorithm follows a top-down approach by iteratively splitting the graph at each step using a quadratic unconstrained binary optimization (QUBO) formulation. To evaluate our approach, we utilize real-world three-line element set (TLE/3LE) data for Starlink satellites from Celestrak. Our experiments, conducted using the D-Wave Advantage annealer and the state-of-the-art solver Gurobi, demonstrate that the quantum annealer significantly outperforms classical methods in terms of runtime while maintaining the solution quality. The performance achieved with quantum annealers surpasses the capabilities of classical computers, highlighting the transformative potential of quantum computing in optimizing the management of large-scale satellite networks.