$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$ When using Grover's algorithm to invert a function $f\colon \{0,1\}^m \rightarrow \{0,1\}$, an ancilla bit is used in order to "flip the sign" of basis vectors $\ket{i_0}$ such that $f(i_0) = 1$. In many expositions that I've seen, the ancilla bit is omitted afterwards because we don't touch it again. I'm wondering why we are able to do this.

In particular, in [BBHT96], they say that the action of a single Grover iteration (assuming a single satisfying assignment) is to map

$$k\ket{i_0}+l\sum_{i \neq i_0} \ket{i}$$ to $$\left(\frac{N-2}{N}k+\frac{2(N-1)}{2}l\right)\ket{i_0} + \left(\frac{N-2}{N}l-\frac{2}{N}k\right)\sum_{i \neq i_0} \ket{i} $$

However, I'm wondering why it isn't actually a map to

$$\left(\frac{N-2}{N}k\ket{1}+\frac{2(N-1)}{2}l\ket{0}\right)\ket{i_0} + \left(\frac{N-2}{N}l\ket{0}-\frac{2}{N}k\ket{1}\right)\sum_{i \neq i_0} \ket{i}$$

which I think is what we get if we keep track of the ancilla qubit rather than forgetting about it. Note that these are both normalized states.

The reason that I think this ought to matter is that if we measure the state after a Grover iteration, the probability of observing $\ket{i_0}$ would, if I understand partial measurements correctly, be

$$\left(\frac{N-2}{N}k\right)^2 + \left(\frac{2(N-1)}{2}l\right)^2$$

rather than what they have, which is


I assume something I've written above is wrong, but I'm not sure what. Why are we able to forget about this bit in general? Why do we even expect this to yield a normalized state - I know it does here, but why ought it?


1 Answer 1


$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$ I was being silly :)

The sign change that happens is in some sense either associated with the $\ket{a}$ or with the ancilla qubit. By taking the ancilla qubit to be (say) $\left(\frac{\ket{0}-\ket{1}}{\sqrt{2}}\right)$, upon XORing with $f(x)$ we get a sign change that we can stick onto the state qubits and leave the oracle qubits untouched. More formally,

$$\ket{a}\left(\frac{\ket{0}-\ket{1}}{\sqrt{2}}\right) \mapsto \ket{a}\left(\frac{\ket{1}-\ket{0}}{\sqrt{2}}\right) = (-\ket{a})\left(\frac{\ket{0}-\ket{1}}{\sqrt{2}}\right).$$

We can forget about the ancilla qubit because it literally doesn't change and is the same everywhere.


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.