Create a free profile to get unlimited access to exclusive videos, sweepstakes, and more!
Want to visit 2 million stars? There’s a shortcut, but you’ll need a warp drive
It’s towel day. Really. Someone has actually come up with a real hitchhiker’s guide to the galaxy, though there are no directions to the Restaurant at the End of the Universe.
The shortest path to take in order to visit 2 million stars has been found by mathematicians William Cook and Keld Helsgaun. They have finally solved a long-standing mystery. By analyzing data from the Gaia space telescope that included 2,079,471 stars in our galaxy, they mapped the most efficient 3D route to hop over to each of them once, and the margin for error is extremely small. The only problem is that you’d need a warp drive that could travel at the speed of light (at least), and we’re definitely not there yet. That, and you would probably have to be immortal or close to it, as the journey would still take about 100 million years.
Cook and Helsgaun were after the solution to the traveling salesman problem, which asks how you could take the shortest route between multiple destinations with only one stop at each. The journey would eventually bring you back to where you started from, which, in this scenario, is the sun. Helsgaun searched for ways to find better and better tours, while Cook was the one who proved guarantees on how short a tour could possibly be. The tours inform the guarantees while the guarantees help improve the tours. Figuring out how to do this with the stars in our galaxy puts it on the largest scale ever.
“To make the rotating maps of the tours, we used the three.js Javascript 3D library,” Cook told SYFY WIRE. “The 3D positions of the stars were taken from a data set created at the Max Planck Institute for Astronomy. We used somewhere between 100 and 200 CPU years in the computations, running on a network of computers when they were not otherwise occupied.”
The problem took up to 200 years of computing time that was compressed into just two years (it is faster when you don’t have thousands of people trying to log onto the same network). Quantum computers could potentially speed up that process, but Cook has doubts. If someone could come up with technology advanced enough for a huge and extremely strong quantum computer, it could help with finding shorter tours, and quantum computing search could further help in shortening those routes. The problem is that we’re not technologically there yet. The quantum computers that do exist are just unable to support such an extreme dataset, let alone dream up every possible tour at once.
“It is not at all clear that a quantum computer can help in solving large instances of the traveling salesman problem,” Cook said. “In particular, there is no indication that quantum computing can help substantially in finding a guarantee needed to prove a tour is shortest possible.”
Gaia, whose mission is to make the largest and most precise 3D map of the Milky Way, has released data on the locations of 1.33 billion stars, so Cook and Helsgaun are now trying to figure out the shortest route between them. This is a dataset 500 times larger than the last. Their best result yet is over 15 trillion light years. So far, they can only guarantee that it is at most about a factor of 1.0038 longer than the shortest possible tour, which seems like nothing, but is a far greater margin for error than the factor of 0.0000074, which is 700 light years for that particular route. Not bad compared to the nearly hundred thousand the entire trip would take. Even then, Cook still wants to push it further.
“We have found a set of rules (using parallel computing) that we hope will give a strong guarantee, but the huge scale of the problem makes it difficult to find the combination of the rules that we need,” he said. “This combination task is called linear programming — it is the workhorse for the field of mathematical optimization. Our 1.33-billon star project is driving the creation of LP algorithms to handle examples nearly 1,000 times larger than was previously possible.”
By the way, because Cook and Helsgaun believe that the 2 million-star tour could be done in even less time than the guarantee, they are offering a reward* of $50 for each parsec (3.26 light years) that can be saved by rearranging the route to those 2,079,471 stars, up to a $10,000 total. Just saying.
*It's legit. Cook personally asked your friendly neighborhood writer to spread the word about this.
