Quantum computers don't try all the possible solutions, so how does the QFT really work?

Question

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.

Answer 1

The question asked is:

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?

And this is the quote you say Scott made:

Scott Aaronson is fond of saying "Quantum computers do not solve hard search problems instantaneously by simply trying all the possible solutions at once."

I agree with Scott, that quantum computers do not solve search problems "instantaneously". If you look at Grover's search algorithm, for example, there is still a lot of work to be done, and a cost of $\mathcal{O}(\sqrt{N})$ gates for searching an $N$ entry database. Wouldn't the number of operations be $\mathcal{O}(1)$ if we were just searching everything simultaneously at once?

The QFT however, does act on all of its input qubits at once. For example, here's a 2-qubit QFT:

So it is indeed acting on all input qubits at once, which is maybe why you think it contradicts Scott's statement, but here's where the loophole is: Scott's quote is only about search problems and QFT is not doing any search. QFT is literally just changing $N$ qubits according to a matrix like the one I showed.

Answer 2

In many quantum algorithms, the first step is to compute some problem on all instances at the same time -- if you wish, you compute all solutions at once. But then you are left with a state such as $$ \sum_x |x\rangle|f(x)\rangle\ , $$ where the information about the solution is contained in $|f(x)\rangle$. (Grover is a bit different, but the oracle still queries all solutions at once, just in a different way.) However, it is completely unclear how to access the solution. This is what makes each algorithm different, and what is the tricky thing to figure out -- how to get the information out by measuring. This is what distinguishes Deutsch-Jozsa, Simon's algorithm, period finding, ... : You need to find a smart way to extract said information.

Thus, evaluating all function values at once is usually one part of the problem (as e.g. for period finding = QFT = Shor), but this is not sufficient: It must be combined with a smart way of extracting the information, which is only possible in certain cases. Thus, it is very different from a non-determinstic Turing machine.