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

Question

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.

Answer 1

Consider the last part of your question:

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.