Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quantum Fourier transform

  1. May 13, 2015 #1
    When using the Quantum Fourier transform to find the period of the function [itex]f(x)\equiv a^x\mod N[/itex] why is it that the input register is 2n qubits in size and the output register is n qubits?
  2. jcsd
  3. May 13, 2015 #2


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook