Editing Deutsch–Jozsa algorithm (section)

== Deutsch's algorithm==
Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm where n = 1 in <math>f\colon\{0,1\}^n\rightarrow \{0,1\}</math>. We need to check the condition <math>f(0)=f(1)</math>. It is equivalent to check <math>f(0)\oplus f(1)</math> (where <math>\oplus</math> is addition modulo 2, which can also be viewed as a quantum [[XOR gate]] implemented as a [[Controlled NOT gate]]), if zero, then <math>f</math> is constant, otherwise <math>f</math> is not constant.

We begin with the two-qubit state <math>|0\rangle |1\rangle</math> and apply a [[Quantum_logic_gate#Hadamard_gate|Hadamard gate]] to each qubit. This yields
<math display="block">\frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle).</math>

We are given a quantum implementation of the function <math>f</math> that maps <math>|x\rangle |y\rangle</math> to <math>|x\rangle |f(x)\oplus y\rangle</math>. Applying this function to our current state we obtain
<math display="block">\begin{align}
& \frac{1}{2}(|0\rangle(|f(0)\oplus 0\rangle - |f(0)\oplus 1\rangle) + |1\rangle(|f(1)\oplus 0\rangle - |f(1)\oplus 1\rangle)) \\
&=\frac{1}{2}((-1)^{f(0)}|0\rangle(|0\rangle - |1\rangle) + (-1)^{f(1)}|1\rangle(|0\rangle - |1\rangle)) \\
&=(-1)^{f(0)}\frac{1}{2}\left(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle\right)(|0\rangle - |1\rangle).
\end{align}</math>

We ignore the last bit and the global phase and therefore have the state
<math display="block">\frac{1}{\sqrt 2}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle).</math>

Applying a Hadamard gate to this state we have
<math display="block">\begin{align}
&\frac{1}{2} (|0\rangle + |1\rangle + (-1)^{f(0)\oplus f(1)}|0\rangle - (-1)^{f(0)\oplus f(1)}|1\rangle) \\
&=\frac{1}{2} ((1 +(-1)^{f(0)\oplus f(1)}) |0\rangle + (1-(-1)^{f(0)\oplus f(1)}) |1\rangle).
\end{align}</math>

<math>f(0)\oplus f(1) = 0</math> if and only if we measure <math>|0\rangle</math> and <math>f(0)\oplus f(1)=1</math> if and only if we measure <math>|1\rangle</math>. So with certainty we know whether <math>f(x)</math> is constant or balanced.