# Nielsen and Chuang, Exercise 6.5: How to simulate oracle for n+1 qubits using one oracle gate for n qubits and one extra qubit?

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: 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?

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: 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.  Summary Update - simple solution with ancilla • Thank you for your explanation, your ideas push me to the following solution (i put it in the answer). It looks quite simple. Dec 25, 2019 at 13:36
• So, we actually can control an unknown black box if it just permutes a known basis. Nice. Dec 25, 2019 at 15:53

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

After some ideas of @Craig Gidney probably i found the following simple solution: • This solution is not correct. It leaves the |x> register entangled with the ancilla qubit. You need to uncompute the ancilla qubit. Dec 25, 2019 at 13:58
• 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$. Dec 25, 2019 at 16:16
• 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. Dec 25, 2019 at 16:28
• 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. Dec 25, 2019 at 17:19

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.