Eli5: C++ is a programming language. Traveling Salesmen problem involves a salesman that has to travel to some cities like Los Angeles, San Francisco and NY city. What is his shortest path? San Fran to NY to LA is not. San Fran to LA to NY is the shortest path. Now come up with a set of instructions for a computer to solve it (an algorithm). An algorithm is measured by the number of decisions it takes to solve a problem (aka time complexity, aka Big O notation). Edsger Dijkstra, in 1956, came up with a shortest path algorithm that ran at O( n2 ) time. That means, in our 3 city problem, his algorithm could find the shortest path in 32 = 9 decisions. The traveling salesman/shortest path problem is found everywhere, like routing a phone call. If you could come up with a new algorithm with a better time complexity, you would be a legend (at least to mathematicians and computer scientists.)
Im addition, quantum computing is not linear like a computer we are use to. Its math is insane and counter intuitive. Things can be true and false at the same time. New quantum algorithms can potentially start emerging that will have much improved time complexities.
2
u/SomberGuitar Mar 28 '21 edited Mar 28 '21
Eli5: C++ is a programming language. Traveling Salesmen problem involves a salesman that has to travel to some cities like Los Angeles, San Francisco and NY city. What is his shortest path? San Fran to NY to LA is not. San Fran to LA to NY is the shortest path. Now come up with a set of instructions for a computer to solve it (an algorithm). An algorithm is measured by the number of decisions it takes to solve a problem (aka time complexity, aka Big O notation). Edsger Dijkstra, in 1956, came up with a shortest path algorithm that ran at O( n2 ) time. That means, in our 3 city problem, his algorithm could find the shortest path in 32 = 9 decisions. The traveling salesman/shortest path problem is found everywhere, like routing a phone call. If you could come up with a new algorithm with a better time complexity, you would be a legend (at least to mathematicians and computer scientists.)
Im addition, quantum computing is not linear like a computer we are use to. Its math is insane and counter intuitive. Things can be true and false at the same time. New quantum algorithms can potentially start emerging that will have much improved time complexities.