1

Let $f: \{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function and say we are given a phase shift oracle $O_f^{\pm}$ which performs $|x\rangle \mapsto (-1)^{f(x)}|x\rangle$. Is there any way we can decide the value of $f$ on a given string $y\in {0,1}^n$?

I am aware that there is no way to use quantum gates to distinguish states of qubits that are the same up to a phase shift, so it seems like this wouldn't be possible but I have seen in many places that the other form of an oracle (the XOR oracle if you will) is "equivalent" to $O_f^{\pm}$, so you should be able to get the actual value of $f$ for a given string according to that.

Greedo
  • 13
  • 3

1 Answers1

1

I have seen in many places that the other form of an oracle (the XOR oracle if you will) is "equivalent" to $O_f^{\pm}$

What you've seen is probably the other way: going from the other oracle to $O_f^{\pm}$. In order to do the other way around, you would have to have access to a controlled version of your oracle.

Furthermore, if you define $\overline{f}$ to be $f$ but bit-flipped: $$\overline{f}(x)=f(x)\oplus1$$ Then $O_f^\pm$ and $O_\overline{f}^\pm$ differ only by a global phase, and thus are indistinguishable. Thus, it's not possible to recover the value of $f(x)$, as performing the same experiment with the exact opposite function would yield the same result. Note that this also tells you that you can't transform this oracle into a XOR one without having access to its controlled version.

However, what you can do is know $f(x)\oplus f(0)$. That is, if you arbitrarily fix the value of $f(0)$, then you can determine the value of $f(x)$.

Let $U$ be any unitary such that $$U|0\rangle= \frac{|0\rangle+|x\rangle}{\sqrt2}.$$ Prepare the state $U|0\rangle$: $$\frac{|0\rangle+|x\rangle}{\sqrt2}$$ then apply the oracle: $$\frac{(-1)^{f(0)}|0\rangle+(-1)^{f(x)}|x\rangle}{\sqrt2}$$ and finally apply $U^\dagger$. You can convince yourself that if $f(0)=f(x)$, then you will get back $|0\rangle$ (up to a global phase). However, if $f(0)\neq f(x)$, then you'll get a state that is orthogonal to $|0\rangle$, since unitaires preserve scalar product.

Thus, if you measure $|0\rangle$, then you know that $f(x)=f(0)$. Otherwise, you know that $f(x)=f(0)\oplus1$. Of course, there's nothing special about $0$, you can fix any other arbitrary input and find whether other coefficients match its sign.

Tristan Nemoz
  • 8,429
  • 3
  • 11
  • 39