Talk:Deutsch–Jozsa algorithm

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Physics Low‑importance This article is within the scope of WikiProject Physics, a collaborative effort to improve the coverage of Physics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.PhysicsWikipedia:WikiProject PhysicsTemplate:WikiProject Physicsphysics articles Low This article has been rated as Low-importance on the project's importance scale. Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Computing: Software / CompSci Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles Low This article has been rated as Low-importance on the project's importance scale. This article is supported by WikiProject Software (assessed as Low-importance). This article is supported by WikiProject Computer science (assessed as Mid-importance). Things you can help WikiProject Computer science with: edit history watch purge Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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

The text says: "The best case occurs where the function is balanced and the first two output values that happen to be selected are different." Isn't the best case when the function is constant and the two differing values are observed? — Preceding unsigned comment added by Wmagro (talk • contribs) 19:48, 17 January 2020 (UTC)[reply]

If the function is constant, you can't observe different values. 128.250.0.202 (talk) 06:00, 25 August 2022 (UTC)[reply]

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

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

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

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 ${\displaystyle 2^{n}}$. —Preceding unsigned comment added by DavidBoden (talk • contribs) 15:42, 15 August 2009 (UTC)[reply]

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

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: ${\displaystyle {\frac {1}{2^{n}}}|\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|^{2}}$ say f(x) = 1 then the formula evaluates to: ${\displaystyle {\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: ${\displaystyle |{\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)[reply]

I think that the correct formula for the probability should be:
${\displaystyle |{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|^{2}}$
not
${\displaystyle {\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:
${\displaystyle {\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)[reply]

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

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: ${\displaystyle {\color {Blue}{\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}$

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

==== This paragraph is okay, but IMHO it should be after the main algorithm. Otherwise it interrupts the flow of the article. MikeR613 (talk) 19:10, 9 September 2012 (UTC)[reply]

For the constant functions, the expression for x, the first qubit, remains ${\displaystyle {\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.

For the balanced functions, the expression for x is changed to ${\displaystyle {\color {Red}{\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}}$ 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 ${\displaystyle |0\rangle }$ and the balanced functions to ${\displaystyle |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)[reply]

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

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

Agreed. This is just an excellent and interesting algorithm. There is absolutely *no* need to bring up *any* interpretation of QM, especially in such an obfuscating and unilluminating way. 129.97.136.28 (talk) 13:36, 9 August 2011 (UTC)[reply]

I removed two paragraphs from that section. The remainder may still need a bit of work but I don't have an opinion of how to improve it. Skippydo (talk) 22:32, 9 August 2011 (UTC)[reply]

I rewrote the motivation. Is that better? --Robin (talk) 03:01, 23 March 2013 (UTC)[reply]

I think the article should be named after the problem instead of the algorithm. The problem was invented to show a separation and didn't exist before. (Unlike, say, Shor's algorithm for factorization or Grover's algorithm for the search problem.) That also makes the article an appropriate place to discuss classical algorithms and oracle separations that can be proved using this problem. --Robin (talk) 03:05, 23 March 2013 (UTC)[reply]

Am i the only one that i cannot understand the symbolism of the function mentioned on the problem statement section? Please any help apreciated.. Sperxios (talk) 00:15, 23 August 2013 (UTC)[reply]

In layman's terms, the function ${\displaystyle f}$ takes ${\displaystyle n}$-digit binary value as inputs and produces either a ${\displaystyle 0}$ or a ${\displaystyle 1}$ as output for each such value. — Aldaron • T/C 01:04, 23 August 2013 (UTC)[reply]

Thank you Aldaron! I added your description in main page, since i believe that not everybody is aware of this notation. — Preceding unsigned comment added by Sperxios (talk • contribs) 10:39, 25 August 2013 (UTC)[reply]

Especially for the claim regarding conventional randomized algorithms. Where is this being got from? M cuffa (talk) 13:15, 8 February 2014 (UTC)[reply]

Agreed. Where does the "classical solution" section come from? Dr. Universe (talk) 14:56, 30 December 2019 (UTC)[reply]

The actual algorithm for the general n to 1 case is not described, and there are no implementation suggestions or details regarding implementation attempts made in the past. — Preceding Aviv comment added by 87.211.107.83 (talk) 11:28, 30 September 2014 (UTC)[reply]

Circuits that provide a constant output of either ${\displaystyle |0\rangle }$ or ${\displaystyle |1\rangle }$, assuming that the output qubit is initialised to ${\displaystyle |0\rangle }$, can be viewed as having the output qubit disconnected from the input qubits. It is therefore expected that the input qubits measure as ${\displaystyle |0\rangle ^{\otimes n}}$.

Output qubit is constant ${\displaystyle |0\rangle }$	Output qubit is constant ${\displaystyle |1\rangle }$

In the circuit diagrams, the functions are shown within a dashed line border. It is important to note that an ${\displaystyle X}$ gate that flips ${\displaystyle |0\rangle }$ to ${\displaystyle |1\rangle }$ has no effect in the Hadamard basis. ${\displaystyle |+\rangle }$ passes through an ${\displaystyle X}$ gate unchanged.

A sub-class of balanced functions uses only a single input qubit to decide whether the output qubit is ${\displaystyle |0\rangle }$ or ${\displaystyle |1\rangle }$.

Output qubit is the value of one input qubit	Output qubit is the negation of one input qubit

In the Hadamard basis, the ${\displaystyle CNOT}$ gate affects the value of what would be considered the input qubit in the computational basis. In these examples, the input qubits will measure as ${\displaystyle |0\rangle ^{\otimes n-1}|1\rangle }$ due to the connection between the input qubits and the output qubit.

DavidBoden (talk) 20:05, 12 March 2019 (UTC)[reply]

The circuit diagram shows the use of an ancilla bit and computing y + f(x). This complexity is not necessary. The algorithm can be implemented with n hadamard gates before and after a phase oracle and then measure all the outputs. I think we should show this alternative description. The two are equivalent, but it can be easier to understand the second. Jehochman ^Talk 18:11, 15 October 2022 (UTC)[reply]