# Why is the second register needed to define bit flip quantum oracles in a way that distinguishes between complementary oracles?

If our input $$x \in \{0, 1\}^{n}$$ is given as a black box, we usually query an oracle as follows.

$$O_{x}|i, b \rangle = (-1)^{b x_{i}} |i, b \rangle$$

$$i = \{1, 2, \cdots, n \}$$ is the index of the input we are querying. $$x_{i}$$ is the value at that index. $$b = \{0, 1\}$$ is an arbitrary Boolean value.

Why do we need the $$|b \rangle$$ register? Why can't we have a query of the form

$$O_{x}|i \rangle = (-1)^{x_{i}} |i \rangle$$

This transformation is certainly unitary. Andrew Childs notes in his lecture that we can't distinguish between $$x$$ and $$\bar{x}$$ (bitwise complement of $$x$$) if we exclude the $$|b \rangle$$ register. I don't see why this should be the case.

Why can't we have a query of the form $$O_{x}|i \rangle = (-1)^{x_{i}} |i \rangle$$ This transformation is certainly unitary. Andrew Childs notes [...] that we can't distinguish between $$x$$ and $$\bar{x}$$ (bitwise complement of $$x$$) if we exclude the $$|b \rangle$$ register. I don't see why this should be the case.
Let $$\lvert \psi \rangle = \sum_k u_k \lvert k \rangle$$. Then: \begin{align*} O_x \lvert \psi \rangle & = \sum_k (-1)^{x_k} u_k \lvert k \rangle \\[2ex] O_{\bar x} \lvert \psi \rangle & = \sum_k (-1)^{\bar x_k} u_k \lvert k \rangle \\ & = \sum_k (-1)^{1 + x_k} u_k \lvert k \rangle \\ & = \sum_k - (-1)^{x_k} u_k \lvert k \rangle \\ &= - O_x \lvert \psi \rangle. \end{align*} Because global phases (such as the factor difference between $$O_{\bar x} \lvert \psi \rangle$$ and $$- O_x \lvert \psi \rangle$$) aren't detectable, it is impossible to distinguish between these two states. In fact, more properly speaking, they are the same state — and these two different vectors are just equivalent ways of representing it, as the differences they have do not correspond to any physical properties.