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

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...

## 1 Answer

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?

• Those two conditions combined clearly gives $U U^\dagger=I$. The first, $U=U^{-1}$ is clear. But why eigenvalues of this operation are $\pm 1$ from which one follows $U=U^\dagger$? Oct 25 at 11:01
• Oh yes, of course: $U^2|\psi\rangle = \lambda^2 |\Psi\rangle$. From this I get trivially $\lambda = \pm 1$. Oct 25 at 11:15
• Why is my original approach wrong? When the norm is conserved in one orthogonal base, I thought, by insertion of the unit-operator, this is true in any base. The property "unitary" cannot depend on the base I use - where am I wrong? Oct 25 at 19:45
• Consider the operator $P=\sqrt{2}|+\rangle\langle +|$. This has $P|0\rangle=|+\rangle$ and $P|1\rangle=|+\rangle$. For both computational basis states of a qubit, the length is preserved. But for other states, such as $|+\rangle$, it is not. It should be sufficient to additionally prove that orthogonality of your outputs is preserved. Oct 26 at 6:39
• It's true I skipped over that (it wasn't obvious to me from the question what the appropriate level of detail was). It might be easiest to take a look at quantumcomputing.stackexchange.com/questions/5779/… Oct 27 at 9:48