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.

  • $\begingroup$ 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. $\endgroup$
    – Minh Pham
    Aug 28, 2021 at 16:44
  • $\begingroup$ 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. $\endgroup$
    – Minh Pham
    Aug 28, 2021 at 16:51
  • 1
    $\begingroup$ @Minh Pham Thanks for providing the clues! $\endgroup$ Aug 30, 2021 at 5:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.