Qiskit: How can I modify Grover's algorithm to search for a state that doesn't belong to a basis set?

Let's say I need to find the state $$111$$ in a "database" that is not the computational basis for a 3-qubits system (because it doesn't contain all of the basis vectors or contains the same vector more than one time). For example, this database could be the set $$\{000, 010, 001, 000, 000, 110\}$$.

How can I adjust Grover's algorithm for this kind of search? I would like a Qiskit implementation of this case.

• Could be please a little bit clear? State 111 is not in the database, so it cannot be found. Nov 21 '20 at 7:35
• Yes, I was considering the case where I don't know if the winner state actually is in the database or not. Are you suggesting that Grover's algorithm can't be implemented if I am not sure that the database contains my winner state? Nov 21 '20 at 16:39
• That is really good question. I suppose that resulting state will be equally distributed superpostion as no state is marked and hence there is no change in the phase. But I am not absolutely sure about this... Nov 22 '20 at 6:49

I will quickly reexplain how Grover's Algorithm works :

• First you put your whole system in an equal superposition. The means, for example, with 3 qubits, that your system will be in the state : $$|\psi\rangle = \frac{1}{\sqrt{3}}|000\rangle+\frac{1}{\sqrt{3}}|001\rangle+\cdots+\frac{1}{\sqrt{3}}|110\rangle+\frac{1}{\sqrt{3}}|111\rangle$$. You will assign one of these basis states for each element of your database.
• Then you run the phase-flip oracle gate : $$|U_\omega\rangle$$
• You also run Grover's diffusion operator : $$|U_s\rangle$$
• You repeat the two last steps until the complex amplitude of the state that corresponds to the searched element of your database, has a high enough probability to be measured

As you can see you need at least as many basis states as you have elements in your database, because you assign an element of you database to each basis set. But since you system starts in an equal superposition, every basis state is searchable, as is every element of your database as long as you link a basis state to an element of your database.

However, many different questions mix inside yours, for example, if there is more than one correct element, how does the algorithm work ? I hope I could shed some light on the situation !

• Thank you! I thought that searching for a basis state was just a particular case where the database I need to search is the actual basis set for my n-qubit states. But, as you are saying, it doesn't matter if my database contains bit strings, words, images or whatever because in every scenario I end up assigning each element to a basis set that allows me to use Grover's algorithm. Still one thing I don't understand: what if there's the chance my database does not contain the winner element I am looking for? Is Grover's algorithm useless? Nov 21 '20 at 16:56
• I guess the algorithm will run infinitely, this is why it is always a good idea to set a maximum number of iterations for applying $U_\omega$ and $U_s$ Nov 22 '20 at 15:55

You can use the Quantum Associative Memory algorithm which does not require every element to be present in the database:

There are various improvements over it:

You mentioned, the same element can be present multiple times. This can be taken care by the improvement of Grover search:

You can also use a Quantum Counting (existence) algorithm to search the number of solutions prior to running the Grover search (or the above variants).