A search space that's 2^2000 big when each fitness function evaluation takes a few seconds is intractable on a conventional computer. The relative performance gain is exponential the more qubits you add, which is why this is the first interesting quantum computer (or quantum optimizer if you're being picky).

That's not how quantum annealing works. This is a pretty good walk through expected and actual gains. http://science.sciencemag.org/content/348/6231/215.full

I've never heard anyone claim it'd be exponential. In fact, there are proofs showing it can't be.

Yes, but you don't get to just input any optimization problem into the dwave. The problem is that the specific kind of optimization that the dwave can do (even ignoring the fact that the output doesn't correspond directly with a solution) hasn't been found to map to any problems classical computers are actually bad at.

If you really think the problems you work on are that novel and up the D-Wave's alley, I suggest you email one of the academic teams looking for problems that the D-Wave is good at. They've yet to find any.