Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?

Question

I have been studying on Quantum Fourier Transform (QFT) by myself, and I am little bit confused about how could QFT be used. For example, if the QFT of three quantum bits is

$a_1|000\rangle + a_2|001\rangle + a_3|010\rangle + a_4|011\rangle + a_5|100\rangle + a_6|101\rangle + a_7|110\rangle+ a_8|111\rangle$

three questions arising in my mind:

1. Whether or not the useful information is represented by the probability amplitude coefficients ($a_1,..., a_8$) of the superposition state? Are these coefficients the same as their counterparts in DFT?
2. To my best knowledge, once a quantum system is measured, the superposition state will be destroyed, and the information represented by the probability coefficients ($a_1, ..., a_8$) will be lost. Then how could the coefficients be extracted from by measurements?
3. How is QFT related with Shor’s Algorithm?

Thank you by advance for answers.

Answer 1

You probably shouldn't be thinking of the Quantum Fourier Transform as being something where you want to extract the outcoming probability amplitudes. As you say, when you start measuring, you destroy the superposition. The only way to extract the amplitudes is to make the same state many, many times, and keep repeating your measurements until you get enough statistics to determine the $|a_n|^2$ with reasonable accuracy.

Instead, think of it as a quantum subroutine. Something that takes a quantum superposition as input, and provides a superposition as output. So, for example, QFT is used as a subroutine within Shor's algorithm. Before application of the QFT, Shor's algorithm has worked very hard to produce a superposition that somehow contains the correct computational answer, but it contains that answer encoded in the relative phases of the superposition. The QFT spits out that relative phase information as a bit string. The trick is that you don't want to know the probability amplitudes. You want to know the bit string that is produced with highest probability (i.e. the value of $n$ for which $|a_n|^2$ is largest. It occurs with a probability at least $4/\pi^2$, if memory serves). In fact, all you do is run the algorithm once. There's a fair chance you've got the right answer, and with a bit of classical post-processing, you can tell whether or not you got the right answer, and hence whether or not you need to run the whole algorithm again.

Answer 2

1. The probability amplitudes of a quantum state are what characterises the state itself. In this sense, they convey all of the information. The modulus squared of $a_i$ gives the probability of finding the system in the $i$-th state (for example, $\lvert a_2\rvert^2$ is the probability of finding your system in the state $\lvert 001\rangle$). Furthermore, the phases of $a_i$ give information about the way the state will turn out when subjected to some evolution (equivalently, they tell you the outcome probabilities with respect to other measurement choices).

   These coefficients are not the same as their counterparts in the context of the DFT, in the sense that the DFT produces as output a list of numbers written in your computer, while the QFT is a physical operation that produces a quantum state whose amplitudes are related to the amplitudes of the initial state via the DFT. In particular, while one has in principle complete knowledge about the output of a DFT of some vector, you do not have direct access to the amplitudes of the quantum state that is obtained after applying the QFT to some state.

2. Yes, measuring the system will only give you one of the states of which the system is in a superposition of. Measuring your state you might get the second output, then the fourth, and so forth. If you perform the measurement many times, however, you will recover $\lvert a_i\rvert^2$ into the frequencies with which you observe the different outcomes. More generally, one can (but generally does not want to) perform quantum state tomography to completely reconstruct the amplitudes of a state.

   However, it is important to notice that reconstructing a state via tomography is highly inefficient, and will most likely destroy all the advantages you would have gained by running a given quantum algorithm. Instead, the usefulness of the QFT (and similar operations) is that, if you set things up correctly, you can get the answer to whatever question you are asking more or less directly. For example, say the answer to your question is "3", then you might have an algorithm which generates a quantum state such that, after application of the QFT, evolves into the state $\lvert001\rangle$, that is, the third state using your notation. Note that such a state does not have the problem abovementioned: if you measure the output and find it to be "3", then that is the answer to the problem (in an ideal scenario at least).

3. They are related in that the QFT is a fundamental ingredient of Shor's factorisation algorithm. Very roughly speaking, the idea is to reduce the problem of factoring to the problem of period finding, and then period finding can be efficiently solved using the QFT. If you want more details about this process I would ask it in a separate question though.