How does this represent modular multiplication

Question

How does this circuit map $|x\rangle$ to $|7x \space mod15\rangle$? Looking into Shor's and I thought that phase kickback causes the modular exponentiation part to be mapped onto the measurement qubits through the Fourier basis.

Answer 1

Applying a NOT gate to every qubit in an $n$ bit register performs the transformation $f(x) = 2^n - 1 - x$. In this case that's $f(x) = 16-1-x = -x \pmod{15}$. So the NOT gates are equivalent to negating.

The triplets of CNOTs are performing swaps and the swaps implement a right-rotate:

An $n$ bit right-rotate is equivalent to multiplying by the multiplicative inverse of 2 mod $2^n-1$, which is $8$ in our case.

Together these two multiplications multiply by $-1 \cdot 8 = -8 = -8 + 15 = 7 \pmod{15}$.

Note that the circuit isn't quite correct. There is a degeneracy where $|0\rangle$ is mapped to $|15\rangle$ instead of $|0\rangle$. In the general case, unexpected information could leak into this degeneracy and decohere when the register is measured. But in the context of Shor's algorithm you know the register has no overlap with $|0\rangle$ so it's fine.

Also note that if your qubits are not restricted to linear connectivity, you can make the circuit shallower by running two of the swaps in parallel: