Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives within allowed parameters subject to constraints. The missions of interest here, involve routing multiple UAVs visiting multiple targets, utilising sensors to capture data relating to each target. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. Furthermore, during the mission new constraints and objectives may arise, requiring a new solution to be computed within a short time period. To achieve this we investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods. We demonstrate how a large family of these problems can be formulated as a Mixed Integer Linear Program (MILP) and then converted to a Quadratic Unconstrained Binary Optimisation (QUBO). The formulation provided is versatile and can be adapted for many different constraints with clear qubit scaling provided. We discuss the results of solving the QUBO formulation using commercial quantum annealers and compare the solutions to current edge classical solvers. We also analyse the results from solving the QUBO using Quantum Approximate Optimisation Algorithms (QAOA) and discuss their results. Finally, we also provide efficient methods to encode to the problem into the Variational Quantum Eigensolver (VQE) formalism, where we have tailored the ansatz to the problem making efficient use of the qubits available.
Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives within allowed parameters subject to constraints. The missions of interest here, involve routing multiple UAVs visiting multiple targets, utilising sensors to capture data relating to each target. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. Furthermore, during the mission new constraints and objectives may arise, requiring a new solution to be computed within a short time period. To achieve this we investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods. We demonstrate how a large family of these problems can be formulated as a Mixed Integer Linear Program (MILP) and then converted to a Quadratic Unconstrained Binary Optimisation (QUBO). The formulation provided is versatile and can be adapted for many different constraints with clear qubit scaling provided. We discuss the results of solving the QUBO formulation using commercial quantum annealers and compare the solutions to current edge classical solvers. We also analyse the results from solving the QUBO using Quantum Approximate Optimisation Algorithms (QAOA) and discuss their results. Finally, we also provide efficient methods to encode to the problem into the Variational Quantum Eigensolver (VQE) formalism, where we have tailored the ansatz to the problem making efficient use of the qubits available.
Drone-delivery planning combines routing decisions with operational constraints such as payload capacity and limited onboard energy, resulting in combinatorial optimization problems that can become costly to encode directly in binary form. This work investigates a hybrid quantum--classical approach in which candidate drone missions are generated and evaluated classically before constructing a quadratic unconstrained binary optimization (QUBO) model for mission selection. Payload- and energy-infeasible missions are removed during preprocessing, while the reduced QUBO is solved using exact enumeration, simulated annealing (SA), and the Quantum Approximate Optimization Algorithm (QAOA), with mixed-integer linear programming (MILP) used as a classical reference. Experiments on controlled synthetic delivery instances evaluate solution quality, the effect of preprocessing, and computational scaling. Exact QUBO optimization reproduces the MILP optimum on the evaluated small instances, while SA achieves 100% feasibility with a median optimality gap of 0%. Combined payload-and-energy preprocessing reduces the mean number of QUBO variables by 29.60% and quadratic interactions by 49.20%, while reducing mean SA runtime by 31.26%. In contrast, the evaluated shallow statevector-based QAOA configuration achieves lower feasibility and is restricted to small QUBO instances. These results indicate that, in the considered setting, the main practical benefit of the hybrid architecture comes from classical feasibility preprocessing that reduces the binary search space before QUBO-based optimization.
Mission planning for multiple unmanned aerial vehicles (UAVs) is a complex problem that is expected to be solved by quantum computing. With the increasing application of UAVs, the demand for efficient conflict management strategies to ensure airspace safety continues to increase. In the era of noisy intermediate-scale quantum (NISQ) devices, variational quantum algorithms (VQA) for optimizing parameterized quantum circuits with the help of classical optimizers are currently one of the most promising strategies to gain quantum advantage. In this paper, we propose a mathematical model for the UAV collision avoidance problem that maps the collision avoidance problem to a quadratic unconstrained binary optimization (QUBO) problem. The problem is formulated as an Ising Hamiltonian, then the ground state is solved using two kinds of VQAs: the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). We select conditional value-at-risk (CVaR) to further promote the performance of our model. Four examples are given to validate that with our method the probability of obtaining a feasible solution can exceed 90% based on appropriate parameters, and our method can enhance the efficiency of a UAVs' collision avoidance model.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Consider a constellation of n satellites in medium-earth orbit as well as k ground stations distributed over the Earth. Such satellites require semiregular contacts with mission control in order to upload telecommands or general purpose maintenances, which is done via ground stations. In order to plan ground station contacts for such a constellation it is necessary to calculate possible visibilities between satellite--ground station pairs, and then build a valid schedule from that data which satisfies all mission-specific constraints. This is a typical challenge for the mission planning system of a satellite constellation. In addition, there is often some kind of relevant optimization goal, for example fairness conditions or minimization of total number of contacts to have more time available for the actual missions objectives. Depending on the constraints for such ground station contact plans as well as the size of n and k, this problem may be hard to solve optimally. In particular, if k is much smaller than n it may be non-trivial to find any solution at all. For such problems one often employs global optimizers such as Gurobi, CPLEx or SCIP, or problem-specific heuristic search algorithms that try to find a solution that is good enough for practical purposes. While such approaches can be made to work for most real scenarios, classical solvers tend to struggle to find solutions in a reasonable time for very large satellite constellations. Due to this reason, we investigate potential applications of quantum computers to larger instances of this problem in this paper. To this end, we developed a library called QUARGS (Quantum Reinforced Ground Station Scheduling) which allows solving examples for such ground station scheduling problems using different quantum algorithms. In this paper we compare and evaluate these different solutions against each other as well as against a classical solution using the global optimizer SCIP. After an overview of similar problems in the literature we define the concrete problem including all constraints as well as possible optimization functions. Then we give a brief overview of quantum algorithms that may be used to solve such scheduling problems. This includes in particular quantum annealing (QA), quantum approximate optimization algorithm (QAOA), variational quantum eigensolvers (VQE), as well as evolutionary variational quantum eigensolvers (E-VQE). The latter in particular was implemented and published in an open-source Python library QUEASARS (Quantum Evolving Ansatz Variational Solver). Besides evaluating these algorithms on sample cases regarding their solution quality and quantum circuit depths, we discuss difficulties for the implementation of various constraints in the algorithms and their potential solutions.
The increasing availability of quantum hardware has stimulated interest in applying quantum algorithms to combinatorial optimization problems. Collision avoidance for unmanned aerial vehicles (UAVs) is one such challenge due to the computational complexity of coordinating multiple agents in shared airspace. In this paper, we formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model that captures route selection and collision constraints, enabling the use of the Quantum Approximate Optimization Algorithm (QAOA). To improve efficiency, we introduce a constrained QAOA Ansatz employing an XY-mixer that preserves one-hot route assignment constraints and restricts the search space to valid solutions. We evaluate the approach through noiseless simulations and device-based noise models, analyzing its behavior under realistic conditions and highlighting the opportunities and limitations of near-term quantum hardware for multi-agent routing problems.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.