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

Question

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?

Answer 1

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.

---

It sounds to me like you might be thinking that exact quantum algorithms are philosophically more desirable than approximate quantum algorithms. This is false. Approximate constructions are often orders of magnitude cheaper and achieve the same ultimate result.

For example, when factoring a 2048 bit number, you have to do a 2048 qubit QFT. More than 99% of the gates in that QFT circuit are phasing operations with phasing angles that are less than a trillionth of a trillionth of a trillionth of a degree. If you drop every single one of those operations, the result is basically observationally indistinguishable from what you'd get with the exact circuit. So the approximate circuit is 100x cheaper, because it omits 99% of the gates from the exact circuit, and gets essentially the same result. Obviously you do the just-as-good thing that's 100x cheaper.

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.