# Quantum Computing Approaches for Mission Covering Optimization
## 1 Introduction  
Quantum computing hardware is quickly developing [1] together with the theory of quantum computing algorithms [2]. Problems historically solved classically have been translated into quantum computing formulations [3; 4; 5; 6], and these formulations differ even within the various quantum hardware types. In this work, we explore how well constrained optimization can be implemented between two well-known quantum computing hardware types, (i) adiabatic, and (ii) the gate-based. Many constrained optimization problems can be formulated into Quadratic Unconstrained Binary Optimization (QUBO) in which adiabatic and gate-based hardware types solve via quantum annealing and QAOA, respectively.  
To perform our analysis, we choose a constrained optimization problem that can be implemented on current gate-based and annealing hardware. Job-shop scheduling [7] is one particular NP-Hard constrained optimization problem with many applications in industry; it is intractable to obtain exact solutions on classical hardware. There are efforts to compose job-shop scheduling onto quantum hardware [8]; however, this requires many ancillary qubits to encode the many constraints that come with the problem. This is not ideal for current gate-based hardware, as the machines that are used are very limited in qubits. Another industry-useful NP-Hard problem is the generalized assignment problem [9; 10]. The formulation of general assignment on gate-based architecture is also bottlenecked by the qubit amount due to the inequality constraints that are encoded within it. Motivated by the applicability of these classically intractable problems, we construct a new optimization problem we coin as Mission Covering Optimization (MCO) that we believe meets the criteria for our analysis as it is implementable on current quantum hardware (both adiabatic and gate-based) while still having applicability (when scaled) in the industry. Furthermore, specific scenarios of MCO can be designed to set the number of constraints. This is important for analyzing how the implementation may change when additional constraints are added to each problem.  
The goal of this paper is to assess the performance of each algorithm used when solving a particular Mission Covering Optimization problem. Variations of MCO problems are of great interest to industry as well as government. Manufacturing operations, for example, require covering a set of steps with a number of needed resources. Airline network optimization consists in best allocating airplanes, pilots, flight attendants, and maintenance crew [11]. Military missions success is the result of a large number of resources working together for a common goal. Optimizing these processes will bring great societal benefits.  
MCO describes a problem in which a set of missions are to be performed given constraints on the available resources, where missions are organized efforts to achieve an objective. Examples of mission types include industrial, logistic, and militaristic, where the problem can be anything from transporting packages to destinations to efficiently producing and maintaining equipment devices [8; 12]. The global solutions to such problem are computationally challenging. It is a complex optimization problem [13], often non-convex. Heuristic approaches are used to find feasible solutions, but they depend on domain knowledge and problem decomposition, leading to inaccurate solutions. Therefore, this category of problems is a good candidate for quantum acceleration. In this effort, we will address an abstraction of a real MCO problem.  
We formulate the problem for a Quantum Annealer, specifically the D-Wave quantum computer, as well as investigate the formulation for a gate-based model approach, specifically the IBM quantum computer. By using the results from the Quantum Processing Unit (QPU) and through simulations, we present strengths and weaknesses found with both models, and outline the fundamentals of this new type of optimization problem.