Travelling Sales Person Problem how Quantum computer does it better

D-wave system

I checked out a recent article in BBC on Nasa/Google inducting a new Quantum computer – D-wave Two , what impressed me more was it’s benchmark results based on Travelling Salesman Problem(TSP). It’s been long, I did a math post so thought why not do small, simple demo on TSP for you and explain how Quantum computer like D-wave excels at it.

 

This demo is for people for whom combinatorial optimisation is new or those who want to check out implementation of TSP on Wolfram alpha. This post is not Computation/Mathematics experts as I won’t be covering any algorithms or optimisation approach, this post is just aimed at giving basic understanding of TSP.

 

Travelling Sales Person problem, how Quantum computing solves it faster

The Objective of the Travelling Sales Person problem is cover a set of cities such as to take route with least distance to cover all cities and reach the starting point. I have given a wolfram alpha widget below to explain the concept with actual Indian cities – Chennai, Mumbai, Bangalore, Kochi.

Usage :

1. Click “Check it out “

2. Click “Show Shortest path”

Solution :

Here the optimal solution i.e least distance for tour is Mumbai->Chennai->Bangalore->Kochi->Mumbai .

Computation :

The TSP problem is NP-Hard problem which cannot be solved in polynomial time, in simple terms a very hard problem. Since the computation is linear, i.e  the distance between all cities have to be calculated to know the least distance. The problem gets complicated when number of cities increases, infact the computation is in  O(n!). For 50 Cities, it becomes 10^64  (Thats 10 followed by 64 zeros ! ) . Even powerful computers struggle for Hard TSP problems. Variety of approaches like Dynamic Programming, Exact algorithms, Heuristic and approximation algorithms are used to solve TSP problems.

Video demo :

Quantum Computing :

“The laws of quantum physics, which govern the microscopic world, allow bits of matter to be in two states simultaneously”, says D-wave Systems. D-wave 2 a 15 million $ quantum computer has two unique processors which use a concept called “Quantum Tunneling”.

DWave 2 processors makes use of Quantum Tunnelling.

D-Wave 2 processors makes use of Quantum Tunnelling

The benchmarks of D-wave 2 accessed by Nasa/Google shows that the TSP problem which took 30 minutes to solve on a traditional computer software like the one I used in my demo above, was solved less than fraction of a second on a D-wave 2 quantum computer. D-wave is able to produce such impressive results using it’s “quantum annealing” feature that can extract optimal mathematical solution from all possibilities.

In the case of  TSP, The D-Wave Two chip can compare all the possible distances at once, rather than having to work through each in turn. That saves lot computational time and thus explains better results. This is made possible because using Quantum annealing, Dwave can save information to both 0 and 1 states simultaneously.

Conclusion :

What D-wave 2 has done here is very impressive, that explains Nasa and Google beating to try it out. Taking different approach to quantum computing seems to have done wonders to Dwave. Hope Quantum computing becomes main stream computing and soon find it’s way to personal computing space , don’t ask – Our requirements are limit less !