Slight modification of Grover's algorithm

Question

Let $S$ be a set $\{| j ⟩~|~j = 0, 1, · · · ,N − 1\}$ with assuming $⟨j_i|j_j⟩ = δ_{ij}$. Thus, total number of quantum states in $S$ is $N$. Usual Grover’s algorithm is to find a state $|w⟩ \in S$ with $\sqrt{N}$ queries. This means that the oracle and diffuser should be repeated approximately $\sqrt{N}$ times.

Now, I want to change a situation slightly. Let us assume that the number of $|j⟩$ in $S$ is $α_j$. Thus, total number of quantum states in $S$ is $\tilde{N} = \sum_{j=0}^{N-1} α_j$. Of course, the number of the state $|w⟩ \in S$ is $α_w$. I want to find the value of $α_w$ and all $|w⟩$ quantum state efficiently by modifying the Grover’s algorithm. Is it possible? We assume that the total number of states $\tilde{N}$ is known, but $α_j$ is unknown.

Answer 1

Grover's algorithm can find the answer in your situation without any modification. But, you have to formulate your situation more precisely.

First, your notations and terminologies suggest you are finding a 'state' among possible 'quantum states' $\newcommand{\ket}[1]{\left|{#1}\right\rangle}\ket{0}, \dots, \ket{N-1}$, but with possible duplication. Of course, if two quantum states are identical, then they are, well, identical: there cannot be any duplicates.

It is better to imagine Grover's algorithm as working with a classical logical predicate $P$: given some index $i$, $P(i)=1$ or $P(i)=0$. What Grover's algorithm is doing is to find some $i$ satisfying $P(i)=1$, when $P$ is given as an oracle.

Of course, you can define/implement this predicate in many different ways and hence use Grover's algorithm in different contexts. One way would be 'database search': you are given a database of $N$ items: $D(i)$ is the entry stored at the $i$th position. Now, you want to find a particular $y$. Rather, you want to find an index $i$ satisfying $D(i)=y$. This can be done by defining the predicate $P$ as $P(i)=[D(i)=y]$; in other words, $P(i)=1$ iff $D(i)=y$, and $P(i)=0$ iff $D(i)\neq y$.

In this scenario, Grover's algorithm does not say anything about uniqueness of items $D(0), \dots, D(N-1)$: it works without any restriction on uniqueness. In fact, Grover's algorithm only makes oracle queries to the predicate $P$; it does not care how this $P$ is implemented, or whether there is a database behind the implementation of $P$, with duplicates or not.

So, in short, if you think about your situation and formulate it more precisely, then Grover's algorithm works without any modification.