1
$\begingroup$

Is there a good comparison of alternative versions of the Quantum Fourier Transform (QFT) that mirror the alternative decimation-in-time or decimation in frequency versions for the conventional Fast Fourier Transform (FFT)?

Most of the descriptions that I find seem to be based on Nielsen and Chuang's text, which appears to be based on the decimation in frequency version: the input qubits are in regular order and the output qubits are in bit-reversed order.

The recursive construction presented in the text "Quantum Computing: A Gentle Introduction," by Eleanor Rieffel and Wolfgang Polak, appears to be based on a decimation in time version, where, once the recursion is rolled out, the input qubits will first be sorted in bit reversed order before performing the rest of the transform.

Partly, related to the above, I also have a question regarding drawing conventions for quantum circuits. In a large part of the world, we read from left to right and top to bottom. Therefore, if one is using the little-endian ordering with the lowest order qubit in the rightmost position for horizontal placement , I would expect vertical placement to use a convention with the lowest order qubit in the bottom-most position. However, almost all the circuit diagrams I see for the QFT seem to have the lowest order qubit in the top-most position (and other circuit diagrams do not necessarily follow a consistent convention). I'd appreciate any insight into why this is the case.

$\endgroup$

1 Answer 1

1
$\begingroup$

Some versions of QFT include a swap of the bits at then end so that the outputs are in the correct order. Other versions of QFT don't include the bit swap in order to save gates. I don't think anyone considers one more "correct" than the other.

As to your overall question. Remember that quantum computing is still in its infancy. It wasn't until the early 20th century that mathematicians finally all agreed that "1" wasn't prime, and you could still find text books well into the 1970s in which "1" was prime. We still have both big-endian and little-endian computers, even though little-endian appears to be gaining the upper hand. There is no "right" answer to the drawing conventions. Eventually a consensus will be reached. Or maybe it won't.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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