# Why are oracles Hermitian by construction?

$$\newcommand{\qr}{|#1\rangle}$$In this lecture, it is nicely explained how to define an operator that computes a function $$f(x)$$. I know how to implement such operators. (We just define $$O\qr{x}\qr{y} = \qr{x}\qr{y \oplus f(x)}$$.)

However, it it said in the lecture that this effectively proves $$O = O^\dagger$$ and I fail to see it so clearly. It says $$O = O^\dagger$$ by construction. How can I see that so clearly as it is implied?

• Just apply O a second time on your definition. – DaftWullie Oct 24 '18 at 20:48
• Brilliant! That's definitely an answer: it now hits me that $f(x) \oplus f(x) = 0$. Thank you! – R. Chopin Oct 24 '18 at 20:52

Showing that $$O=O^\dagger$$ is equivalent to showing that $$O^2=\mathbb{I}$$. In other words, $$O^2|x\rangle|y\rangle=|x\rangle|y\rangle$$ for all $$x$$ and $$y$$.

To show this, we start from the definition of the oracle $$O|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$$ and apply $$O$$ again: $$O^2|x\rangle|y\rangle=O|x\rangle|y\oplus f(x)\rangle=|x\rangle|y\oplus f(x)\oplus f(x)\rangle=|x\rangle|y\rangle$$ as required (since $$a\oplus a=0$$, and bitwise addition is associative).

Defining such oracles, you may visualize it as many controlled operations, especially $$\text{CNOT}$$s which is an easy way to build oracles.

We know the effect of the $$\text{CNOT}$$ is if the control is a 1 then we add 1 into the target (you can see it as part of a function itself but it is meant for one bit representing the output register). If we enumerate options on a simple 2-bit example with the first as control we have : $$\text{CNOT}(00) = 00; \text{CNOT}(01) = 01; \text{CNOT}(10) = 1(0+1)=11;\text{CNOT}(11) = 1(1+1)=10$$

We know also that we cancel the effect of the CNOT by applying it again. Take the action of a CNOT but now on images from a first CNOT: $$\text{CNOT}(00) = 00; \text{CNOT}(01) = 01; \text{CNOT}(11) = 1(1+1)=10;\text{CNOT}(10) = 1(0+1)=11$$

So you see that the effect on bits representing the output of your function represented by controlled operations.

The $$\oplus$$ symbol illustrate that if I may say so.