How mechanics found in nature could make quantum computing a reality
The travelling salesperson problem does not sound like a major quandary. The task? Compute the shortest possible route between a list of destinations and return to base. Unfortunately, although it’s conceptually simple to work it out, no one has come up with an algorithm that is efficient enough to run at speed for tasks with more than a short list of destinations. The naive approach of adding up the total distances for all possible routes results in a combinatorial explosion of calculations. Computer scientists have tried all manner of tricks to bring it down from the order of n-factorial needed for the naive approach. But you still wind up with a running time on the order of two to the power of the number of destinations. If you aren’t scheduling an entire lifetime of sales visits, that…