1
$\begingroup$

$\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:

  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 ;))
$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.