5
$\begingroup$

$\newcommand{\qr}[1]{|#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?

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

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.