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

$$\newcommand{\ket}{|#1 \rangle}$$ $$\newcommand{\bra}{\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:

1. Create uniform superposition: $$\ket{\psi_0} = H^{\otimes n'}$$
2. 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$$
3. 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$$
1. 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 ;))