How to implement modular exponentiation efficiently in Shor's algorithm?

Question

I'm a noob in quantum computing and I'm trying to get Shor's algorithm working on Q# (the language is unrelated). However, I'm stuck on computing $f(x)$s in the quantum circuit. Let $N\sim \log_2(n)$ be the number of qubits needed for finding the period. As far as I know, we can initialize $s=1$, and multiply it with $a,a^2,a^4 \cdots a^{2^{N-1}} \mod n$ according to the $N$ control qubits. However, all methods I can think of needs around $O(N^2)$ modulus and thus $O(N^2)$ ancillary clean qubits (for example, compute $a,a^2,a^4 \cdots a^{2^{N-1}}\mod n$ beforehand, use additions, comparing numbers and subtracting accordingly). Is there a way to implement modulus as some reversible circuit? Or, am I all wrong?

Answer 1

There is no circuit that performs the mod operation reversibly. You need to keep your numbers mod'ed the whole time. For example, instead of using an adder and then attempting to mod, use a fundamentally modular adder.

There's actually quite a lot of detail that goes into constructing these circuits. Too much for an answer here. A preprint that goes through all the details (and had working ProjectQ code at the time) is "Factoring with n+2 clean qubits and n-1 dirty qubits".

Here's a few example diagrams:

Note that the constructions are really going out of their way to avoid using ancillae, so they often have not-so-great gate counts.

And here's one to reinforce the point that it's complicated: