Suppose $x$ is an $N=2^n$ elements database. Let's define a $2N$-bit database with $y \in \{0,1\}^{2N}$ indexed by $(n+1)$-bit strings $j=j_1\ldots j_n j_{n+1}$, where \begin{align} y_j=\begin{cases}1 & \text{if }x_{j_1 \ldots j_n}=1 \text{ and } j_{n+1}=0 \\ 0 & \text{otherwise} \end{cases} \end{align}

How can one implement the oracle $|j \rangle \rightarrow (-1)^{y_j} |j\rangle$ using one query to the $x$ oracle $O_x: |i,b \rangle \rightarrow |i, b\oplus x_i \rangle $ and some elementary gates?

Edit: Basically what would do the job on a high level would be to check if the the result of $O_x$ was 1 or 0. If it was 1 a controlled gate on $j_{n+1}$ that flips everything again if $j_{n+1}$ is 1 and do nothing otherwise, if it was 0 do nothing. At least this is my intuition but I cannot formalize it.

  • 1
    $\begingroup$ I'm not sure you want a $2^n$ bits database (i.e. with $2^{2^n}$ elements!). You also probably have a typo in the definition of $y$. $\endgroup$ Mar 17, 2019 at 16:28
  • $\begingroup$ Sure @Nelimee, edited. $\endgroup$
    – Karl
    Mar 17, 2019 at 16:33

1 Answer 1


You can implement a multiple controlled $\operatorname{Z}$ gate on $n+1$ qubits together with two $\operatorname{X}$-gates on the $n+1$-th qubit before and after the multiple controlled gate.

This gate can be made by constructing a multiple controlled $\operatorname{NOT}$ gate, that is a $C^n\operatorname{NOT}$ gate, and on the $n+1$-th qubit a $\operatorname{H}$-gate before and after the multiple controlled $\operatorname{NOT}$-gate.

The $\operatorname{X}$ gate before and after the multiple controlled gate make sure that the state is flipped for $j_{n+1}=0$ instead of for $j_{n+1}=1$.

Simple evaluation of the matrices shows that this works as desired.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.