Editing Grover's algorithm (section)

== Problem description ==
As input for Grover's algorithm, suppose we have a function <math>f\colon \{0,1,\ldots,N-1\} \to \{0,1\}</math>. In the "unstructured database" analogy, the domain represent indices to a database, and {{nowrap|1=''f''(''x'') = 1}} if and only if the data that ''x'' points to satisfies the search criterion. We additionally assume that only one index satisfies {{nowrap|1=''f''(''x'') = 1}}, and we call this index ''ω''. Our goal is to identify ''ω''.

We can access ''f'' with a [[subroutine]] (sometimes called an [[Oracle machine|oracle]]) in the form of a [[unitary operator]] ''U<sub>ω</sub>'' that acts as follows:

<math display="block">\begin{cases}
 U_\omega |x\rang = -|x\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\
 U_\omega |x\rang = |x\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0.
\end{cases}</math><!-- Explanation of bar/pipe notation required. -->

This uses the <math>N</math>-dimensional [[mathematical formulation of quantum mechanics|state space]] <math>\mathcal{H}</math>, which is supplied by a [[quantum register|register]] with <math>n = \lceil \log_{2} N \rceil</math> [[qubit]]s.
This is often written as

<math display="block">U_\omega|x\rang = (-1)^{f(x)}|x\rang.</math>

Grover's algorithm outputs ''ω'' with probability at least ''1/2'' using <math>O(\sqrt{N})</math> applications of ''U<sub>ω</sub>''. This probability can be made arbitrarily large by running Grover's algorithm multiple times. If one runs Grover's algorithm until ''ω'' is found, the [[Expected value|expected]] number of applications is still <math>O(\sqrt{N})</math>, since it will only be run twice on average.

=== 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>''.