Scott Aaronson is fond of saying "Quantum computers do not solve hard search problems instantaneously by simply trying all the possible solutions at once." That is, they are not non-deterministic Turing Machines.
However, most descriptions I've read of quantum QFT say that the way it works is by using qubits that are both 0 and 1 at the same time. So is the QFT, which is the basis of Shor's factoring algorithm, an exception Aaronson's aphorism, or is there something else going on that's deeper?
Based on @MarkS's comment, I gather that the something deeper involves constructive and destructive interference and the Chinese Remainder Theorem.