Re:Review of Vivek Wadhwa’s Washington Post Column on Quantu...
by MrMoenty on Tuesday February 13, 2018 @05:20PM
(#16371364)
Well, funnily enough, quantum computing CAN help with factoring, and likely not with TSP. Factoring is one of those rare problems in NP that is not known to be NP-complete, but for which we also don't know a polynomial algorithm. In 1994, Peter Shor came up with a quantum algorithm that solves factoring in polynomial time [1].
On the other hand, it is generally not believed that quantum computers would be able to solve NP-complete problems such as TSP in polynomial time.
On the other hand, it is generally not believed that quantum computers would be able to solve NP-complete problems such as TSP in polynomial time.
[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm