It's just taking away only one bit of difficulty. Since quantum computers still have to iterate through a extremely large numbers of inputs in order to find one below some nonce N, The worst case running time is still 2^(256-1-log2(nonce) <-- number of nonce bits) * SHA256_speed*2 [as you perform a SHA256 twice for each input].

It's still far too long to throw QCs at the problem and expect them to finish in a reasonable amount of time. Also we can't really claim anything specific about how fast QCs can do any algorithm until someone actually designs an instruction set for them like ARM or x86 (or CUDA/OpenCL, in the case of GPUs). If we expect here to be an industry around QCs they all have to be able to run the same kind of programs. Even ASIC miners are to some extent configurable.