Implementing an oracle

Question

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.

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.