Editing Grover's algorithm (section)

=== Alternative oracle definition ===
This section compares the above oracle <math>U_\omega</math> with an oracle <math>U_f</math>.

''U<sub>ω</sub>'' is different from the standard [[Oracle machine|quantum oracle]] for a function ''f''. This standard oracle, denoted here as ''U<sub>f</sub>'', uses an [[ancilla bit|ancillary qubit]] system. The operation then represents an inversion ([[Quantum gate#Pauli X|NOT gate]]) on the main system conditioned by the value of ''f''(''x'') from the ancillary system:

<math display="block">\begin{cases}
 U_f |x\rang |y\rang = |x\rang |\neg y\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\
 U_f |x\rang |y\rang = |x\rang |y\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0,
\end{cases}</math>

or briefly,

<math display="block">
U_f |x\rang |y\rang = |x\rang |y \oplus f(x)\rang.
</math>

These oracles are typically realized using [[uncomputation]].

If we are given ''U<sub>f</sub>'' as our oracle, then we can also implement ''U<sub>ω</sub>'', since ''U<sub>ω</sub>'' is ''U<sub>f</sub>'' when the ancillary qubit is in the state <math>|-\rang = \frac1{\sqrt2}\big(|0\rang - |1\rang\big) = H|1\rang</math>:

<math display="block">
\begin{align}
U_f \big( |x\rang \otimes |-\rang \big)
&= \frac1{\sqrt2} \left( U_f |x\rang |0\rang - U_f |x\rang |1\rang \right)\\
&= \frac1{\sqrt2} \left(|x\rang |0 \oplus f(x)\rang - |x\rang |1 \oplus f(x)\rang  \right)\\
&= \begin{cases}
 \frac1{\sqrt2} \left(-|x\rang |0\rang + |x\rang |1\rang\right) & \text{if } f(x) = 1, \\
 \frac1{\sqrt2} \left( |x\rang |0\rang - |x\rang |1\rang \right) & \text{if } f(x) = 0
\end{cases} \\
&= (U_\omega |x\rang) \otimes |-\rang
\end{align}
</math>

So, Grover's algorithm can be run regardless of which oracle is given.<ref name=Nielsen-Chuang/> If ''U<sub>f</sub>'' is given, then we must maintain an additional qubit in the state <math>|-\rang</math> and apply ''U<sub>f</sub>'' in place of ''U<sub>ω</sub>''.