# How to efficiently construct quantum circuits of oracles in multi-target quantum search?

In standard Grover's quantum search with only one target or its extension of multi-target quantum search, one of the two key parts is to quantize the boolean function $$f(x):\{0,1,\cdots,N-1\}\rightarrow \{0,1\}$$, where $$0,1,\cdots,N-1$$ are indices of all $$N$$ candidate elements and the elements with $$f(x)=1$$ are targets we desire to search. The corresponding quantized quantum oracle can be described by $$U_O|x\rangle=(-1)^{f(x)}|x\rangle$$, that is, the phases of target states are flipped but the others are kept unchanged. For simplicity, we assume $$N=2^n$$, so all the $$N$$ indices $$0,1,\cdots,N-1$$ can be represented by $$n$$ bits. For an example with $$N=8$$ and targets being with odd indices 1,3,5,7, $$U_O$$ would act as $$U_O|000\rangle=|000\rangle\\ U_O|001\rangle=-|001\rangle\\ U_O|010\rangle=|010\rangle\\ U_O|011\rangle=-|011\rangle\\ U_O|100\rangle=|100\rangle\\ U_O|101\rangle=-|101\rangle\\ U_O|110\rangle=|110\rangle\\ U_O|111\rangle=-|111\rangle.$$ It is easy to see, without complicated multi-controlled operation, implementing the pauli $$Z$$ operation on the last qubit is sufficient to implement $$U_O$$. However, if targets are with general indices not composing an odd, even, or other special sequence, $$U_O$$ must not be as simple as that involving only one pauli $$Z$$ operation.

So my question is: Is there any efficient quantum circuit to implement $$U_O$$ where the target indices are general and provided beforehand? It would be appreciated as well if someone can provide some clues.

• Check this out, arxiv.org/pdf/1712.01859.pdf this walks you through how to formulate the oracle in terms of phase polynomials and outlines an algorithm for optimizing this circuit. Note the problem is NP-complete. Aug 28, 2021 at 16:44
• But if you don't care about the cost of the oracle implementation, you can just do a CCZ gate whenever you need to inject a negative phase, note that if the input is 001 for example you need to add X gate at the beginning and the end of the control bits. Aug 28, 2021 at 16:51
• @Minh Pham Thanks for providing the clues! Aug 30, 2021 at 5:04