# 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. – Alex Dec 25 '19 at 13:36
• So, we actually can control an unknown black box if it just permutes a known basis. Nice. – Danylo Y Dec 25 '19 at 15:53
• i add summary scheme with ancilla to your answer – Alex Dec 25 '19 at 20:03

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. – Craig Gidney Dec 25 '19 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$. – Alex Dec 25 '19 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. – Alex Dec 25 '19 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. – Craig Gidney Dec 25 '19 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.