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

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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