Home / IT & Computer Science / Coding & Programming / Understanding Quantum Computers / Quantum Fourier Transform
Quantum Fourier Transform
Quantum Fourier Transform is a quantum equivalent of the classical Fourier transform.
We introduced the classical Fourier transform rather briefly earlier this week. There is a quantum equivalent called naturally enough, the quantum Fourier transform or QFT. Like the classical transform, it takes data from the original signal representation to the frequency domain representation. It differs and then it operates on a superposition state and produces a different superposition state as the output. It works using interference, which is we saw on the first week makes the signal either stronger or weaker. The components interfere either constructively or destructively depending on their amplitude and phase. Let’s take a look at a three-qubit example.
Recall that each of the eight possible states of a three-qubit registers called a basis state and effectively represents an additional dimension in our space. We can write them in the ket notation or a full vector notation. Inside the ket, we can write them using either decimals or binary notation. Using the QFT, we will see that the phase in various state changes. The size of the individual step depends on how many qubits we have in our register. For N qubits, the step size is 1 over 2 to the N of the revolution, so for 2 qubits for example, the size of our step is one quarter of a revolution.
For 3 qubits, the size of our step is one-eighth of a revolution. For 4 qubits, the size of our step is one-sixteenth of a revolution. When the QFT operates on any individual basis state alone, it produces a superposition of all the possible states as its output. Here is the transform of the zero state. Here we see, QFT or 0 ket, written – same thing written in the vector form and then our output over here. The amplitude of each of the states is all the same so that we would have an equal probability of measuring any of them if we measure the register right now.
Note that the dials are scaled so that each vector is the size of the circle in this animation. The length of each one should really be 1 over the square root of 8; however, the phase depends on which basis state was input and which output basis state we are looking at. This animation shows the effective 3 qubit QFT using the ket notation and the vector notation for the input and our clock down notation for the output. Watch the animation a couple of times through the loop, can you see the relationship? The top dial doesn’t move. Its value is the same in regards to the input.
The second dial moves one-eighth of a revolution for each step change in the input value. The third dial moves twice as fast and the fourth dial moves three times as fast. The position of the clock hand for each output basis state is the product of the input state value and the position in the output vector 0 through 7, all modulo two pi, of course. In a quantum system, things start to get interesting when your input is a superposition of state.
If we start with a superposition two states as our input, the output will be the superposition of their transforms, so the quantum Fourier transform of the state 0 plus 4 equals the quantum Fourier transform of the state 0 plus the quantum Fourier transform of the state 4. In order to work this out, we need to know how two vectors add. Working in our clock dial vector representation, a few examples will show us what happens. If we have two vectors pointing up, they add and we get one pointing up. If we have one pointing up and one pointing down, they cancel and we get nothing.
If we have one pointing up into the right and another down to the left, those also cancel and we get nothing. If we have two vectors pointing to the right, we add them up, they add up. Now, let’s look at what happens when we apply this to our entire vector. So here’s the QFT of the 0 plus 4 state. It equals the QFT of the 0 state, which is all the up vectors plus the QFT of the 4 state which was alternating up and down vectors. Add those up and you get this result. Remarkably, half of our vectors now point up and the other half have been canceled out entirely, that’s constructive interference here and destructive interference there.
Look at this difference we have here, so this is 0 plus 4. What happens when we have the inputs 1 plus 5 instead? Well, in this case, we have the QFT of the 1 state plus the QFT of the 5 state and now our phases are a little less obvious, but it turns out they are actually matching up in the same pattern. The same set of values have a positive vector that’s been constructively interfered and the same set of values have no vector at all where we’ve had destructive interference. Same thing happens when our input state is the superposition of the 2 state and the 6 state.
Again, we get constructive interference on the states 0, 2, 4 and 6 and destructive interference on the states 1, 3, 5 and 7. Same thing happens when our input state is the superposition 3 plus 7, again constructive interference on 0, 2, 4 and 6 and destructive interference on 1, 3, 5 and 7, that’s the basic effect of the quantum Fourier transform.
Like the classical Fourier transform, quantum Fourier transform (QFT) takes data from the original signal representation to the frequency domain representation. The QFT differs from the classical Fourier transform in that it operates on a superposition state and produces a different superposition state as the output. QFT works using interference, which as we saw in the first week makes the signal either stronger or weaker. The components interfere either constructively or destructively, depending on their amplitude and phase. Let’s take a look at a three-qubit example.
量子フーリエ変換
古典的なフーリエ変換と同様に、量子フーリエ変換（QFT）はデータ表現を元の信号から周波数領域に変換する操作を指します。 ですが、QFTは古典フーリエ変換と違い、重ね合わせの状態で動作し、出力となる別の重ね合わせを生成します。 QFTは、第一週で見てきたような波の干渉を利用し、波の位相及び振幅に応じて、信号を強め合ったり弱め合ったりします。 ３量子ビットを使ったQFTの例を見てみましょう。
Reach your personal and professional goals
Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.
Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.
