3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\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.