# How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as

$$C U_{a^{2}}(|c\rangle|y\rangle)=|c\rangle\left|\left(a^{2^{i}}\right)^{c} y \bmod N\right\rangle$$ in this paper.

It's described similarly here

The issue I have is this does not seem to be unitary, since $$N<2^n$$, we can get stuff like this:

$$C U_{a^{2}}(|c\rangle|0\rangle)=C U_{a^{2}}(|c\rangle|N\rangle)=|c\rangle\left| 0\right\rangle$$

I don't understand how modular multiplication can possible be inversible when we explicitly choose $$N < 2^n$$, and so there have to be values the mod to the same result.

• As mentioned in the answer to the question you mention, the unitary $CU_{a^2}$ only works as a controlled modular exponentiation matrix for states $|c\rangle |y\rangle$ with y<N. Hence $|c\rangle |N\rangle$ should not necessarily map to $|c\rangle |0\rangle$ (and by your argument indeed it doesn't). – smapers Jun 11 at 11:48
• A more detailed descriptions of reversible modular multipliers: arxiv.org/abs/1202.6614 (in particular, it says what to do with numbers exceeding $N$). – Dmitri Urbanowicz Jun 11 at 11:55
• Thank you! I was really confused – Marlon_T Jun 11 at 17:19