$\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:
- Create uniform superposition: $\ket{\psi_0} = H^{\otimes n'}$
- 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$
- Define Circuit $G_A$:
- 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$:
- Create uniform superposition: $\ket{\psi_0} = H^{\otimes n}$
- 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$
-
- 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$
- Define Function G_{Aa}
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%.
- What is wrong about my intuition on a nested Grover search?
- And/ or how do I implement this in Quirk?
- 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 ;))