# Why is the operator $M_a |x\rangle= |a \cdot x \pmod{N} \rangle$ unitary?

If $$N\geq 2$$, $$a\in \mathbb{Z}_N$$, and $$a^r= 1$$ for some $$r$$. Consider the operator $$M_a$$, which is related to order finding :

$$M_a |x\rangle= |a \cdot x \pmod{N} \rangle$$ if $$x\in \mathbb{Z}_N$$

What is an easy way to show that it's a unitary?

• What are your thoughts on this? have you attempted anything to see why it's a unitary operation? Nov 19, 2023 at 20:14
• I have no idea on what ket 3, for example, can possibly be. Or ket of the equiv. class 3 of $\mathbb{Z}_N$ Nov 19, 2023 at 20:34

Assuming $$\gcd(N,a)=1$$, then the operator $$M_a$$ mapping $$x\in\mathbb Z_N$$ to $$a\cdot x \pmod N$$ is a permutation, which means that it’s reversible, ergo unitary.
• +1 The assumption is in fact not only sufficient, but also a necessary condition for unitarity of $M_a$. If $\gcd(N,a)=b>1$, then $N=ub$ and $a=vb$ for some non-zero $u,v\in\mathbb{Z}_N$ and $M_a|u\rangle=|0\rangle=M_a|0\rangle$, so $M_a$ fails to be injective. Nov 20, 2023 at 3:41
• @AdamZalcman indeed, as another way to state the same, in the OP's framing $a$ must generate all of $\mathbb Z_N$, and hence $r$ must equal $N$. Nov 20, 2023 at 14:00