Talk:Deutsch-Jozsa algorithm

From Wikipedia, the free encyclopedia

This is the talk page for discussing improvements to the Deutsch-Jozsa algorithm article.
Please sign and date your posts by typing four tildes (`~~~~`). Put new text under old text. Click here to start a new topic. New to Wikipedia? Welcome! Ask questions, get answers. This is not a forum for general discussion about the article's subject.	Be polite Assume good faith No personal attacks Be welcoming	Article policies No original research Neutral point of view Verifiability

This article is within the scope of multiple WikiProjects.
Click [show] for further details

WikiProject Physics (Rated Start-Class)
	Portal This article is within the scope of WikiProject Physics, which collaborates on articles related to physics.
Start	This article has been rated as Start-Class on the assessment scale.
Low	This article is on a subject of Low importance within physics.
Help with this template This article has been rated but has no comments. If appropriate, please review the article and leave comments here to identify the strengths and weaknesses of the article and what work it will need.

WikiProject Computing
	This article is within the scope of Computing WikiProject, an attempt to build a comprehensive and detailed guide to computers and computing. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
???	This article has not yet received a rating on the quality scale.
???	This article has not yet received an rating on the importance scale.

WikiProject Computer science (Rated B-Class)
	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B	rated as B-Class on the assessment scale
Mid	rated as mid-importance on the assessment scale

[edit] 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)

[edit] 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)

[edit] 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/PS_cache/quant-ph/pdf/9708/9708016v1.pdf —Preceding unsigned comment added by Ursubaloo (talk • contribs) 16:47, 9 April 2008 (UTC)