## 4 Our Hybrid Quantum-Classical Optimization Algorithm
### Pheromone Update  
Since the pheromone values are set to \(\tau_{max}\) in the beginning, evaporation on all links is first carried out according to the following equation:  
\[\tau_{i,j}^{(t+1)}=\tau_{i,j}^{(t)}(1-\rho) \tag{17}\]  
The pheromone values on the links of the best iteration tour or the best global tour are updated as:  
\[\tau_{i,j}^{(t+1)}=\tau_{i,j}^{(t)}(1-\rho)+1/costOfIterationOrGlobalBestTour \tag{18}\]  
Since the ACS and the Max-Min algorithms offer different exploration characteristics (e.g., the Max-Min algorithm favors an early exploration), we combined both of these algorithms in a parallel multi-colony system. To further improve the learning of the optimal paths, we implemented a periodic pheromone exchange between the different colonies that resulted in a more collaborative and efficient exploration of the search space.  
Note that the graph partitioning approach to solving the TSP was proposed in many different papers [30; 31; 32; 33]. The approach in [30] used the K-means-based partitioning of the global graph into sub-graphs and optimized the overall solution by using the Lin-Kernighan algorithm. In [31], a heuristic based on cutting the TSP cycle in time proportionally to the number of edges in the graph was used to partition the graph. The partitions were assembled and optimized further. While the partitioning approach does reduce the time complexity of the entire optimization, it often results in sub-optimal performance as compared to the approach optimizing the entire tour as a whole. The main reason is that a node s\({}_{i}\) in a sub-tour is not swapped with a node in a different sub-tour, s\({}_{j}\), during the optimization of the individual sub-tours. Further, the initial breakdown of the sub-tours can have a major impact on the overall tour optimization if the sub-tours are not properly chosen. We addressed the initial partitioning and the combined optimization of the optimized sub-tours through a significantly improved and novel parallel ACO algorithm. We will first describe the details of our novel parallel ACO algorithm and then present a hybrid parallel ACO sub-graph-partitioning version of it for use in a quantum environment.  
The parallel multi-colony ACO algorithm developed in this work is multithreaded, and each thread runs either the ACS or the Max-Min algorithm. Generally, better results are obtained when half the colonies execute the ACS algorithm, and the other half the Max-Min algorithm. The different threads are periodically synchronized via barrier synchronization and perform pheromone exchange between colonies according to a selected pheromone exchange policy. The general architecture of our parallel implementation is shown in Figure 4.  
After a specified number of iterations of the individual ACO algorithm running in each thread, the threads were synchronized and performed a pheromone exchange. The reason for doing this was to learn which paths were most commonly used, so that more weight could be attributed to those commonly used sub-paths during the exploration of an optimal path. In fact, \"the best route between two given cities\" will most likely involve the major highways connecting them, while the roads that connect to these major highways may offer alternative routes. We implemented the following different pheromone exchange policies after a fixed number \(k\) of iterations.