I've been struggling to understand the modular exponent bit of Shor's algorithm. My understanding is that it takes a register in the state $\frac{1}{\sqrt{Q}}\sum_{k=1}^{Q-1} |k\rangle |0\rangle$ to the state $\frac{1}{Q}\sum_{k=1}^{Q-1} |k\rangle |f(k)\rangle$ where $f(k) = x^{k}$ mod $N$. (Here, $x$ is the random integer found at the start of Shor's algorithm.)

My question is: Why is this operation unitary?


1 Answer 1


The critical thing, in this case, about a unitary operator is that it maps orthogonal states to orthogonal states (if $\langle i|j\rangle=0$, then $\langle i|U^\dagger U|j\rangle=0$, so the transformed vectors $U|i\rangle$ and $U|j\rangle$ are orthogonal). Now, you've defined what it must do for a set of states: $$ |k\rangle|0\rangle\mapsto |k\rangle|f(k)\rangle. $$ Now, it should be clear that all of the outputs are orthogonal to all other ones, simply as a result of the different values of $k$. So, surely, it will be possible to define a unitary over all possible basis states.

Indeed, the one of the usual starting points is to define the action of the unitary as $$ |k\rangle|y\rangle\mapsto \left\{\begin{array}{cc} |k\rangle|y+x^k\text{ mod }N\rangle & y<N \\ |k\rangle|y\rangle & y\geq N \end{array}\right. $$ (a second is to use $|k\rangle|yx^k\text{ mod }N\rangle$ on the top line). If we look at all possible $y$ and $k$, then we're looking at the whole basis. Again, different $k$s clearly give orthogonal vectors, independent of the value of $y$. Primarily, we have to check that $$ \langle y+x^k\text{ mod }N|y'+x^k\text{ mod}N\rangle=0. $$ This must be true provided $y-y'\text{ mod }N\neq0$, which is true for cases $y,y'<N$ and $y\neq y'$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.