# Why don't we use exact QFT in Shor's algorithm?

In DLP ($$g \equiv x^r$$ (mod $$p$$) with known order of $$x$$ as $$p$$), Shor algorithm applies QFT to the state $$\frac{1}{p}\sum_{a, b}^{p-1}|a, b, g^ax^b⟩$$ Here QFT is of size $$q$$ that satisfies $$(p-1)\le q< 2(p-1)$$. Then the state becomes $$\frac{1}{pq}\sum_{a, b}^{p -1}\sum_{c, d}^{q - 1}\text{exp}(\frac{i2\pi(ac+bd)}{q})|a, b, g^ax^b⟩$$ The amplitude of the state $$|c, d, g^k⟩$$is $$|\frac{1}{pq}\sum_{a+br\equiv k\,(\text{mod}\,p)}^{p -1}\text{exp}(\frac{i2\pi(ac+bd)}{q})|$$ In Shor algorithm, $$q$$ also satisfies $$\log_2(q)\in\mathbb{N}$$ because size of QFT is only limited to power of 2, and hence in most of cases $$p\ne q$$. Then the probability analysis becomes a mess, and we need to run the circuit polynomial times to get a nice pair of $$(c, d)$$ (so-called "good state").

However, if $$p=q$$, then the amplitude becomes $$|\frac{1}{p^2}\sum_{b=0}^{p -1}\exp(\frac{i2\pi(kc+b(d-cr))}{p})|$$ This is the easy case of DLP described in original paper of Shor algorithm, which proves that in this situtation $$c$$ and $$d$$ must satisfy $$d=cr\,(\text{mod}\,p)$$. If $$c$$ and $$p$$ is coprime, then we get the result.

Here $$p=q$$ can be achieved by exact QFT of arbitrary size $$N$$ that does $$|a, 0⟩\mapsto|\Phi_a, 0⟩,\text{ where }|\Phi_a⟩=\frac{1}{\sqrt{N}}\sum_{c=0}^{N-1}\exp(\frac{i2\pi}{N}ac)|c⟩$$ There is a lot of spare auxiliary qubits after modular operations. Thus, we don't need additional qubits for implementing exact QFT.

Exact QFT has $$O(n^2)$$ operation complexity. It should be acceptable compared with $$O(n^3)$$ complexity of the entire circuit. However, all paper I read use non-exact QFT to solve DLP. Is there any shortage of exact QFT that I missed?

The circuits for the QFT where $$N$$ is a power of 2 are simpler than circuits where $$N$$ is an arbitrary number. They get just-as-good results with lower cost. Power of 2 sizes also enable important optimizations like qubit recycling, which allow you to only store one exponent qubit at a time, which is a substantial space savings.
Even if you wanted to stick to exact quantum algorithms out of stubborn principle, it's not actually physically plausible to run them. The control signals you send into physical hardware have limited precision. You cannot rotate by 45 degrees; you can only rotate by $$45 \pm \epsilon$$ degrees. You can make $$\epsilon$$ amazingly small by using quantum error correction, but you can never make it zero. Everything is already tainted by imperfection and approximation. Might as well revel in it.