2 ms·
As I understand it, quantum computers will offer tremendous speed on the "traveling salesman" problem, and otherwise vastly improve questions of efficient resou
by chasil 3y ago
As I understand it, quantum computers will offer tremendous speed on the "traveling salesman" problem, and otherwise vastly improve questions of efficient resource scheduling and optimization.
https://en.m.wikipedia.org/wiki/Travelling_salesman_problem https://en.m.wikipedia.org/wiki/Travelling_salesman_problem
- Jabbles 3y agoAs that article says, approximate classical algorithms "can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution." Although faster quantum algorithms for the exact solution exist, I see no reason why this would result in "vastly" improved efficiency.
- zachf 3y agoMost quantum computer experts think that this is not the case, that it is very unlikely that quantum computers can solve NP-complete problems like travelling salesman more efficiently than classical computers. (In particular, the popular intuition that quantum computers “try a lot of solutions in parallel” is basically totally wrong, at least from the perspective of making a useful heuristic for what quantum computers are good for.) This is an older article, but its conclusions are still about right: https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Co...