## 6 Results  
To implement the HPACO with quantum optimization for sub-tours, we used the IBM Qiskit quantum simulator. The current Qiskit simulator is only able to handle a three-node TSP problem. For the optimization of a four-node problem, the simulator takes almost 30 min, and often errors are made. This phenomenon was also reported in [35]. Thus, we first considered a relatively small-size problem, i.e., a 51-node TSP (eil51 from the TSPLib benchmark), and used our HPACO algorithm to optimize it. A tour cost of 426 was obtained (the known optimal cost for this benchmark is 426). In the rest of the experiments, we replaced the QAOA with the parallel ACO algorithm, as detailed in Figure 7, so that we could assess the effectiveness of our hybrid approach, without being limited by the size of the current quantum computers or simulators in the optimization of the sub-graphs. One of the key strengths of our parallel ACO algorithm is the cooperation between different ant colonies. In our experimental setup, the algorithm was implemented using C#. Our computing platform was a 48-core Xeon processor with 128 GB RAM allowing us to run multiple ant colonies. The progress of different ant colonies during the optimization of the Ch150 (150 nodes) benchmark is shown in Figure 8.  
The parallel ACO algorithm periodically used the information on the common paths taken by different colonies to increase the pheromone value on these common paths. Figure 9 shows the common paths taken by the ant colonies during the optimization of the Ch150 benchmark. Our HPACO algorithm, as described in Section 5, obtained optimal results for TSPLIB benchmarks with up to 150 nodes, partitioning sub-graphs of 30-50 nodes. For example, for the 150-node Ch150 benchmark, the optimum value obtained by our HPACO algorithm was 6530.90. The optimal tour is shown in Figure 10.  
Figure 7: Modified HPACO for quantum environments. Figure 8: Progress of different ant colonies during the optimization of the Ch150 benchmark. Figure 9: Common paths taken by the ant colonies during the optimization of the Ch150 benchmark. **Optimal tour (Ch150)**: 1 98 103 82 95 107 5 100 143 97 146 26 75 18 142 85 65 132 137 50 55 58 141 83 56 90 46 92 54 138 134 131 32 23 38 67 43 109 51 20 25 110 81 29 86 135 70 108 102 114 99 19 2 37 6 28 9 42 120 47 139 40 53 118 24 12 116 101 41 57 39 127 69 36 61 11 148 130 17 66 60 140 117 129 27 31 123 74 13 106 91 119 68 128 45 71 44 64 112 136 145 144 147 49 72 80 14 122 77 133 15 78 21 150 115 4 104 22 125 149 62 3 113 10 94 88 121 79 59 16 111 105 33 126 52 93 124 35 96 89 8 7 84 30 63 48 73 76 34 87 1. As can be seen from the progress of optimization in Figure 8, there are many Hamiltonian cycles possible that are near optimal (without intersecting edges). Without our parallel ACO algorithm which uses periodic cooperation between ant colonies, the optimization can easily get trapped in a local minimum. The six ant colonies depicted in Figure 8 used a slightly different evolutionary strategy (ACS or Max-Min) with different optimization parameters, which further aided the optimization as the algorithm progressed. Regarding the cooperation between ant colonies, we focused on the common paths taken by all colonies and, especially, on those path choices for which there was a disagreement between the colonies. The paths highlighted in Figure 9 were determined to be the common paths for the optimization of the Ch150 benchmark, with about 2000 iterations of the optimization process. Figure 11 shows the progress of the different ant colonies during the optimization of the kroA200 benchmark as well as the common paths taken by the ant colonies during the optimization of kroA200 benchmark. Table 1 shows the optimization results for the different pheromone exchange policies and the HPACO. Figure 10: Best tour with a cost of 6530.90 for the Ch150 benchmark (the prior known optimal cost was 6532.28).