## 6 Results
Evidently, the pheromone exchange policy ICDU, which increased the pheromone value on common links and reduced the pheromone value on uncommon links between two randomly selected colonies, produced better results when the entire tour was optimized without breaking it into sub-graphs. When we used the HPACO algorithm (as described in Section 5), it produced the best results. Note that this algorithm starts out as a parallel ACO on the entire graph, partially op-timizes it, then partitions it into disjoint sub-tours that are individually optimized in parallel, and finally the assembled sub-tours as a whole are optimized using the paral-lel ACO algorithm of Section 4. The optimization of the individual sub-tours can be carried out by a quantum computer implementing the QAOA algorithm. The size of the partitioned sub-tours then depends on the number of qubits \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**TSPLIB Benchmark**} & **Exchange** & \multirow{2}{*}{**Exchange Policy PIR**} & \multicolumn{2}{c}{**Exchange Policy**} & \multirow{2}{*}{**HPACO**} \\  & **Policy APAL** & & & **ICDU** & \\ \hline Eli51 & 429.48 & 428.98 & 428.98 & **428.98 \({}^{*}\)** \\ Berlin52 & 7544.36 & 7544.36 & 7544.36 & **7544.36 \({}^{*}\)** \\ Rd100 & 7918 & 7910.39 & 7910.39 & **7909.10 \({}^{*}\)** \\ Ch130 & 6156.27 & 6144.32 & 6114.02 & **6110.73 \({}^{*}\)** \\ Ch150 & 6576.54 & 6547.32 & 6538.76 & **6530.90 \({}^{*}\)** \\ kroA200 & 29,644.3 & 29,744.5 & 29,492.2 & 29,443 \\ pr439 & 108,537 & 108,425 & 108,208 & 107,744 \\  & & & & (0.5\% of Optimal) \\ d2103 & 81,518 & 81,469 & 81,296 & 81,283 \\  & & & & (1.03\% of Optimal) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of the tour lengths for different variations of the parallel ACO algorithm for TSPLIB benchmarks (* indicates the optimal value). Figure 11: Common paths taken by all ant colonies during the optimization of the kroA200 benchmark—red circles depict examples of the common paths taken by all colonies. available in the quantum computer. The number of nodes that can be currently optimized using a quantum computer is less than 50. Figure 12 shows the results of the modified version of the HPACO algorithm, where after the partitioned sub-tours were optimized, only one iteration of \(k\)-opt (2-opt) was used on the entire graph. After determining a better swap of the nodes, the sub-graphs were generated again and optimized. This process was repeated. This implementation will allow for the most efficient execution time in a quantum environment. As can be seen from the algorithm in Figure 6, the modified HPACO algorithm obtained optimal results for benchmarks with up to 150 nodes, as observed for the HPACO algorithm in Section 5, but its execution was much more efficient, as can be seen from the code in Figure 7. For larger problems, the algorithm allowed achieving a result within 1% of the known optimal result for graphs containing up to a few thousand nodes. Figure 13 shows the effect of the sub-graph size on the tour cost with respect to the known optimal value for the d2103 benchmark with 2103 nodes. As can be seen, and as intuitively expected, as the sub-graph size increased, the tour cost decreased if the sub-graphs were optimal. In Figure 13, each sub-graph was optimized using the HPACO algorithm and executed for 500 iterations. If a quantum computer is available, then sub-graph optimization can be carried out instantaneously. One of the interesting observations is that the difference in the optimization results between a sub-graph with a size of 20 and a sub-graph with a size of 100 was relatively small. This can be attributed to the capability of our parallel ACO algorithm that is able to overcome the less optimal merge of sub-graphs into a better optimization via periodic pheromone exchange between the colonies. Another advantage of our hybrid approach is that it can overcome, to some extent, the noise and decoherence issues occurring when using quantum computers for sub-graph optimization.