  We found that the actual computational time-cost of the QFT is O(n 2^n) for
large n in a quantum computer using nuclear spins. The computational cost of a
quantum algorithm has usually been estimated as the sum of the universal gates
required in such ideal mathematical models as the Quantum Turing Machine(QTM)
and the quantum circuit. This cost is proportional to an actual time-cost in
the physical implementation where all quantum operations can be achieved in the
same time. However, if the implementation takes a different time for each
quantum gate, there is a possibility that the actual time-cost will have a
different behavior from the ideal cost. So we estimated the actual time-cost of
the QFT in these implementations by considering the gating time. The actual
time-cost is drastically different from O(n^2) estimated by complexity
analysis.

Quantum Physics