How to implement *nested* Grover search (in Quirk)?

Question

$\newcommand{\ket}[1]{|#1 \rangle}$ $\newcommand{\bra}[1]{\langle #1 |}$

PS: I suppose this question could also ask "How to implement $2 \ket{s}\bra{s} - I$ for any (identifiable) $\ket{s} \in \mathcal{H}_A \subset \mathcal{H}$" (in Quirks)?

I am struggling to implement a nested Grover search on gate level, e.g. in quirk (https://algassert.com/quirk). (Essentially, I was following this paper: https://arxiv.org/pdf/quant-ph/9806078.pdf)

Setup

Consider the Hilbert space $\mathcal{H} = \mathcal{H}_A \otimes \mathcal{H}_B$, with $\mathcal{H} = \mathbb{C}^{2^n}$, such that there are $2^n$ elements in $\mathcal{H}$ (respectively $n_A, n_B$ for $\mathcal{H}_A, \mathcal{H}_B$). (Also, sorry for slight abuse of set-formalisms here)

We are given a function $f_A(x) = \begin{cases} 1 \Leftrightarrow x \in \mathcal{H}_A,\\ 0 \text{ otherwise} \end{cases} \qquad$ and $f_a(x) = \begin{cases} 1 \Leftrightarrow x \in M,\\ 0 \text{ otherwise} \end{cases}$

Grover Search

... on any element in $H_A$ performs the following steps:

0. Create uniform superposition: $\ket{\psi_0} = H^{\otimes n'}$
1. Repeat about $\frac{4}{\pi} \sqrt{N/n_A}$ times:
   • Define Circuit $G_A$:
     • Apply oracle: $\ket{\psi_{A,1}} = U_{f_A} \ket{\psi_0}$
     • Apply Diffusion on $\mathcal{H}$: $\ket{\psi_{A, 2}} = 2 \ket{\psi_{A,1}} \bra{\psi_{a,1}} - I$
2. The resulting state is close to $\ket{x} \in \mathcal{H}_A$.

where $2 \ket{\psi_{A,1}} \bra{\psi_{A,1}} - I$ is implemented via: $H^{\otimes n} (I - 2\ket{0}\bra{0}) H^{\otimes n}$

Nested Grover Search

... to find a elements $a \in M \subset\mathcal{H_A}$. ... first creates a superposition over $\mathcal{H}_A$ via a search using the function $f_A$, then searches that subspace via function $f_a$:

1. Create uniform superposition: $\ket{\psi_0} = H^{\otimes n}$
2. Repeat about $\sqrt{n_a/ |M|}$ times:
   • Define Function G_{Aa}
     • Apply $G_A$ about $\frac{4}{\pi} \sqrt{N/n_A}$ times // Now $\ket{\psi_{A, 2}}$ is (close to) a superposition of $\ket{x} \in \mathcal{H}_A$
     • 2. Apply oracle: $\ket{\psi_{a,1}} = U_{f_a} \psi_{A,2}$
     • Apply Diffusion on $\mathcal{H_A}$: $\ket{\psi_{a,2}} = 2 \ket{\psi_{A,2}} \bra{\psi_{A,2}} - I$

where
$2 \ket{\psi_{A,2}} \bra{\psi_{A,2}} - I$ is implemented via: $G_A (I - 2\ket{0}\bra{0}) G_A^{\dagger}$

Simple Instantiation

For simplicity, consider $n=4$ such that the database are the numbers from $0,1,... 15$. Our target values are $M = \{2\}$ ('10'), hence a single element.

• We first identify the number in $a \in \mathcal{H}_A$ with $f_A(x) = 1 \leftrightarrow x \leq 3$. For this particular example $G_A$ has to be applied once to get $\psi_{A,2} = \sqrt{1/4} \sum_{x=0}^{3} \ket{x}$.

• Then we identify $a$ with $f_a(x) = 1 \leftrightarrow x \leq 2$. In theory, a single call to the oracle should be sufficient here too.

Since $\sqrt{\frac{n_a}{|M|}} = 1$ I suppose we would need to iterations of the complete circuit. In my implementation (Quirk Nested Grover); after one step of each '10' clearly has a larger amplitude than the other states, but not close to 100%.

1. What is wrong about my intuition on a nested Grover search?
2. And/ or how do I implement this in Quirk?
3. If this is not a good example, do you know a simple example that can be implemented? (I would prefer an implementation in Quirk, Q# would be okay'ish too ;))

Answer 1

Well, checking again with the paper it seems I simply forgot a pair of Hadamard gates (Correct Quirk Cicruit).