Recent studies have shown promising results indicating the potential of Noisy Intermediate Scale Quantum (NISQ) devices. In this work, Low-earth Orbit (LEO) satellite network design problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and Quantum Annealing (QA) is utilized to solve the resulting problem with real world setting. Compare to classical approaches, the experimental results indicate improvements in terms of network path length and number of satellite hops in network path that amount to network latency. Further, an iterative post-processing method, Statistical Qubit Freezing (SQF), which freezes initial states of qubits and reduces the size of the problem in each annealing cycle, is proposed and evaluated. Solution found with SQF indicates that SQF in fact allows the system to reach lower energy state.
Recent studies have shown promising results indicating the potential of Noisy Intermediate Scale Quantum (NISQ) devices. In this work, Low-earth Orbit (LEO) satellite network design problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and Quantum Annealing (QA) is utilized to solve the resulting problem with real world setting. Compare to classical approaches, the experimental results indicate improvements in terms of network path length and number of satellite hops in network path that amount to network latency. Further, an iterative post-processing method, Statistical Qubit Freezing (SQF), which freezes initial states of qubits and reduces the size of the problem in each annealing cycle, is proposed and evaluated. Solution found with SQF indicates that SQF in fact allows the system to reach lower energy state.
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.
Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. In this paper, we study how to use quantum computing to solve BP problems. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. Therefore, we propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.
Abstract The scheduling complexity of Agile Earth Observation Satellites (AEOSs) increases significantly as Earth Observation missions progress. This makes traditional optimization techniques less effective, restricting their application to small-scale and open-loop scheduling problems. In this paper, we investigate the potential of quantum solvers to address the closed-loop scheduling problem for a formation of AEOSs, overcoming the limitations of classical optimization techniques. To this end, we formulate the scheduling problem as a novel Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e., a formulation specifically designed for quantum solvers. Moreover, penalty functions are introduced to minimize mission energy consumption and reduce deviations between the original and rescheduled solutions. The formulated QUBO problem is implemented on a D-Wave quantum annealer for a daily and large-scale scheduling scenario. The obtained results demonstrate significant improvements in computational efficiency and solution quality compared to traditional methods like Simulated Annealing and Tabu Search, highlighting the potential of quantum solvers in optimizing complex scheduling tasks for AEOS formations.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Abstract The rapid accumulation of space debris in Low Earth Orbit (LEO) poses a significant challenge to the sustainability of space operations. While preventive measures limit new debris generation, they are insufficient to mitigate the growing population of defunct satellites, rocket stages, and collision fragments. Active Debris Removal (ADR) has emerged as a viable solution, which requires solving NP-hard combinatorial optimization problemsimilar to the Traveling Salesman Problem (TSP) to maximize mission efficiency by minimizing fuel and mission duration. This work explores the application of Quantum Annealing (QA) and Hybrid Quantum Annealing (HQA) for optimizing multi-target ADR missions. Specifically, it introduces a Quadratic Unconstrained Binary Optimization (QUBO) model for ADR, exploiting quantum computing to enhance solution efficiency. A novel quadratization method is developed to reduce computational complexity, enabling large-scale mission planning. Additionally, a novel constraint-handling strategy is proposed, integrating mission constraints into post-processing to enhance quantum solver efficiency. The proposed approach is validated using real-world satellite debris datasets and benchmarked against classical metaheuristic optimizers, including Simulated Annealing (SA), Tabu Search (TS), and Genetic Algorithms (GA). The obtained results demonstrate the advantages of quantum optimization for ADR mission planning, providing a scalable and computationally efficient solution.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.