4 ms·
can you give an example of a linear programming task that is not currently practical to solve on classical computers but could become so with a huge speed up?
by kaiabwpdjqn 7y ago
can you give an example of a linear programming task that is not currently practical to solve on classical computers but could become so with a huge speed up?
- MrK93 7y agoRouting, TSP, scheduling, they all benefit from huge speed ups.
- kaiabwpdjqn 7y agoI guess. But we already optimize these things. Without any specific domain in mind, I wonder how much better we could get. Like maybe amazon could find the global minimum cost to route, but right now it’s getting pretty darn close. Or maybe that’s entirely naive and the potential for finding faster solutions to real time problems is huge
- dekhn 7y agoit is huge. that's the only reason people are motivated to implement QC- because in principle then we can break crypto, do QM much faster, solve intractable problems, etc. Day-to-day, we're not really blocked on QC to get important work done.
- kaiabwpdjqn 7y agoOk but what I’m looking for is an actual example of an intractable problem. Breaking crypto is one, I guess, but it’s also one that makes everything worse, so I don’t take that as a useful outcome.
- alex_anglin 7y agoSimulated annealing[1] versus Quantum annealing[2], though it’s not there yet practically speaking as I understand it. [1] https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing [2] https://en.wikipedia.org/wiki/Quantum_annealing?wprov=sfti1 https://en.wikipedia.org/wiki/Quantum_annealing?wprov=sfti1
- kragen 7y agoSimulated annealing is not a linear programming problem!