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.
Re:Review of Vivek Wadhwa’s Washington Post Column on Quantu...
by randomsearch on Tuesday February 13, 2018 @05:25PM
(#16371406)
I think that was a joke...
Re:Review of Vivek Wadhwa’s Washington Post Column on Quantu...
by jacquesm on Tuesday February 13, 2018 @06:14PM
(#16371807)
I think he improved on it.
Re:Review of Vivek Wadhwa’s Washington Post Column on Quantu...
by eru on Wednesday February 14, 2018 @12:32PM
(#16377507)
Linear programming is in P.
Perhaps you are talking about Integer Linear Programming?
The traveling salesman problem isn't hard. It's one of those things that's NP-hard only for pathological cases, as is linear programming. Solutions to the TSP which produce a near-optimum result, and the optimal result most of the time, are easy. (Connect nodes arbitrarily. Then randomly cut two links to split path into three sections, try all ways to reconnect the three sections, pick the best. Repeat until no improvement for a while. Bell Labs, 1960s.)
Now, if quantum computing could help with factoring, we'd have a problem.
[1] https://books.google.com/books?id=tTkEAAAAMBAJ&pg=PA40&lpg=P...