3 ms·
The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/que
by jcoffland 9y ago
The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer.
https://cstheory.stackexchange.com/questions/31084/travelling-sales-man-with-quantum-computers https://cstheory.stackexchange.com/questions/31084/travellin...
- xxs 9y agoIndeed, I have never heard how (any) NP-complete stuff would be solved by quantum computers. It was very surprising to see it as top comment.
- deleted 9y ago[deleted]
- visarga 9y ago> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?
- CJefferson 9y agoIt's unclear a quantum computer can find you an approximate solution any faster either.
- monob 9y agoDo you have a paper on approximating NP complete problems and the bounds on the error in the solution?
- jcoffland 9y agoThat has nothing to do with quantum vs. classical.
- visarga 9y agoApproximate solutions have to do with solving problems with limited resources and scaling up. Quantum computers will be fast at solving certain types of problems, while approximate solutions are fast at solving practical problems.