Editing Deutsch–Jozsa algorithm (section)

== Algorithm ==

For the Deutsch–Jozsa algorithm to work, the oracle computing <math>f(x)</math> from <math>x</math> must be a quantum oracle which does not [[Quantum decoherence|decohere]] <math>x</math>. In its computation, it cannot make a copy of <math>x</math>, because that would violate the [[no cloning theorem]]. The point of view of the Deutsch-Jozsa algorithm of <math>f</math> as an oracle means that it does not matter what the oracle does, since it just has to perform its promised transformation.

[[Image:Deutsch-Jozsa-algorithm-quantum-circuit.png|thumb|400px|right|Deutsch-Jozsa algorithm [[quantum circuit]]]]

The algorithm begins with the <math>n+1</math> bit state <math>|0\rangle^{\otimes n} |1\rangle </math>. That is, the first n bits are each in the state <math>|0\rangle </math> and the final bit is <math>|1\rangle </math>. A [[Quantum_logic_gate#Hadamard_gate|Hadamard gate]] is applied to each bit to obtain the state

<math display="block">\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle ),</math>

where <math>x</math> runs over all <math>n</math>-bit strings, which each may be represented by a number from <math>0</math> to <math>2^n - 1</math>. We have the function <math>f</math> implemented as a quantum oracle. The oracle maps its input state <math> |x\rangle|y\rangle </math> to <math> |x\rangle|y\oplus f(x) \rangle </math>, where <math>\oplus</math> denotes addition modulo 2. Applying the quantum oracle gives;

<math display="block">\frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^n-1} |x\rangle (|0\oplus f(x)\rangle - |1\oplus f(x)\rangle ).</math>

For each <math>x, f(x)</math> is either 0 or 1. Testing these two possibilities, we see the above state is equal to

<math display="block">\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle ).</math>

At this point the last qubit <math>\frac{|0\rangle - |1\rangle}{\sqrt{2}}</math> may be ignored and the following remains:

<math display="block">\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle.</math>

Next, we will have each qubit go through a [[Quantum logic gate#Hadamard gate|Hadamard gate]]. The total transformation over all <math>n</math> qubits can be expressed with the following identity:

<math display="block">H^{\otimes n} |k\rangle = \frac{1}{\sqrt{2^n}} \sum_{j = 0}^{2^n - 1} (-1)^{k \cdot j} |j\rangle</math>

(<math>j\cdot k = j_0 k_0\oplus j_1 k_1\oplus\cdots\oplus j_{n-1} k_{n-1} </math> is the sum of the bitwise product). This results in

<math display="block">\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1}(-1)^{f(x)} \left[ \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} {\left(-1\right)}^{x\cdot y}  |y\rangle \right] =
\sum_{y=0}^{2^n-1} \left[ \frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)} (-1)^{x\cdot y}\right] |y\rangle .</math>

From this, we can see that the probability for a state <math>k</math> to be measured is

<math display="block">\left|\frac{1}{2^n} \sum_{x=0}^{2^n-1} {\left(-1\right)}^{f(x)} {\left(-1\right)}^{x \cdot k} \right|^2</math>

The probability of measuring <math>k = 0 </math>, corresponding to <math>|0\rangle^{\otimes n}</math>, is

<math display="block">\bigg|\frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\bigg|^2</math>

which evaluates to 1 if <math>f(x)</math> is constant ([[constructive interference]]) and 0 if <math>f(x)</math> is balanced ([[destructive interference]]). In other words, the final measurement will be <math>|0\rangle^{\otimes n}</math> (all zeros) if and only if <math>f(x)</math> is constant and will yield some other state if <math>f(x)</math> is balanced.