that traveling salesman is NP-hard

Flipping through this month's issue of Technology Review, I came across an interesting article on a company I hadn't heard much from in some time. British Columbia-based D-Wave Systems, the "Quantum Computing Company," has been claiming to have developed the first (ultimately) commercially viable quantum computer for a little over a year now, with little evidence to support their claim.

Though they're efforts thus far have only yielded an inefficient (and quite pricey) prototype with a mere 28 quantum bits (or qubits), the thought of an applicable quantum computer is pretty astounding. While that size isn't anything to write home about, the direction they're taking (and the amount of sophisticated VC dollars pumped into the venture) looks to lead down an interesting road.

For those unfamiliar with the concept of quantum computing, my excitement stems from the possibilities that could be if we were able to utilize quantum parallelism in computation. While classical computers process information broken down to a bit level yielding two possibilities, True or False, Yes or No (or as they are symbolically represented, 0 and 1), quantum computers can, theoretically, register or explore 0 and 1 simultaneously (known as superposition). What this allows for is the ability to explore exponentially possible candidates for an answer in parallel, creating processing speeds many many times faster than exist today. And so the Traveling Salesman Problem (TSP). While the problem requires a search for a solution among exponentially many possibilities, a quantum computer could (eventually) test all of those possibilities simultaneously, and signal with complete certainty when it found a successful solution.

The applications are endless: What is the meaning of Life? How many licks does it take to get to the center of a Toostie-Roll Pop? Longoria or Mendes? Endless...