Talk:Deutsch–Jozsa algorithm

corrected mistake

I found a small mistake in the description of the algorithm, and I corrected it. To me, the wording of the article is still a bit sloppy; but I'm not going to try to fix it at the moment. At least now the algorithm works. :) Karadoc** 05:27, 3 July 2006 (UTC)

What the...?

In section History, it is claimed that the original Deutsch algorithm was meant to solve the n=1 case only, and, furthermore, it was randomized, having only a 1/2 probability of successfully recognizing the input function as either constant or not. Well, i don't need a quantum computer for that... Simply toss a coin. If it comes up heads, claim 'constant'; 'non-constant' if tails. Or the other way around. You get the idea: Something must be amiss here. —Preceding unsigned comment added by 89.152.248.155 (talk) 04:02, 10 March 2008 (UTC)

As I recall, the algorithm would return yes, no or fail (failed with prob 1/2). The gain over a coin flip was that the algorithm guaranteed confidence in the result. That is, a yes answer from the algorithm means it really was constant. Skippydo (talk) 07:45, 23 March 2008 (UTC)

In the original algorithm, which result can we be confident in? Is it when we find that the function is *constant* we're sure it's correct and can stop trying or is it when we find that the function is *balanced* that we're sure it's correct and can stop trying? We should include this in the text. The author of this question is right, it currently sounds like the original algorithm didn't tell us much! :o) --DavidBoden (talk) 13:59, 20 January 2009 (UTC)

Consider changing to this? The original algorithm was successful in detecting a constant function with a probability of one half and did not falsely indicate that a function was constant when it was balanced. Applying the function n times and having it indicate balanced every time increases confidence that the function is in fact balanced in the order of $2^{n}$. —Preceding unsigned comment added by DavidBoden (talk • contribs) 15:42, 15 August 2009 (UTC)

From what I understand from Scott Aaronson's blog, Skippydo's interpretation seems correct. Possibly the algorithm outputs 2 bits, one which indicates whether the algorithm has failed or succeeded, and the second bit tells you whether it is constant or not in the case that it has succeeded. --Robin (talk) 19:49, 17 August 2009 (UTC)

problem with the formula for the probability of measuring ket 0

The formula that is given for measuring ket 0 does not make sense. Take the case that f(x) is balanced. The current formula is: ${\frac {1}{2^{n}}}|\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|^{2}$ say f(x) = 1 then the formula evaluates to: ${\frac {1}{2^{n}}}|{2^{n}}|^{2}={\frac {1}{2^{n}}}{2^{2n}}={2^{n}}$ this is not equal to 1 as is claimed in the article, so there is an error in the formula
the correct formula should be: $|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|^{2}$

Good catch, the square was the typo. Fixed! Skippydo (talk) 23:41, 8 April 2008 (UTC)

I think that the correct formula for the probability should be:
$|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|^{2}$
not
${\frac {1}{2^{n}}}|\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|$
The following article mentions the Deutsch-Jozsa Algorithm and it says that the amplitude of ket(0) is:
${\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}$
And the probability is the square of the amplitude.
http://arxiv.org/abs/quant-ph/9708016v1 —Preceding unsigned comment added by Ursubaloo (talk • contribs) 16:47, 9 April 2008 (UTC)

Fixed! Skippydo (talk) 23:19, 9 April 2008 (UTC)

Complete

How about expanding the whole basic 2 bit algorithm out. It never hurts to explain the same thing twice I'm still working on this one:

${\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 ))$

Function	Output state	Which equals ${\frac {1}{2}}$	Which equals ${\frac {1}{2}}$
f(0)=0, f(1)=0	${\frac {1}{2}}(|0\rangle (|0\rangle -|1\rangle )+|1\rangle (|0\rangle -|1\rangle ))$	$(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )$	$|00\rangle -|01\rangle +|10\rangle -|11\rangle$
f(0)=0, f(1)=1	${\frac {1}{2}}(|0\rangle (|0\rangle -|1\rangle )+|1\rangle (|1\rangle -|0\rangle ))$	$(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )$	$|00\rangle -|01\rangle -|10\rangle +|11\rangle$
f(0)=1, f(1)=0	${\frac {1}{2}}(|0\rangle (|1\rangle -|0\rangle )+|1\rangle (|0\rangle -|1\rangle ))$	$(|0\rangle -|1\rangle )(|1\rangle -|0\rangle )$	$-|00\rangle +|01\rangle +|10\rangle -|11\rangle$
f(0)=1, f(1)=1	${\frac {1}{2}}(|0\rangle (|1\rangle -|0\rangle )+|1\rangle (|1\rangle -|0\rangle ))$	$(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )$	$-|00\rangle +|01\rangle -|10\rangle +|11\rangle$