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.
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.
Satellite communication (SatCom) systems play a vital role in providing global connectivity and enable a wide range of applications, including Internet of Things (IoT) connectivity for remote areas, such as forests and oceans. Two crucial resource allocation challenges in SatCom are beam placement (BP) and frequency assignment (FA) problems, which involve the clique covering (CC) and graph coloring (GC) problems, respectively. Conventional solutions for these problems incur excessive computational cost, which is intractable for classical computers. A promising approach is to formulate these problems using the Ising model, construct their Hamiltonians, and then solve them efficiently by a quantum computer. However, the current quantum computers have very limited hardware and can only handle rather small inputs. To overcome this limitation, we propose a hybrid-quantum-classical-computational pipeline where an efficient hamiltonian reduction method is the key for solving large CC/GC instances. Through experiments on real quantum computers, our reduction method outperforms commercial solutions, allowing quantum annealers to handle significantly larger BP/FA instances while maintaining high probability to achieve feasible solutions and near-optimal performance. Although the inherent hardness of the CC/GC problems cannot be overcome by quantum computing, our research contributes to the early exploration of quantum computing in the context of the complex optimization problems in SatCom systems, particularly in the realm of IoT connectivity for remote areas.
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.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
Field-Programmable Gate Arrays (FPGAs) have become indispensable components in modern computing, providing adaptable and reconfigurable hardware platforms. FPGA-based accelerators offer promising avenues for advancements in diverse fields such as real-time data processing, machine learning, and cryptography. However, optimizing the spatial arrangement of functional blocks on an FPGA, known as placement, presents a challenging task due to its NP-hard nature, necessitating sophisticated algorithms for efficient solutions. Enhancing the placement process directly translates to reduced resource utilization during implementation. Quantum computing (QC) presents a promising approach for tackling such combinatorial problems by exploring vast solution spaces. In this paper, we propose a novel approach to the placement problem, re-formulating it as a series of quadratic unconstrained binary optimization (QUBO) problems, which we then solve using QC. Our novel formulation allows for straightforward integration of design constraints and enables the adaptation of sub-problem sizes to match hardware capabilities. Alongside presenting our method, we also investigate the resilience of contemporary quantum hardware in finding placements for real-world-sized FPGAs. A numerical assessment conducted on a D-Wave Advantage 5.4 quantum annealer indicates that the answer is indeed positive.
In this work we explore the use of quantum computers in solving the NP-hard placement problem of the Field-Programmable Gate Array (FPGA) implementation phase and introduce a novel approach suited for current quantum hardware sizes. Adiabatic quantum computing (AQC), with its capability to traverse expansive solution spaces, is a good fit for addressing this combinatorial problem with its exponentially large solution space. Instead of solving a single the whole problem at once, we re-formulate the placement problem as a series of so called quadratic unconstrained binary optimization (QUBO) problems which are subsequently solved via AQC. Our novel formulation facilitates a straight-forward integration of design constraints. Moreover, the size of the sub-problems can be conveniently adapted to the available hardware capabilities. Beside the sole proposal of a novel method, we ask whether contemporary quantum hardware is resilient enough to find placements for real-world-sized FPGAs. A numerical evaluation on a D-Wave Advantage 5.4 quantum annealer suggests that the answer is in the affirmative.
Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.