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

Question

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.

Answer 1

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{8}}|000\rangle+\frac{1}{\sqrt{8}}|001\rangle+\cdots+\frac{1}{\sqrt{8}}|110\rangle+\frac{1}{\sqrt{8}}|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 !

Answer 2

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

• https://arxiv.org/abs/quant-ph/9807053

There are various improvements over it:

• https://www.sciencedirect.com/science/article/abs/pii/S0020025500000578
• https://link.springer.com/article/10.1007/s10773-012-1237-0

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

• https://arxiv.org/abs/quant-ph/9807027

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).