Exactly. It makes no difference how powerful quantum computers are for Deutsch's argument. If we had waited exponential time for a classical computer to do it, we would not wonder "where the number was factored." Waiting only polynomial time for it to be factored then begs the question.

I am well aware of the extremely interesting complexity limitations of quantum computing. It definitely only extends computational capability a little bit -- and we still can't even prove that P does not equal NP. But none of this is relevant to Deutsch's "where was the number factored" argument. He is saying that if quantum states are physically real and not just a calculational tool, then you have to give a physical account of how Shor's algorithm works and the orthodox views of wavefunction collapse could not do that.