What about quantum computers?

The advent of quantum computers has some believing that all optimization problems will be able to be optimally solved by quantum computers. Time magazine had a cover calling it "The Infinity Computer". Such power would of course render the library useless. An investigation was in order.

For this, we created a simulated, really really fast quantum computer.

The table below shows time to solve the Traveling Salesman Problem for an increasing number of cities for three different computers.

1. An Intel T7400 processor. Times are actual up to 16 cities, then extrapolated.

2. The Cray Titan at Oak Ridge is the second fastest computer in the world (China's Tianhe-2 is about 50% faster). It has a speed of 20 petaflops – about one million times faster that the Intel T7400 processor. The estimated times for the Titan are based on that.

3. A simulated quantum computer. It is assumed to have the 2512 qubits with full quantum effects. In addition, we have given it the speed of the Cray Titan. If we assume quantum computers will work, there still will not be anything this fast for some time.

The results show how blazingly fast such a quantum computer would be. For the 36 city problem, the Cray Titan would take over 8,000,000,000 trillion years. The quantum computer would solve the problem almost instantaneously.

But starting with the 263 city problem, the quantum computer falls prey to combinatorial explosion of the search space. At 268 cities, the quantum computer takes over 5,000,000 trillion years. Don't wait up. The search space for that problem is 10535. For comparison, the search space for a complex job shop is estimated to be between 10800 and 10900. The largest problem posed in the Reconnaissance Aircraft Scheduler is estimated to have a search space of over 1027,000.

This might be a good time to point out that using the Optimization Library, the Intel T7400 solved the 666 city problem to 0.68% of optimal in 9 hours. The 666 city problem has a search space of 101593.

CitiesSearch SpaceIntel T7400 TitanQuantum
161013 4.01 hours 0.014 seconds 0.00 milliseconds
1710142.84 days 0.246 seconds0.00 milliseconds
18101551.17 days 4.421 seconds0.00 milliseconds
1910172.66 years 1.40 minutes0.00 milliseconds
20101853 years 28.00 minutes0.00 milliseconds
2110191,118 years 9.80 hours0.00 milliseconds
22102124,595 years 8.98 days0.00 milliseconds
231022565,690 years 206.62 days0.00 milliseconds
24102314 million years 13.58 years0.00 milliseconds
251025339 million years 339 years0.00 milliseconds
2610269 billion years 8,825 years0.00 milliseconds
271028238 billion years 238,269 years0.00 milliseconds
2810296,672 trillion years 7 million years0.00 milliseconds
291030193,474 trillion years 193 million years0.00 milliseconds
3010325,804,225 trillion years 6 billion years0.00 milliseconds
311033179,930,978 trillion years 180 billion years0.00 milliseconds
3210355,757,791,300 trillion years 5,758 trillion years0.00 milliseconds
331036190,007,112,913 trillion years 190,007 trillion years0.00 milliseconds
3410381021 trillion years 6,460,242 trillion years0.00 milliseconds
3510401023 trillion years 226,108,464 trillion years0.00 milliseconds
3610411024 trillion years 8,139,904,717 trillion years0.00 milliseconds
3710431026 trillion years 301,176,474,535 trillion years0.00 milliseconds
3810441028 trillion years 1022 trillion years0.00 milliseconds
3910461029 trillion years 1023 trillion years0.00 milliseconds
4010471031 trillion years 1025 trillion years0.00 milliseconds
4110491032 trillion years 1026 trillion years0.00 milliseconds
4210511034 trillion years 1028 trillion years0.00 milliseconds
4310521036 trillion years 1030 trillion years0.00 milliseconds
4410541037 trillion years 1031 trillion years0.00 milliseconds
4510561039 trillion years 1033 trillion years0.00 milliseconds
4610571041 trillion years 1035 trillion years0.00 milliseconds
4710591042 trillion years 1036 trillion years0.00 milliseconds
4810611044 trillion years 1038 trillion years0.00 milliseconds
4910621046 trillion years 1040 trillion years0.00 milliseconds
5010641047 trillion years 1041 trillion years0.00 milliseconds
5110661049 trillion years 1043 trillion years0.00 milliseconds
5210671051 trillion years 1045 trillion years0.00 milliseconds
5310691052 trillion years 1046 trillion years0.00 milliseconds
5410711054 trillion years 1048 trillion years0.00 milliseconds
5510731056 trillion years 1050 trillion years0.00 milliseconds
5610741058 trillion years 1052 trillion years0.00 milliseconds
5710761059 trillion years 1053 trillion years0.00 milliseconds
5810781061 trillion years 1055 trillion years0.00 milliseconds
5910801063 trillion years 1057 trillion years0.00 milliseconds
6010811065 trillion years 1059 trillion years0.00 milliseconds
6110831067 trillion years 1061 trillion years0.00 milliseconds
6210851068 trillion years 1062 trillion years0.00 milliseconds
6310871070 trillion years 1064 trillion years0.00 milliseconds
6410891072 trillion years 1066 trillion years0.00 milliseconds
6510901074 trillion years 1068 trillion years0.00 milliseconds
6610921076 trillion years 1070 trillion years0.00 milliseconds
6710941077 trillion years 1071 trillion years0.00 milliseconds
6810961079 trillion years 1073 trillion years0.00 milliseconds
6910981081 trillion years 1075 trillion years0.00 milliseconds
70101001083 trillion years 1077 trillion years0.00 milliseconds
71101011085 trillion years 1079 trillion years0.00 milliseconds
72101031087 trillion years 1081 trillion years0.00 milliseconds
73101051088 trillion years 1082 trillion years0.00 milliseconds
74101071090 trillion years 1084 trillion years0.00 milliseconds
75101091092 trillion years 1086 trillion years0.00 milliseconds
76101111094 trillion years 1088 trillion years0.00 milliseconds
77101131096 trillion years 1090 trillion years0.00 milliseconds
78101151098 trillion years 1092 trillion years0.00 milliseconds
791011610100 trillion years 1094 trillion years0.00 milliseconds
801011810102 trillion years 1096 trillion years0.00 milliseconds
811012010104 trillion years 1098 trillion years0.00 milliseconds
821012210106 trillion years 10100 trillion years0.00 milliseconds
831012410107 trillion years 10101 trillion years0.00 milliseconds
841012610109 trillion years 10103 trillion years0.00 milliseconds
851012810111 trillion years 10105 trillion years0.00 milliseconds
861013010113 trillion years 10107 trillion years0.00 milliseconds
871013210115 trillion years 10109 trillion years0.00 milliseconds
881013410117 trillion years 10111 trillion years0.00 milliseconds
891013610119 trillion years 10113 trillion years0.00 milliseconds
901013810121 trillion years 10115 trillion years0.00 milliseconds
911014010123 trillion years 10117 trillion years0.00 milliseconds
921014210125 trillion years 10119 trillion years0.00 milliseconds
931014410127 trillion years 10121 trillion years0.00 milliseconds
941014610129 trillion years 10123 trillion years0.00 milliseconds
951014810131 trillion years 10125 trillion years0.00 milliseconds
961014910133 trillion years 10127 trillion years0.00 milliseconds
971015110135 trillion years 10129 trillion years0.00 milliseconds
981015310137 trillion years 10131 trillion years0.00 milliseconds
991015510139 trillion years 10133 trillion years0.00 milliseconds
1001015710141 trillion years 10135 trillion years0.00 milliseconds
1011015910143 trillion years 10137 trillion years0.00 milliseconds
1021016110145 trillion years 10139 trillion years0.00 milliseconds
1031016310147 trillion years 10141 trillion years0.00 milliseconds
1041016610149 trillion years 10143 trillion years0.00 milliseconds
1051016810151 trillion years 10145 trillion years0.00 milliseconds
1061017010153 trillion years 10147 trillion years0.00 milliseconds
1071017210155 trillion years 10149 trillion years0.00 milliseconds
1081017410157 trillion years 10151 trillion years0.00 milliseconds
1091017610159 trillion years 10153 trillion years0.00 milliseconds
1101017810161 trillion years 10155 trillion years0.00 milliseconds
1111018010163 trillion years 10157 trillion years0.00 milliseconds
1121018210165 trillion years 10159 trillion years0.00 milliseconds
1131018410167 trillion years 10161 trillion years0.00 milliseconds
1141018610169 trillion years 10163 trillion years0.00 milliseconds
1151018810171 trillion years 10165 trillion years0.00 milliseconds
1161019010173 trillion years 10167 trillion years0.00 milliseconds
1171019210175 trillion years 10169 trillion years0.00 milliseconds
1181019410178 trillion years 10172 trillion years0.00 milliseconds
1191019610180 trillion years 10174 trillion years0.00 milliseconds
1201019810182 trillion years 10176 trillion years0.00 milliseconds
1211020010184 trillion years 10178 trillion years0.00 milliseconds
1221020210186 trillion years 10180 trillion years0.00 milliseconds
1231020510188 trillion years 10182 trillion years0.00 milliseconds
1241020710190 trillion years 10184 trillion years0.00 milliseconds
1251020910192 trillion years 10186 trillion years0.00 milliseconds
1261021110194 trillion years 10188 trillion years0.00 milliseconds
1271021310196 trillion years 10190 trillion years0.00 milliseconds
1281021510198 trillion years 10192 trillion years0.00 milliseconds
1291021710201 trillion years 10195 trillion years0.00 milliseconds
1301021910203 trillion years 10197 trillion years0.00 milliseconds
1311022110205 trillion years 10199 trillion years0.00 milliseconds
1321022410207 trillion years 10201 trillion years0.00 milliseconds
1331022610209 trillion years 10203 trillion years0.00 milliseconds
1341022810211 trillion years 10205 trillion years0.00 milliseconds
1351023010213 trillion years 10207 trillion years0.00 milliseconds
1361023210215 trillion years 10209 trillion years0.00 milliseconds
1371023410218 trillion years 10212 trillion years0.00 milliseconds
1381023610220 trillion years 10214 trillion years0.00 milliseconds
1391023810222 trillion years 10216 trillion years0.00 milliseconds
1401024110224 trillion years 10218 trillion years0.00 milliseconds
1411024310226 trillion years 10220 trillion years0.00 milliseconds
1421024510228 trillion years 10222 trillion years0.00 milliseconds
1431024710230 trillion years 10224 trillion years0.00 milliseconds
1441024910233 trillion years 10227 trillion years0.00 milliseconds
1451025110235 trillion years 10229 trillion years0.00 milliseconds
1461025410237 trillion years 10231 trillion years0.00 milliseconds
1471025610239 trillion years 10233 trillion years0.00 milliseconds
1481025810241 trillion years 10235 trillion years0.00 milliseconds
1491026010243 trillion years 10237 trillion years0.00 milliseconds
1501026210246 trillion years 10240 trillion years0.00 milliseconds
1511026410248 trillion years 10242 trillion years0.00 milliseconds
1521026710250 trillion years 10244 trillion years0.00 milliseconds
1531026910252 trillion years 10246 trillion years0.00 milliseconds
1541027110254 trillion years 10248 trillion years0.00 milliseconds
1551027310257 trillion years 10251 trillion years0.00 milliseconds
1561027510259 trillion years 10253 trillion years0.00 milliseconds
1571027810261 trillion years 10255 trillion years0.00 milliseconds
1581028010263 trillion years 10257 trillion years0.00 milliseconds
1591028210265 trillion years 10259 trillion years0.00 milliseconds
1601028410268 trillion years 10262 trillion years0.00 milliseconds
1611028610270 trillion years 10264 trillion years0.00 milliseconds
1621028910272 trillion years 10266 trillion years0.00 milliseconds
1631029110274 trillion years 10268 trillion years0.00 milliseconds
1641029310276 trillion years 10270 trillion years0.00 milliseconds
1651029510279 trillion years 10273 trillion years0.00 milliseconds
1661029710281 trillion years 10275 trillion years0.00 milliseconds
1671030010283 trillion years 10277 trillion years0.00 milliseconds
1681030210285 trillion years 10279 trillion years0.00 milliseconds
1691030410287 trillion years 10281 trillion years0.00 milliseconds
1701030610290 trillion years 10284 trillion years0.00 milliseconds
1711030910292 trillion years 10286 trillion years0.00 milliseconds
1721031110294 trillion years 10288 trillion years0.00 milliseconds
1731031310296 trillion years 10290 trillion years0.00 milliseconds
1741031510299 trillion years 10293 trillion years0.00 milliseconds
1751031810301 trillion years 10295 trillion years0.00 milliseconds
1761032010303 trillion years 10297 trillion years0.00 milliseconds
1771032210305 trillion years 10299 trillion years0.00 milliseconds
1781032410308 trillion years 10302 trillion years0.00 milliseconds
1791032710310 trillion years 10304 trillion years0.00 milliseconds
1801032910312 trillion years 10306 trillion years0.00 milliseconds
1811033110314 trillion years 10308 trillion years0.00 milliseconds
1821033310317 trillion years 10311 trillion years0.00 milliseconds
1831033610319 trillion years 10313 trillion years0.00 milliseconds
1841033810321 trillion years 10315 trillion years0.00 milliseconds
1851034010323 trillion years 10317 trillion years0.00 milliseconds
1861034210326 trillion years 10320 trillion years0.00 milliseconds
1871034510328 trillion years 10322 trillion years0.00 milliseconds
1881034710330 trillion years 10324 trillion years0.00 milliseconds
1891034910333 trillion years 10327 trillion years0.00 milliseconds
1901035110335 trillion years 10329 trillion years0.00 milliseconds
1911035410337 trillion years 10331 trillion years0.00 milliseconds
1921035610339 trillion years 10333 trillion years0.00 milliseconds
1931035810342 trillion years 10336 trillion years0.00 milliseconds
1941036110344 trillion years 10338 trillion years0.00 milliseconds
1951036310346 trillion years 10340 trillion years0.00 milliseconds
1961036510349 trillion years 10343 trillion years0.00 milliseconds
1971036810351 trillion years 10345 trillion years0.00 milliseconds
1981037010353 trillion years 10347 trillion years0.00 milliseconds
1991037210355 trillion years 10349 trillion years0.00 milliseconds
2001037410358 trillion years 10352 trillion years0.00 milliseconds
2011037710360 trillion years 10354 trillion years0.00 milliseconds
2021037910362 trillion years 10356 trillion years0.00 milliseconds
2031038110365 trillion years 10359 trillion years0.00 milliseconds
2041038410367 trillion years 10361 trillion years0.00 milliseconds
2051038610369 trillion years 10363 trillion years0.00 milliseconds
2061038810372 trillion years 10366 trillion years0.00 milliseconds
2071039110374 trillion years 10368 trillion years0.00 milliseconds
2081039310376 trillion years 10370 trillion years0.00 milliseconds
2091039510379 trillion years 10373 trillion years0.00 milliseconds
2101039810381 trillion years 10375 trillion years0.00 milliseconds
2111040010383 trillion years 10377 trillion years0.00 milliseconds
2121040210386 trillion years 10380 trillion years0.00 milliseconds
2131040510388 trillion years 10382 trillion years0.00 milliseconds
2141040710390 trillion years 10384 trillion years0.00 milliseconds
2151040910393 trillion years 10387 trillion years0.00 milliseconds
2161041210395 trillion years 10389 trillion years0.00 milliseconds
2171041410397 trillion years 10391 trillion years0.00 milliseconds
2181041610400 trillion years 10394 trillion years0.00 milliseconds
2191041910402 trillion years 10396 trillion years0.00 milliseconds
2201042110404 trillion years 10398 trillion years0.00 milliseconds
2211042310407 trillion years 10401 trillion years0.00 milliseconds
2221042610409 trillion years 10403 trillion years0.00 milliseconds
2231042810411 trillion years 10405 trillion years0.00 milliseconds
2241043010414 trillion years 10408 trillion years0.00 milliseconds
2251043310416 trillion years 10410 trillion years0.00 milliseconds
2261043510418 trillion years 10412 trillion years0.00 milliseconds
2271043710421 trillion years 10415 trillion years0.00 milliseconds
2281044010423 trillion years 10417 trillion years0.00 milliseconds
2291044210425 trillion years 10419 trillion years0.00 milliseconds
2301044410428 trillion years 10422 trillion years0.00 milliseconds
2311044710430 trillion years 10424 trillion years0.00 milliseconds
2321044910432 trillion years 10426 trillion years0.00 milliseconds
2331045110435 trillion years 10429 trillion years0.00 milliseconds
2341045410437 trillion years 10431 trillion years0.00 milliseconds
2351045610440 trillion years 10434 trillion years0.00 milliseconds
2361045910442 trillion years 10436 trillion years0.00 milliseconds
2371046110444 trillion years 10438 trillion years0.00 milliseconds
2381046310447 trillion years 10441 trillion years0.00 milliseconds
2391046610449 trillion years 10443 trillion years0.00 milliseconds
2401046810451 trillion years 10445 trillion years0.00 milliseconds
2411047010454 trillion years 10448 trillion years0.00 milliseconds
2421047310456 trillion years 10450 trillion years0.00 milliseconds
2431047510459 trillion years 10453 trillion years0.00 milliseconds
2441047810461 trillion years 10455 trillion years0.00 milliseconds
2451048010463 trillion years 10457 trillion years0.00 milliseconds
2461048210466 trillion years 10460 trillion years0.00 milliseconds
2471048510468 trillion years 10462 trillion years0.00 milliseconds
2481048710471 trillion years 10465 trillion years0.00 milliseconds
2491049010473 trillion years 10467 trillion years0.00 milliseconds
2501049210475 trillion years 10469 trillion years0.00 milliseconds
2511049410478 trillion years 10472 trillion years0.00 milliseconds
2521049710480 trillion years 10474 trillion years0.00 milliseconds
2531049910483 trillion years 10477 trillion years0.00 milliseconds
2541050210485 trillion years 10479 trillion years0.00 milliseconds
2551050410487 trillion years 10481 trillion years0.00 milliseconds
2561050610490 trillion years 10484 trillion years0.00 milliseconds
2571050910492 trillion years 10486 trillion years0.00 milliseconds
2581051110495 trillion years 10489 trillion years0.00 milliseconds
2591051410497 trillion years 10491 trillion years0.102 seconds
2601051610499 trillion years 10493 trillion years26.449 seconds
2611051810502 trillion years 10496 trillion years1.92 hours
2621052110504 trillion years 10498 trillion years20.93 days
2631052310507 trillion years 10501 trillion years15.07 years
2641052610509 trillion years 10503 trillion years3,979 years
2651052810512 trillion years 10506 trillion years1 million years
2661053110514 trillion years 10508 trillion years281 million years
2671053310516 trillion years 10510 trillion years75 billion years
2681053510519 trillion years 10513 trillion years20,072 trillion years
2691053810521 trillion years 10515 trillion years5,399,238 trillion years
2701054010524 trillion years 10518 trillion years1,457,794,270 trillion years
2711054310526 trillion years 10520 trillion years395,062,247,168 trillion years
2721054510529 trillion years 10523 trillion years1023 trillion years
2731054810531 trillion years 10525 trillion years1025 trillion years
2741055010533 trillion years 10527 trillion years1027 trillion years
2751055310536 trillion years 10530 trillion years1030 trillion years
2761055510538 trillion years 10532 trillion years1032 trillion years
2771055710541 trillion years 10535 trillion years1035 trillion years
2781056010543 trillion years 10537 trillion years1037 trillion years
2791056210546 trillion years 10540 trillion years1040 trillion years
2801056510548 trillion years 10542 trillion years1042 trillion years
2811056710551 trillion years 10545 trillion years1045 trillion years
2821057010553 trillion years 10547 trillion years1047 trillion years
2831057210555 trillion years 10549 trillion years1049 trillion years
2841057510558 trillion years 10552 trillion years1052 trillion years
2851057710560 trillion years 10554 trillion years1054 trillion years
2861057910563 trillion years 10557 trillion years1057 trillion years
2871058210565 trillion years 10559 trillion years1059 trillion years
2881058410568 trillion years 10562 trillion years1062 trillion years
2891058710570 trillion years 10564 trillion years1064 trillion years
2901058910573 trillion years 10567 trillion years1067 trillion years
2911059210575 trillion years 10569 trillion years1069 trillion years
2921059410578 trillion years 10572 trillion years1072 trillion years
2931059710580 trillion years 10574 trillion years1074 trillion years
2941059910582 trillion years 10576 trillion years1076 trillion years
2951060210585 trillion years 10579 trillion years1079 trillion years
2961060410587 trillion years 10581 trillion years1081 trillion years
2971060710590 trillion years 10584 trillion years1084 trillion years
2981060910592 trillion years 10586 trillion years1086 trillion years
2991061210595 trillion years 10589 trillion years1089 trillion years