Let us assume that we start with the state

(1) |

(2) |

(3) |

(4) |

Now, the phase factor can be rewritten as

(5) |

since if . We thus notice that the phase for any given value of (ie the n-th least significant bit of k) depends only on the values of the bits of of order less that . If we line up the bit representations of and we have

... | ... | ||||||

... | .... |

The Fourier factor which depends on is

(6) |

We can now perform the Fourier Transform bit by bit starting with the lowest
digit of , namely . Let me assume that we have managed to
transform the state by replacing the highest digits of with the
lowest digits of . I.e., I have created, by some sequence of
transformations, the state

(7) |

(8) |

This transformation can be decomposed into the two sets of transformations

(9) |

and

(10) |

The first transformation is just a rotation of the bit.

(11) |

The second set just correspond to a series of controlled one bit phase rotations.

(12) |

I.e., these are transformations which phase rotate the bit depending on whether bit is one or zero.

Thus given the transform up to bits, it requires a single rotation of a single bit, and controlled single-bit phase rotations, for a total of operations. Thus the whole Fourier transformation requires operations (, we recall is the number of bits in each of the numbers).

If we apply this Fourier transform to a state of the form

(13) |

(14) |

Note again that the representation is the bit reversed of the representation of . While one could do a bit reversal operation to get into the same bit order as , there is no point.