Skip to 0 minutes and 3 secondsWe 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.

Skip to 0 minutes and 42 secondsRecall 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.

Skip to 1 minute and 21 secondsFor 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.

Skip to 1 minute and 59 secondsNote 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.

Skip to 2 minutes and 36 secondsThe 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.

Skip to 3 minutes and 4 secondsIf 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.

Skip to 3 minutes and 39 secondsIf 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.

Skip to 4 minutes and 23 secondsLook 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.

Skip to 5 minutes and 2 secondsAgain, 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.

# 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.

© Keio University