Talk:Deutsch–Jozsa algorithm: Difference between revisions

Revision as of 21:44, 8 September 2009

Revision as of 22:12, 8 September 2009

Line 50:

== A more complete explanation of the 2 bit algorithm ==

How about expanding the whole basic 2 bit algorithm out.? It never hurts to explain the same thing more than once; bearing in mind that this is the simplest possible useful quantum computing algorithm, we want to make the article as accessible as possible to people new to the subject. I'm still working on this one:

The starting point is:

<math>{\color{Blue}\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)}\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)</math>

Applying <math>f(x)</math> gives

<math>\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))</math>

Line 61 ⟶ 65:

! Which equals

|-

| <math>f(0)=0, f(1)=0</math>

| Constant

| <math>\frac{1}{2}(|0\rangle(|0\rangle - |1\rangle) + |1\rangle(|0\rangle - |1\rangle))</math>

| <math>{\color{Blue}\frac{1}{2}{\colorsqrt{Blue2}}(|0\rangle + |1\rangle)}\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)</math>

|-

| <math>f(0)=0, f(1)=1</math>

| Balanced

| <math>\frac{1}{2}(|0\rangle(|0\rangle - |1\rangle) + |1\rangle(|1\rangle - |0\rangle))</math>

| <math>{\color{Red}\frac{1}{2}{\colorsqrt{Red2}}(|0\rangle - |1\rangle)}\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)</math>

|-

| <math>f(0)=1, f(1)=0</math>

| Balanced

| <math>\frac{1}{2}(|0\rangle(|1\rangle - |0\rangle) + |1\rangle(|0\rangle - |1\rangle))</math>

| <math>{\color{Red}\frac{1}{2}{\colorsqrt{Red2}}(|0\rangle - |1\rangle)}\frac{1}{\sqrt{2}}(|1\rangle - |0\rangle)</math>

|-

| <math>f(0)=1, f(1)=1</math>

| Constant

| <math>\frac{1}{2}(|0\rangle(|1\rangle - |0\rangle) + |1\rangle(|1\rangle - |0\rangle))</math>

| <math>{\color{Blue}\frac{1}{2}{\colorsqrt{Blue2}}(|0\rangle + |1\rangle)}\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)</math>

|}

=== Constant Functions ===

For the constant functions, the expression for x, the first qubit, remains <math>\frac{1}{2}(|0\rangle + |1\rangle)</math>.

For the constant functions, the expression for x, the first qubit, remains <math>{\color{Blue}\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)}</math>.

This follows logically when we imagine the implementation of the constant f(x) functions. For f(x) = 0, nothing whatsoever needs to be wired into the circuit to implement the function. The value of the y qubit does not change. It is therefore not surprising that the state of qubit x does not change. The same is true of f(x) = 1; the function does not need to make any reference to qubit x.

=== Balanced Functions ===

For the balanced functions, the expression for x is changed to <math>\frac{1}{2}(|0\rangle - |1\rangle)</math> due to interactions between the x and y qubits. *More explanation required here*

For the balanced functions, the expression for x is changed to <math>{\color{Red}\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)}</math> due to interactions between the x and y qubits. *More explanation required here*

=== Hadamard transform of qubit x ===

The key to the algorithm is the final Hadamard transformation on qubit x, which maps the constant functions to <math>|0\rangle</math> and the balanced functions to <math>|1\rangle</math>

The behaviour is described as part of the description of [[Hadamard_transform#Quantum_computing_applications|Hadamard Transform Quantum Gates]].

The key to the algorithm is the final Hadamard transformation on qubit x, which maps the constant functions to <math>|0\rangle</math> and the balanced functions to <math>|1\rangle</math>