# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 2 Related Work  
Quantum annealing [5; 12] has demonstrated its ability to solve a broad range of combinatorial optimization problems, not only in computer science [6; 17; 27; 31; 40; 41; 42; 43; 44], but also in other fields, such as quantum chemistry [45], bioinformatics [15; 46], and vehicle routing [34; 39; 47; 48], to name just a few. All these problems aim at minimizing a cost function, which can be \"physically\" interpreted as finding the ground state of a typical Ising Hamiltonian [33]. Nevertheless, it is a laborious task to compute a global minimum in problems where multiple local minima exist [49; 50; 51], a fact that shares a lot of similarities to classical spin glasses [49; 50]. The possible superiority of quantum computation could be translated into either providing a better solution (i.e., closer to the optimal one) or arriving at a solution faster or producing a diverse set of solutions (for the multiobjective case). Some known cases where such methods work well are spin glasses [52], graph coloring [53], job-shop scheduling [54], machine learning [17; 55], graph partitioning [31], 3-SAT [56], vehicle routing and scheduling [34; 39; 47; 48], neural networks [57], and image processing [42], where the problem parameters can be expressed as boolean variables. Adiabatic quantum annealing techniques are also used to address multiobjective optimization problems [58]. [PERSON] et al. showed that quantum annealing techniques could outperform their classical counterparts on a known NP-complete problem, the 3-SAT, under special circumstances [56]. In terms of classical approach, [PERSON] et al. presented a set of local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO) problems, providing indicative simulation results on various benchmark tests [30]. The reduction of the large matrix size in QUBO was the main topic in [25] by [PERSON] and [PERSON]. [PERSON] et al. showed in a step by step procedure how one can translate a problem with particular characteristics into a QUBO instance [29]. A hybrid genetic algorithm for finding guaranteed and reliable solutions of global optimization problems using the branch-and-bound technique was proposed by [PERSON] et al. [59]. A branch-and-bound approach was also used in the work of [PERSON] et al. [60], where dynamic preprocessing techniques and heuristics are used to calculate good initial configurations. Quantum Approximate Optimization Algorithms (QAOA), based on adiabatic quantum computation principles [61], are a family of algorithms that can be used in order to solve QUBO problems (such as the one discussed here). [PERSON] [7] showed that QUBO problems can be solved using an adiabatic quantum computer that employs an Ising spin-1/2 Hamiltonian. This was achieved by the reduction, through minor-embedding, of the underlying graph to the quantum hardware graph. [PERSON] et al. built a mechanism that implements a shallow-depth QAOA by estimating the ground state energy of the Ising model using an analog quantum simulator [62], whereas [PERSON] and [PERSON] tried to show the advantages of QAOAs compared to classical approaches [63]. Constrained polynomial optimization problems using adiabatic quantum computation methods were recently discussed by [PERSON] [19]. A similar approach to the one analyzed in this paper was taken by [PERSON] and [PERSON] [64] on how to apply constraints in QUBO schemes. In particular, to avoid the use of large coefficients (hence, more qubits) that result from the use of quadratic penalties, they proposed a novel combinatorial design that involved solving mixed-integer linear programming problems to accommodate the application of the desired constraints. [PERSON] et al. [65] reviewed and solved the Hamiltonian cycle problem in computational frameworks such as quantum circuits, quantum walks and adiabatic quantum computation. They proposed a QUBO formulation, which is suitable for a D-Wave architecture execution. For an in-depth insight on quantum genetic algorithms, the reader is referred to the work of [PERSON] [66].