Revisiting The Traveling Salesman Problem as a Reason to Need Quantum Computers
In the online media and literature, we don’t see the traveling salesman problem discussed too often. If you are unfamiliar with the problem, recommend taking the time to read this Forbes article from the source. Because Quantum is Coming. Qubit
This 90 Year Old Math Problem Shows Why We Need Quantum Computers
+ It’s time to run your errands, and you’ve got multiple stops to make. From your house, you have to hit the supermarket, the gas station, and the hardware store, all before returning home. Assuming you know that you begin and end at your home, there are six possible routes you can take…
Even if no such solution exists, and it might not with a classical computer, the world of quantum computers offers unparalleled hope. A quantum computer can solve classes of problems that no classical computer can efficiently solve, and perhaps that will someday include the traveling salesman problem. When your brute force options are too expensive and an efficient algorithm eludes you, don’t give up on ever solving the problem altogether. The quantum computing revolution might yet make it possible.
+ Finding the most efficient route between a large number of nodes — the essence of the traveling salesman problem — has a myriad of practical applications. It shows up in DNA sequencing. It appears in the planning and manufacture of microchips. It rears its head in planning observing runs of many objects in astronomy. And it’s essential in optimizing delivery routes and supply-chain logistics. But for all its importance and relevance in human society, we do not yet know how to solve the problem efficiently: in what computer scientists call polynomial time.
Content may have been edited for style and clarity. The “+” to the left of paragraphs or other statements indicates quoted material from “Source:” document. Boldface title is original title from “Source:” Italicized statements are directly quoted from “Source:” document. Image sources are indicated as applicable.