# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 2 Related Work
The Chimera graph is the underlying annealing architecture of the current generation of the D-Wave platform. Due to physical limitations and noise levels, some qubits and couplers cannot be exploited, and are thus disabled. Therefore, the underlying graph is marginally incomplete [22; 23]. D-Wave's next generation architecture graph, named Pegasus, will supposedly offer more flexibility and expressiveness over previous topologies, such as more efficient embedding of cliques, penalties, improved run times, boosted energy scales, better handling of errors, etc. [21]. Similarly, [PERSON] and [PERSON] discussed some differences between the two latest D-Wave quantum annealing architectures, namely the Chimera and Pegasus graphs [23]. The D-Wave Two, 2X, and 2000Q all used the Chimera graph (see Table 1), which consisted of a processing unit of \(K_{4,4}\) subgraphs. Each generation of this graph has evolved by exploiting more and more qubits (or vertices). On the other hand, Pegasus totally changed the setting by adding more complex connectivity (each qubit or vertex is coupled with 15 other ones) [22]. This enhanced connectivity allows for better utilization of the existing qubits, thus fewer vertices are capable of broader calculations. [PERSON] demonstrated the graph partitioning mechanism of the D-Wave computers using the quantum annealing tools on the D-Wave 2X [31]. Another iterative version of the quantum annealing heuristic for QUBO problems based on tabu search was presented by [PERSON] et al. [67]. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **D-Wave One** & **D-Wave Two** & **D-Wave 2X** & **D-Wave 2000Q** \\ \hline
**Size** & \(4\times 4\) & \(8\times 8\) & \(12\times 12\) & \(16\times 16\) \\
**Qubits** & 128 & 512 & 1152 & 2048 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Quantitative characteristics (qubits and connectivity) of the Chimera topology of previous D-Wave generations (from [22]). [PERSON] [33] discussed Ising formulations for a variety of NP-complete and NP-hard optimization problems (including the TSP problem), with emphasis on using as few as possible qubits. [PERSON] et al. [35] introduced a different quantum annealing scheme based on path-integral Monte Carlo processes to address the symmetric version of the Traveling Salesman Problem (sTSP). Their approach is built upon a rather constrained Ising-like representation and is compared against the standard simulated annealing heuristic on various benchmark tests, demonstrating its superiority. Such works point out the fact that quantum techniques have already been proven to be useful when it comes to particular TSP variants, which motivated the endeavour of this work. Another work on quantum annealing and TSP was presented by [PERSON] [37]. [PERSON] studied small-scale instances of traveling salesman problems, showcasing how a D-Wave machine using quantum annealing would operate to solve these instance. The motivation for this work was to offer a tutorial-like approach, since the limitations on the number of TSP nodes are quite restrictive for real-world applications.