1
$\begingroup$

Let $U_f$ be the quantum gate such that $| x \rangle | y \rangle \mapsto | x \rangle |y\oplus f(x) \rangle$, where $x$ is some bit string of size $n$, $|y\rangle$ is a qubit, and is $f$ is some boolean function. It is easy to show that if $| y \rangle = | - \rangle$ then the output is $(-1)^{f(x )} |x \rangle | - \rangle$. That is, the effect of $f(x)$ is moved from the last qubit to the phase of $| x \rangle | - \rangle$.

How can we do the opposite? That is, if we have some quantum gate such that $| x \rangle \mapsto (-1)^{f(x)} | x \rangle$. How can we move the effect of $f(x)$ from the phase of $| x \rangle$ to some other (extra) qubit $| y \oplus f(x) \rangle$?

I've tried entangling $(-1)^{f(x)} |x \rangle$ with $| - \rangle$ but I'm sort of stuck.

$\endgroup$
2
  • $\begingroup$ Do you have access to a controlled version of the phase oracle? $\endgroup$
    – Tristan Nemoz
    Feb 11 at 17:21
  • $\begingroup$ @TristanNemoz: I don't think so $\endgroup$
    – joeren1020
    Feb 11 at 18:14

2 Answers 2

1
$\begingroup$

It depends on how you have implemented the map that takes $|x\rangle$ to $(-1)^{f(x)}|x\rangle$. If you simply have a single qubit gate like that, it will be impossible to get out $|y \oplus f(x)\rangle$ because the $(-1)^{f(x)}$ is a global phase. Instead, let's assume your implementation has a control qubit (which I will draw as the second qubit and label $|y\rangle$. So, it adds the phase only if the second bit is inputted to be 1 and if the second bit is 0, it acts like identity. Then, your circuit can be interpreted as $U_f$ but with some Hadamard's around it.

enter image description here

Now, to get back to a function that puts $|y \oplus f(x)\rangle$ on the second qubit, we may use that the Hadamard is self inverse and obtain the following circuit.

enter image description here

where the bit within the dotted lines is in your implementation one single gate, which acts on the first qubit and is controlled by the second.

$\endgroup$
0
$\begingroup$

If you control a temporary move/copy of the value register to an ancillary register using Fredkin gates or Toffoli gates, the phasing effect will kickback onto the control qubit.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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