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?

Simulated 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

[2] https://en.wikipedia.org/wiki/Quantum_annealing?wprov=sfti1

Simulated annealing is not a linear programming problem!

Routing, TSP, scheduling, they all benefit from huge speed ups.

I 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

it 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.

Ok 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.