You are, in fact, wrong -- quantum computers aren't as powerful as you think they are.
The problem is that for what you describe as "root finding" a naive quantum computer only gets a quadratic speedup. Your 256^1000 possibilities still take on the order of 256^500 steps to search.
With that said, if you can build a computer around a closed timelike curve ("time travel") it would be powerful enough to do what you want. The idea here is that the computation starts off by receiving a value from the future, call it N, which it should test out to see if it is a solution. If N is the solution it reports back N at the end, otherwise it reports N+1.