Implementation of Multi-item Search in Grover's algorithm

Question

I am struggling to understand how exactly a multi-item search in a generic Grover algorithm is implemented. As far as I understand, Grover oracle is specifically designed for each marked item. So it seems only way to implement a multi-item search is to design a different oracle but that would be very slow and inefficient. Is there a way to implement a multi-item search without designing a different oracle for each marked state? A pseudo-code would greatly help.

Answer 1

The oracle used in Grover's search algorithm doesn't have to be designed to mark only a single item, it is designed to mark the item or items for which $f(x) = 1$. For example, you can implement the oracle to look for a bit string 111 among all 3-bit bit strings by using a controlled X gate with all 3 input qubits as controls, but you can also implement the oracle to look for bit strings 110 or 111 by using a controlled X gate with only the first 2 input qubits as controls - this will mark two items instead of one.

More generally, the oracle should evaluate the function $f(x)$ rather than mark specific items individually. In the example of looking for 110 or 111, you're evaluating $f(x) = x_0 \land x_1$ using that controlled X with arguments $x_0$ and $x_1$.