Talk:Deutsch–Jozsa algorithm: Difference between revisions

Revision as of 07:42, 8 September 2009

Revision as of 21:44, 8 September 2009

Line 48:

:Fixed! [[User:Skippydo|Skippydo]] ([[User talk:Skippydo|talk]]) 23:19, 9 April 2008 (UTC)

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

== Complete ==

How about expanding the whole basic 2 bit algorithm out. It never hurts to explain the same thing twicemore 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:

<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 57:

|-

! Function

! Type

! Output state

! Which equals <math>\frac{1}{2}</math>

! Which equals <math>\frac{1}{2}</math>

|-

| f(0)=0, f(1)=0

| Constant

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

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

| <math>|00\rangle - |01\rangle + |10\rangle - |11\rangle</math>

|-

| f(0)=0, f(1)=1

| Balanced

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

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

| <math>|00\rangle - |01\rangle - |10\rangle + |11\rangle</math>

|-

| f(0)=1, f(1)=0

| Balanced

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

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

| <math>- |00\rangle + |01\rangle + |10\rangle - |11\rangle</math>

|-

| f(0)=1, f(1)=1

| Constant

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

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

| <math>- |00\rangle + |01\rangle - |10\rangle + |11\rangle</math>

|}

For the constant functions, the expression for x, the first qubit, remains <math>\frac{1}{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.

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*

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>