Quantum Fourier transform

[jimmycricket]

When using the Quantum Fourier transform to find the period of the function f(x)\equiv a^x\mod N why is it that the input register is 2n qubits in size and the output register is n qubits?

 

[Strilanc]

The overall period finding circuit probably uses ancilla bits, but turns them into measured garbage along the way. The Quantum Fourier Transform doesn't need ancilla bits, or measurement, so it's not the cause for adding them.

Personally, I wouldn't count ancilla bits against the input size. The circuit takes n input bits and n ancilla bits, burns the neg-entropy in the ancilla bits, and produces n outputs.