Implementing an oracle

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.

• 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$. – Nelimee Mar 17 '19 at 16:28
• Sure @Nelimee, edited. – Karl Mar 17 '19 at 16:33

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$$.