# Slight modification of Grover's algorithm

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.

## 1 Answer

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.