7
$\begingroup$

In Chapter 6 of "Quantum Computation and Quantum Information" textbook by Nielsen and Chuang, Exercise 6.5 p.255:

We have an oracle gate $O$ for $n$ qubit ($2^n=N$ searching items), and we would like to construct new oracle gate $O'$ for $n+1$ qubit ($2^{n+1}=2N$ searching items) using oracle gate $O$ and extra bit $|q\rangle$ so that new oracle gate $O'$ should mark an item only if it is solution for the oracle gate $O$ and extra bit $|q\rangle$ is $|0\rangle$.

The exact question in the Nielsen and Chuang textbook as follows:

A new augmented oracle $O'$ is constructed which marks an item only if it is a solution to the search problem and the extra bit is set to zero.

Exercise 6.5: Show that the augmented oracle $O'$ may be constructed using one application of $O$, and elementary quantum gates, using the extra qubit $|q\rangle$.

Possible not very good solutions:

enter image description here

The problem with this solution is related to the fact that it requires to open up an Oracle gate $O$ in order to "control" it.

Does anybody have an idea of how to construct gate $O'$ using "pure" gate $O$ without "open up" them?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
10
$\begingroup$

The simplest solution is to use an ancilla in the $|+\rangle$ state. Swap that ancilla for the oracle's output qubit, conditioned on the control qubit being false, before and after applying the oracle. Since toggling the $|+\rangle$ state has no effect, this deactivates the oracle when the control is set.

Here's this technique applied to a simple comparison oracle:

ancilla solution

If you're not allowed to use an ancilla, I'm not sure how to make it work unless you have access to the square root of the oracle. The best I know how to do is to have the controlled oracle bitflip and phaseflip the target. Or to bitflip the target but have a 90 degree phase kickback onto the control for satisfying inputs.

bit flip and phase flip

bit flip and kickback

Summary Update - simple solution with ancilla enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your explanation, your ideas push me to the following solution (i put it in the answer). It looks quite simple. $\endgroup$
    – Alexey Krugovets
    Dec 25, 2019 at 13:36
  • 1
    $\begingroup$ So, we actually can control an unknown black box if it just permutes a known basis. Nice. $\endgroup$
    – Danylo Y
    Dec 25, 2019 at 15:53
  • $\begingroup$ i add summary scheme with ancilla to your answer $\endgroup$
    – Alexey Krugovets
    Dec 25, 2019 at 20:03
3
$\begingroup$

Ancilla-free solution: replace the two controlled-SWAPs in the "summary update" of Craig Gidney's solution with controlled-$Z$s between the second and fourth qubits in the diagram, and remove the third qubit.

(That is, instead of swapping $|-\rangle$ with a $|+\rangle$ state stored in the second register, conditioned on $|q\rangle$ being set to 1, conditionally change $|-\rangle$ to $|+\rangle$ directly using controlled-$Z$.)

Improve this answer
$\endgroup$
0
$\begingroup$

After some ideas of @Craig Gidney probably i found the following simple solution: enter image description here

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ This solution is not correct. It leaves the |x> register entangled with the ancilla qubit. You need to uncompute the ancilla qubit. $\endgroup$
    – Craig Gidney
    Dec 25, 2019 at 13:58
  • $\begingroup$ by "ancilla qubit" - you mean second cubit $|0\rangle$? What do you mean by "uncompute"? If $|x\rangle$ - the searching item (solution) and $|q\rangle$=$|0\rangle$, then $O'$$|x\rangle|0_q\rangle = -|x\rangle|0_q\rangle$. If If $|x\rangle$ - the searching item (solution) and $|q\rangle$=$|1\rangle$, then $O'$$|x\rangle|1_q\rangle = |x\rangle|1_q\rangle$. If $|x\rangle$ is not the searching item and $|q\rangle$=$|0\rangle$ or $|1\rangle$ , then $O'$$|x\rangle|0_q\rangle = |x\rangle|0_q\rangle$ or $O'$$|x\rangle|1_q\rangle = |x\rangle|1_q\rangle$. $\endgroup$
    – Alexey Krugovets
    Dec 25, 2019 at 16:16
  • $\begingroup$ Why you think that entangling between $|x\rangle$ and ancillary is a bed practice? In order to uncompute ancilla qubit i need to use oracle $O$ second time that is not good. $\endgroup$
    – Alexey Krugovets
    Dec 25, 2019 at 16:28
  • 2
    $\begingroup$ It's bad practice because it doesn't maintain coherence. If you try to use this implementation of the oracle within Grover's algorithm, the algorithm will fail. You're leaking information into the ancilla. $\endgroup$
    – Craig Gidney
    Dec 25, 2019 at 17:19
0
$\begingroup$

I don't think it's possible. I think that was the authors idea - to apply controlled $O$ (despite the fact it's impossible to control black boxed unitaries https://arxiv.org/abs/1309.7976)

Update

As Craig Gidney answer suggests, we actually can control unknown black boxes if they just permute a known basis. Though we need to use an ancilla.

Improve this answer
$\endgroup$

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.