Amplitude amplification with or without ancilla state

Question

I am trying to understand amplitude amplification and I am able to find two formulations (almost identical).

(A) No ancilla

Usually, and what I do understand quite well, is that you start with the equal superposition state $$ |\psi_0\rangle = \frac{1}{\sqrt{N}}\sum_i |i\rangle $$ or otherwise by projecting to the "marked" subspace (say its only one state) $|m\rangle$ and its orthogonal completion $|k\rangle$ such that $\langle k | m \rangle = 0$, \begin{align} |\psi_0\rangle &= \frac{\sqrt{N}-1}{\sqrt{N}}|k\rangle + \frac{1}{\sqrt{N}}|m\rangle \\ &= \cos(\phi/2)|k\rangle + \sin(\phi/2)|m\rangle \end{align}

and then you apply two projections, the "oracle" encoding the Boolean function that does the phase inversion: $$ U_f = (\mathbb{1}-2|m\rangle\langle m|) $$ followed by the diffusion operator that projects back onto $|\psi_0\rangle$ and reads $$ V = (2|\psi_0\rangle \langle \psi_0|-\mathbb{1}). $$ The resulting state after $d$ iterations is $(VU_f)^d|\psi_0\rangle$ and it has achieved to amplify the amplitude of the state essentially by projecting it onto $|m\rangle$.

(B) With ancilla

However, in a very similar construction (see this paper for example) I read that one can directly start with the state in $n+1$ qubits (before we only had $n$) \begin{align} |\psi_0\rangle &= \mathcal{A}|0\rangle^n|0\rangle \\ &=\cos(\phi)|k\rangle\otimes|0\rangle + \sin(\phi)|m\rangle \otimes|1\rangle \\ &=\cos(\phi)|k\rangle |0\rangle + \sin(\phi)|m\rangle |1\rangle \end{align} (not sure why the angle discrepancy!) for some operator $\mathcal{A}$ that does the job of projecting into the $\{|k\rangle, |m\rangle \}$ space, and then apply $$ Q = \mathcal{A}S_0 \mathcal{A}^{-1}S_\chi $$ where $S_0 = (\mathbb{1}-2|0\rangle^{n+1}\langle 0|^{n+1})$ and $S_\chi= (\mathbb{1}^{\otimes n} \otimes Z)$. It is clear that $Z$ acting on the last qubit it will change its sign (sends $|0\rangle \to |0\rangle$ and $|1\rangle$ to $-|1\rangle$). Thus, we start from \begin{align} |\psi_0 \rangle = \cos(\phi)|k\rangle |0\rangle + \sin(\phi) |m\rangle |1\rangle \end{align} and applying $S_\chi$ changes is this to \begin{align} |\psi_0 \rangle = \cos(\phi)|k\rangle |0\rangle -\sin(\phi) |m\rangle |1\rangle \end{align} Then applying $\mathcal{A}^{-1}$ takes this back to (what???) and finally $S_0$ it projects this onto $|m\rangle$.

Overall we have $$ Q^d|\psi_0\rangle = \cos((2m+1)\phi)|k\rangle + \sin((2m+1)\phi)|m\rangle $$ which amplifies a lot the second summand.

---

Both (A) and (B) do the same. So the question is what is the difference really? Especially for (B) I do not see how the operator $\mathcal{A}^{-1}$ is applied.

Why do we need the extra ancilla state if the former approach does the same job?

Answer 1

The first formalism is more abstract/generic. You are saying which overall operations must be performed on the input states, but you are not really saying how you would go in implementing such operations as sequences of elementary gates.

In the second case, you are instead also providing a somewhat more explicit way to implement the operations. Note that $S_0,S_\chi$ do not depend on the specific task at hand, so however you write them as a sequence of gates, that will not need to change changing target states etc. You can think of that writing of $Q$ as a way to offload the dependence on the target $|m\rangle$ into the operator $\mathcal A$.

Note that $Q$ can also be written as $$Q=\mathcal AS_0 \mathcal A^{-1}S_\chi = \underbrace{(I - 2|\psi_0\rangle\!\langle\psi_0|)}_{=\mathcal AS_0 \mathcal A^{-1}} \underbrace{(I\otimes Z)}_{=S_\chi}, $$ and that $S_\chi$ acts on $|\psi_0\rangle$ in kind of the same way as $I-2|m\rangle\!\langle m|$, flipping the sign of the term with $|m\rangle$. So $S_\chi$ makes it easier to implement this sign flip in practice, making it into a local operation easy to implement, and this is made possible by the use of an ancillary qubit.

In other words, the second method introduces an ancillary qubit in order to simplify the implementation of some of the necessary operations.