From the Qiskit textbook I read about Simon's algorithm. There are two n-wide quantum registers, so the general state is given by
where x and y are the $2^n-1$ binary representations. A function from the n-subspace into n-subspace id defined by
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:
$$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...