Say that I have a unitary gate $U$ such that $U|b\rangle=|b+1$ mod $N\rangle$. How would I go about finding $U^\dagger|b\rangle$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For a unitary $U$, the conjugate transpose $U^\dagger$ is the inverse of $U$, i.e. the linear operator such that$^1$ $U^\dagger U=UU^\dagger=I$.
Guess and check
The inverse is unique$^2$, so a general approach to finding it is to guess and check. For example, in the case of $U$ given by $U|b\rangle=|b+1\mod N\rangle$, we recall that the modular arithmetic inverse of the increment operation $$b\mapsto b+1\mod N$$ is the decrement operation $$b\mapsto b-1\mod N$$so we guess that $$U^\dagger|b\rangle=|b-1\mod N\rangle.$$ Next, we check \begin{align} U^\dagger U|b\rangle&=U^\dagger|b+1\mod N\rangle\\ &=|b+1-1\mod N\rangle\\ &=|b+0\mod N\rangle\\ &=|b\rangle. \end{align} Since this is true for every $b$, we have $U^\dagger U=I$ proving our guess is correct.
Invert permutation
If $U$ acts as a permutation $f$ on the computational basis $$U|b\rangle = |f(b)\rangle$$ then we have $$U^\dagger|b\rangle=|f^{-1}(b)\rangle$$ where $f^{-1}$ denotes the inverse permutation of $f$. This can be proved using a calculation similar to the one above \begin{align} U^\dagger U|b\rangle&=U^\dagger|f(b)\rangle\\ &=|f^{-1}(f(b))\\ &=|b\rangle \end{align} which shows that $U^\dagger U=I$.
$^1$ In finite dimensions $U^\dagger U=I$ implies $UU^\dagger=I$.
$^2$ Suppose $V$ and $W$ are two inverses of $U$. Then $VU=WU=I$, so
\begin{align}
VU-WU&=I-I\\
(V-W)U&=0\\
V-W&=0\\
V&=W.
\end{align}