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)

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: ${\color {Blue}{\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )$ which can also be represented as the vector ${\frac {1}{2}}{\bigl (}{\begin{smallmatrix}1\\-1\\1\\-1\end{smallmatrix}}{\bigr )}$ where each element corresponds to states ${\bigl (}{\begin{smallmatrix}|00\rangle \\|01\rangle \\|10\rangle \\|11\rangle \end{smallmatrix}}{\bigr )}$.

Applying $f(x)$ gives ${\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	Type	Output state	Which equals
$f(0)=0,f(1)=0$	Constant	${\frac {1}{2}}(|0\rangle (|0\rangle -|1\rangle )+|1\rangle (|0\rangle -|1\rangle ))$	${\color {Blue}{\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )$
$f(0)=0,f(1)=1$	Balanced	${\frac {1}{2}}(|0\rangle (|0\rangle -|1\rangle )+|1\rangle (|1\rangle -|0\rangle ))$	${\color {Red}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )$
$f(0)=1,f(1)=0$	Balanced	${\frac {1}{2}}(|0\rangle (|1\rangle -|0\rangle )+|1\rangle (|0\rangle -|1\rangle ))$	${\color {Red}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}{\frac {1}{\sqrt {2}}}(|1\rangle -|0\rangle )$
$f(0)=1,f(1)=1$	Constant	${\frac {1}{2}}(|0\rangle (|1\rangle -|0\rangle )+|1\rangle (|1\rangle -|0\rangle ))$	${\color {Blue}{\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}{\frac {1}{\sqrt {2}}}(|1\rangle -|0\rangle )$

In vector notation this is:

Function	Type	Output vector	Disregard last bit	After hadamard
$f(0)=0,f(1)=0$	Constant	${\frac {1}{2}}{\bigl (}{\begin{smallmatrix}1\\-1\\1\\-1\end{smallmatrix}}{\bigr )}$	${\frac {1}{\sqrt {2}}}{\bigl (}{\begin{smallmatrix}1\\1\end{smallmatrix}}{\bigr )}$	${\bigl (}{\begin{smallmatrix}1\\0\end{smallmatrix}}{\bigr )}$
$f(0)=0,f(1)=1$	Balanced	${\frac {1}{2}}{\bigl (}{\begin{smallmatrix}1\\-1\\-1\\1\end{smallmatrix}}{\bigr )}$	${\frac {1}{\sqrt {2}}}{\bigl (}{\begin{smallmatrix}1\\-1\end{smallmatrix}}{\bigr )}$	${\bigl (}{\begin{smallmatrix}0\\1\end{smallmatrix}}{\bigr )}$
$f(0)=1,f(1)=0$	Balanced	${\frac {1}{2}}{\bigl (}{\begin{smallmatrix}-1\\1\\1\\-1\end{smallmatrix}}{\bigr )}$	${\frac {1}{\sqrt {2}}}{\bigl (}{\begin{smallmatrix}1\\-1\end{smallmatrix}}{\bigr )}$	${\bigl (}{\begin{smallmatrix}0\\1\end{smallmatrix}}{\bigr )}$
$f(0)=1,f(1)=1$	Constant	${\frac {1}{2}}{\bigl (}{\begin{smallmatrix}-1\\1\\-1\\1\end{smallmatrix}}{\bigr )}$	${\frac {1}{\sqrt {2}}}{\bigl (}{\begin{smallmatrix}1\\1\end{smallmatrix}}{\bigr )}$	${\bigl (}{\begin{smallmatrix}1\\0\end{smallmatrix}}{\bigr )}$

Constant Functions

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

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 ${\color {Red}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}$ 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 $|0\rangle$ and the balanced functions to $|1\rangle$

The behaviour is described as part of the description of Hadamard Transform Quantum Gates. DavidBoden (talk)

I agree with your reasoning for including this. You have my blessing to incorporate this. Bender2k14 (talk) 12:50, 14 October 2010 (UTC)

Looks good. I advise against introducing the vector representation, it isn't currently used in the article and I doubt it's needed. Skippydo (talk) 23:48, 20 October 2010 (UTC)

Motivation needs a rewrite

The content of the motivation section appears irrelevant to the algorithm itself. The MWI discussion was particularly frustrating, and distracts from the rest of the article. Can we leave metaphysics out and stick with the mechanics of Deutsch-Jozsa? Much cleanup and explanation might make the section less cognitively jarring. 198.102.153.2 (talk) 23:52, 25 March 2011 (UTC)