TransWikia.com

Why can we forget about the ancilla bit in Grover's algorithm?

Quantum Computing Asked on March 26, 2021

$defbraket#1#2{langle#1|#2rangle}defbra#1{langle#1|}defket#1{|#1rangle}$
When using Grover’s algorithm to invert a function $fcolon {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

$$kket{i_0}+lsum_{i neq i_0} ket{i}$$
to
$$left(frac{N-2}{N}k+frac{2(N-1)}{2}lright)ket{i_0} + left(frac{N-2}{N}l-frac{2}{N}kright)sum_{i neq i_0} ket{i} $$

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

$$left(frac{N-2}{N}kket{1}+frac{2(N-1)}{2}lket{0}right)ket{i_0} + left(frac{N-2}{N}lket{0}-frac{2}{N}kket{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}kright)^2 + left(frac{2(N-1)}{2}lright)^2$$

rather than what they have, which is

$$left(frac{N-2}{N}k+frac{2(N-1)}{2}lright)^2.$$

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?

One Answer

$defbraket#1#2{langle#1|#2rangle}defbra#1{langle#1|}defket#1{|#1rangle}$ 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.

Correct answer by bean on March 26, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP