1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – smapers Jun 11 at 11:48
  • $\begingroup$ A more detailed descriptions of reversible modular multipliers: arxiv.org/abs/1202.6614 (in particular, it says what to do with numbers exceeding $N$). $\endgroup$ – Dmitri Urbanowicz Jun 11 at 11:55
  • $\begingroup$ Thank you! I was really confused $\endgroup$ – Marlon_T Jun 11 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.