11
$\begingroup$

I am a bit confused about the necessity of an oracle qubit in Grover's algorithm.

My question is, does it depend on how you implement your oracle whether you need an oracle qubit or not? Or, it there any reason for an oracle qubit? (such as, there exist some problems that cannot be solved without an oracle qubit, or it's easier to think about the problem with an oracle qubit, or it's a convention, etc)

Many resources introduce Grover's algorithm with an oracle qubit, but I found there are some cases that you do not need an oracle qubit.

For example, here are two implementations of Grover's algorithm in IBM Q simulator. One is using an oracle qubit, and the other is not. In both cases, I would like to find |11> from a space of |00>, |01>, |10>, and |11>. In both cases, oracle successfully flips |11> to -|11>.

・With an oracle qubit (Link to IBM Q simulator) enter image description here

・Without an oracle qubit (Link to IBM Q simulator) enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

From the perspective of defining the quantum circuit, the oracle qubit is not strictly necessary. For example, in Grover's search, you might normally define the action of the oracle as $$ U|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle, $$ where $f(x)$ returns 1 if $x$ is the marked item. However, we always use this in a particular way, inputting $(|0\rangle-|1\rangle)/\sqrt{2}$ on the oracle qubit. This has the net effect of just implementing a phase on the marked item. In other words, it is entirely equivalent to the implementation of a new unitary $$ \tilde U|x\rangle=(-1)^{f(x)}|x\rangle $$

However, where it makes a difference is the practical reality. Searching for an item, we will actually need some sort of circuit that recognises the marked item, based on the input of $x$. At that point, it's far easier to think about outputting the answer onto the oracle bit, rather than somehow directly building the unitary that gives the phase without using the oracle qubit. Indeed, I suspect if I asked you to design a generic version $\tilde U$, you'd come up with $U$ with the extra qubit as the solution.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It's actually very easy to avoid the extra qubit, assuming it is not used as workspace during the oracle computation. Find any CNOTs onto the extra qubit, and replace them with a Z gate onto the control of the CNOT. Similarly, replace CCNOTs onto the extra qubit with a CZ between the two controls of the CCNOT. Etc. $\endgroup$
    – Craig Gidney
    May 25, 2018 at 22:34
  • $\begingroup$ @CraigGidney It is a fair point, although I think there are more assumptions built into your statement (making it non-generic, even if the majority of cases we know about satisfy them): (1) there should be no intermediate ancillas used during the function evaluation; (2) the oracle's circuit must be decomposed into a gate set where the only multi-qubit gates acting on the oracly qubit are (multi)-controlled-nots that target the oracle qubit; (3) no other gates can act on the oracle qubit (i.e. you cannot just reverse c-nots acting the wrong way by using Hadamards on inputs and outputs). $\endgroup$
    – DaftWullie
    May 26, 2018 at 4:03
  • $\begingroup$ That is correct. $\endgroup$
    – Craig Gidney
    May 28, 2018 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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