2
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ The QFT doesn't "simply try all possible solutions at once." The "deeper" component of the QFT is associated with controlling and choreographing the constructive and destructive interference of the wave function. Aaronson is also fond of saying a good test for popular descriptions of QC's require mention of something resembling "negative" amplitudes, as in destructive interference. $\endgroup$
    – Mark S
    Apr 12 '20 at 23:09
  • $\begingroup$ @MarkS, do you care to expand this to a full answer? $\endgroup$
    – vy32
    Apr 12 '20 at 23:57
  • $\begingroup$ @vy32 ... QFT and QFFT are not the same thing. Shor's algorithm uses QFT. QFT is just a silly name. It's not a quantum fast Fourier transform and has very little to do with the fast Fourier transform. You can confirm this by looking at the Wiki page for QFT and searching the word "fast"... you will not find it. $\endgroup$ Apr 17 '20 at 18:23
  • $\begingroup$ Although to be fair, the Cooley-Tukey fast Fourier transform was repeatedly referenced by Shor in his paper... $\endgroup$
    – Mark S
    May 29 at 0:01
2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ Very nice. Can you point me at an algorithm (or python code) for generating the QFT matrix for $N>2$ ? $\endgroup$
    – vy32
    Apr 17 '20 at 23:02
  • $\begingroup$ Yes, pick a value for $\omega$ and substitute it into this matrix: en.wikipedia.org/wiki/Quantum_Fourier_transform. This is why this is not really a "fast Fourier trasform" ... it's not really an algorithm as much as it's just a matrix. $\endgroup$ Apr 17 '20 at 23:17
  • $\begingroup$ Neat! And $\omega=i$ for all values, it's just N that changes? $\endgroup$
    – vy32
    Apr 18 '20 at 14:01
  • $\begingroup$ @vy32 when you have more qubits, N gets bigger. $\omega$ is an N$^{\textrm{th}}$ root of unity, so in my example $\omega=i$, but it does not always have to be $i$! $\endgroup$ Apr 18 '20 at 17:10
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.