# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 1 Introduction
However, upon measurement, a qubit collapses to the state 0 or 1 and behaves as a classical bit. The quantum annealing process in effect guides the qubits from a superposition of states to their collapse into either the 0 or 1 state. In the end, the net effect is that the system is in a classical state, which must encode an (optimal) solution of the problem. The current generation of D-Wave computers employs the Chimera topology. In the Chimera topology, qubits are sets of connected unit cells that are connected to four vertical qubits via couplers [21; 22; 23]. The unit cells are oriented vertically and horizontally with adjacent qubits connected, creating a sparsely connected network. A Chimera graph consists of an \(N\times N\) grid of unit cells. The D-Wave 2000Q QPU has up to 2048 qubits, which are mapped to a C16 Chimera graph, that is they are logically mapped into a 16 \(\times\) 16 matrix of unit cells, each consisting of 8 qubits. In the D-Wave nomenclature the percentage of working qubits and couplers is known as the working graph, which is typically a subgraph of the total number of interconnected qubits that are physically present in the QPU. A major category of optimization problems, particularly amenable to D-Wave's quantum annealing, are those that can be expressed as quadratic unconstrained binary optimization (QUBO) problems. QUBO refers to a pattern matching technique that, among other applications, can be used in machine learning and optimization, and which involves minimizing a quadratic polynomial over binary variables [21; 24; 25; 26; 27; 28; 29; 30]. We emphasize that QUBO is NP-hard [30]. Some of the most famous combinatorial optimization problems that can be solved as QUBO problems are the Maximum Cut, the Graph Coloring and the Partition problem [31]. More details on the QUBO formulation and related results (that are beyond the scope of this paper) can be found in the survey paper of [PERSON] [26]. QUBO is equivalent to the Ising model, a well-known and extensively studied model in physics, that was introduced in the mid-1920s by [PERSON] and [PERSON] in the field of ferromagnetism [32; 33]. The underlying logical architecture of this model is that variables are represented as qubits and interactions among qubits stand for the costs associated with each pair of qubits. In particular, this architecture can be depicted as an undirected graph with qubits as vertices and couplers as edges among them. The open-source software qbsolv that D-Wave introduced in 2017 is aimed at tackling QUBO problems of higher scale than previous attempts, by utilizing a more complex graph structure with higher connectivity among QPUs, by partitioning the input into parts that are then independently solved. This process is repeated using a Tabu-based search until no further improvement is found [20; 34]. The literature contains several works that are dedicated to solving the standard TSP or some related variant in a quantum setting. One of the first attempts was the work by [PERSON] et al. [35]. The authors introduced a different quantum annealing scheme based on path-integral Monte Carlo processes in order to address the symmetric version of the Traveling Salesman Problem (sTSP). In [36; 37], the D-Wave platform was used as a test bed for evaluating and comparing the efficiency of quantum annealing against classical methods in solving the standard TSP. In [38; 39], the well-known variation of the TSP, the (Capacitated) Vehicle Routing Problem is studied using, again, the D-Wave computer. The TSP with Time Windows (TSPTW) is a challenging problem to tackle, as its inherent high complexity presents great solving difficulties. It is an important problem because the additional time constraints enable one to model more realistic situations than the vanilla TSP. In modern metropolitan cities, there are many practical problems that take the form of traversing a network starting and ending from a specific position, the depot.