Why is the function operator used in Simon's algorithm unitary?

Question

From the Qiskit textbook I read about Simon's algorithm. There are two n-wide quantum registers, so the general state is given by

$$|x\rangle_n|y\rangle_n$$

where x and y are the $2^n-1$ binary representations. A function from the n-subspace into n-subspace id defined by

$$f: |x\rangle\mapsto|f(x)\rangle$$

Now, the "query function" is given by the operation

$$|x\rangle|a\rangle \rightarrow |x\rangle |a \oplus f(x)\rangle$$

All building blocks in quantum computation shall be unitary transformations, so this mapping is unitary too - but how can I prove that this is really the case?

Is it enough to show, that norm is conserved like this:

Denoting

$$U|x\rangle|a\rangle = |x\rangle |a \oplus f(x)\rangle$$

I would have

$$\langle x| \langle a|U^\dagger = \langle x| \langle a \oplus f(x)|$$

so $$\langle x| \langle a|U^\dagger U |x\rangle |a\rangle= \langle x|x\rangle \langle a \oplus f(x)|a \oplus f(x)\rangle = 1 \cdot 1 = 1$$

But this appears a bit too trivial to be a prove...

Answer 1

The easiest way to prove this is to apply the operator twice $$ |x\rangle|a\rangle\mapsto |x\rangle|a\oplus f(x)\rangle\mapsto |x\rangle|a\oplus f(x)\oplus f(x)\rangle=|x\rangle|a\rangle. $$ So, two applications of the function is the identity operation. Thus, the function is its own inverse, $U=U^{-1}$. Moreover, the eigenvalues must all be $\pm 1$, which shows that, for example, $U=U^\dagger$, and hence $UU^\dagger=I$, the standard relation for a unitary.

Incidentally, for what you tried to prove, is it clear that because, in a certain basis, all the lengths of those basis states are preserved, that the lengths of all possible superpositions of those states are also preserved?