This article is ratedC-class on Wikipedia'scontent assessment scale. It is of interest to the followingWikiProjects:

PhysicsLow‑importance This article is within the scope ofWikiProject Physics, a collaborative effort to improve the coverage ofPhysics on Wikipedia. If you would like to participate, please visit the project page, where you can jointhe discussion and see a list of open tasks.PhysicsWikipedia:WikiProject PhysicsTemplate:WikiProject Physicsphysics Low This article has been rated asLow-importance on theproject's importance scale. Computer scienceMid‑importance This article is within the scope ofWikiProject Computer science, a collaborative effort to improve the coverage ofComputer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can jointhe discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Mid This article has been rated asMid-importance on theproject's importance scale. Things you can helpWikiProject 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 (seeList of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles inCategory:Computer science and sub-categories with{{WikiProject Computer science}} Computing:Software /CompSciLow‑importance This article is within the scope ofWikiProject Computing, a collaborative effort to improve the coverage ofcomputers,computing, andinformation technology on Wikipedia. If you would like to participate, please visit the project page, where you can jointhe discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing Low This article has been rated asLow-importance on theproject's importance scale. This article is supported byWikiProject Software (assessed asLow-importance). This article is supported byWikiProject Computer science (assessed asMid-importance). Things you can helpWikiProject 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 (seeList of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles inCategory: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?— Precedingunsigned comment added byWmagro (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.—Precedingunsigned comment added by89.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}$.—Precedingunsigned comment added byDavidBoden (talk •contribs)15:42, 15 August 2009 (UTC)[reply]

From what I understand fromScott 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) = 1then 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—Precedingunsigned comment added byUrsubaloo (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 \frac{1}{\sqrt{2}}(|0⟩+|1⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)}$

Applying${\displaystyle f(x)}$ gives${\displaystyle \frac{1}{2}(|0⟩(|f(0)\oplus 0⟩-|f(0)\oplus 1⟩)+|1⟩(|f(1)\oplus 0⟩-|f(1)\oplus 1⟩))}$

Function	Type	Output state	Which equals
${\displaystyle f(0)=0,f(1)=0}$	Constant	${\displaystyle \frac{1}{2}(|0⟩(|0⟩-|1⟩)+|1⟩(|0⟩-|1⟩))}$	${\displaystyle \frac{1}{\sqrt{2}}(|0⟩+|1⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)}$
${\displaystyle f(0)=0,f(1)=1}$	Balanced	${\displaystyle \frac{1}{2}(|0⟩(|0⟩-|1⟩)+|1⟩(|1⟩-|0⟩))}$	${\displaystyle \frac{1}{\sqrt{2}}(|0⟩-|1⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)}$
${\displaystyle f(0)=1,f(1)=0}$	Balanced	${\displaystyle \frac{1}{2}(|0⟩(|1⟩-|0⟩)+|1⟩(|0⟩-|1⟩))}$	${\displaystyle \frac{1}{\sqrt{2}}(|0⟩-|1⟩)\frac{1}{\sqrt{2}}(|1⟩-|0⟩)}$
${\displaystyle f(0)=1,f(1)=1}$	Constant	${\displaystyle \frac{1}{2}(|0⟩(|1⟩-|0⟩)+|1⟩(|1⟩-|0⟩))}$	${\displaystyle \frac{1}{\sqrt{2}}(|0⟩+|1⟩)\frac{1}{\sqrt{2}}(|1⟩-|0⟩)}$

==== 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 \frac{1}{\sqrt{2}}(|0⟩+|1⟩)}$.

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

The behaviour is described as part of the description ofHadamard 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/C01: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.— Precedingunsigned comment added bySperxios (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.— PrecedingAviv comment added by87.211.107.83 (talk)11:28, 30 September 2014 (UTC)[reply]

Circuits that provide a constant output of either${\displaystyle |0⟩}$ or${\displaystyle |1⟩}$, assuming that the output qubit is initialised to${\displaystyle |0⟩}$, 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{⟩}^{\otimes n}}$.

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

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⟩}$ to${\displaystyle |1⟩}$ has no effect in the Hadamard basis.${\displaystyle |+⟩}$ 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⟩}$ or${\displaystyle |1⟩}$.

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{⟩}^{\otimes n-1}|1⟩}$ 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 aphase 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^Talk18:11, 15 October 2022 (UTC)[reply]

I received feedback on other Qiskit code examples that I recently added, mainly that the code was too long and over-explained. I shortened the code example in this article, and made the explanation more concise.JavaFXpert (talk)19:48, 18 February 2025 (UTC)[reply]

thanks for engaging here; I still find this too long not suitable for an encyclopedia. In my view, this does not explain the Deutsch-Jozsa algorithm but how to program it in Qiskit, which is not the task of the WP article, but of a textbook on Qiskit.

Moreover, even assuming there is a consensus to include the code, it should be backed up byWP:reliable sources. I don't think code of this length written by yourself is appropriate for Wikipedia. Even for calculations the rule is "only routine calculations (like adding numbers), so I don't think writing whole programs is ok without providing a source. --Qcomp (talk)20:44, 18 February 2025 (UTC)[reply]

Thanks. I made modifications that I trust are acceptable.JavaFXpert (talk)00:14, 20 February 2025 (UTC)[reply]

I'm having trouble calling the solution to the Deutsch-Josza problem an 'algorithm.' To me, it sounds more like a physical procedure. The problem it solves is not really a computational problem but rather a physical one—characterizing an oracle, which is even required to come in a specific physical form. If one widens the definition of algorithm to just a sequence of operations, almost everything can be called an algorithm.

I think it's correct to call it an algorithm (as it is universally done in the literature): Deutsch and Jozsa propose afinite sequence of mathematically rigorous instructions tosolve a class of specific problems, namely aPromise problem. So I think it clearly falls under the definition ofAlgorithm. (Being a physicist, I would say that the problem DJ solves -deciding whether a function onn bits is constant or balanced- is quite clearly a math or computer-science problem, not a physics problem (although one can built physical objects that realize such a function.) --Qcomp (talk)11:05, 1 March 2025 (UTC)[reply]

Thanks for your answer, but I'm not completely convinced. I'm sure the experts have chosen their terminology wisely, but it does not show in this article. Especially this sentence in the introduction seems misleading:

"... it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm."

It does not state that the quantum computerruns the algorithm exponentially faster (which it indeed does), but it says the algorithm itself is faster—an assertion that I believe is incorrect.

For a black-box problem, the implementation inside the black box should not matter. Computationally speaking, the function could just as well be implemented mechanically, using wooden gears, as long as it maps each input to a unique output. Using the same reasoning, I could design a classical setup where one of two computers is equipped with an X-ray camera and then define the problem such that the black box must not contain lead shielding—giving the X-ray-equipped computer an unfair advantage.

Shouldn't the concept of an algorithm be independent of such physically constrained advantages?— Precedingunsigned comment added by2001:1C06:2704:D500:DF17:1D45:B3B2:2107 (talk)12:37, 7 March 2025 (UTC)[reply]

(1) regardingruns faster: The statement "algorithm X runs exponentially faster than algorithm Y" is (to my understanding) the standard way to express that "there is an exponential separation between the (time-, query-, ...)complexity classes to which X and Y belong, respectively", i.e., if S(X,N) and S(Y,N) denote the number of steps needed to run the algorithm for an N-bit input, then for large enough N the ratio S(Y,N)/S(X,N) grows faster than an exponential in N one would say that "X is exponentially faster than Y". In the DJ case, we deal with a black-box algorithm and the S(X,N) is measured in term of the number of queries needed (also known as "query complexity" - but here it's the same as time-complexity in a setting where "query the oracle" if one allowed gate). So it's only a statement about the actual run timefor sufficiently large input when any effects of sub-leding terms, prefactors (due to specifics of the implementation such as programming language, gate set,...) become unimportant

(2)regarding the implementation of the black box: It is correct, that the implementation of the black box shouldn't matter (and it does not), but when comparing quantum and classical algorithms one needs to be precise about the black box: we need a "quantum black box", i.e., one that not only produces${\displaystyle \mathcal{B}(|j⟩=|f(j)⟩}$ for all basis states of the register but also${\displaystyle {\mathcal{B}}_f(\sum _j{c}_j|j⟩=\sum _j{c}_j|f(j)⟩}$. It doesn't matter is this is built from (quantum-)mechanical oscillators, superconducting qubits or photons, as long as it realizes the above action on all possible input states. One can run both quantum and classical algorithms using this oracle and the quantum algorithm will win because the classical one cannot query the black box with superposition states (they are not available to a classical algorithm). This implies, thatfor the classical algorithm the black box${\displaystyle \mathcal{B}}$ is equivalent to a classical black box that just realizes${\displaystyle {\mathcal{B}}_f^{(c)}(\sum _j{u}_j|j⟩=\sum _j|u_j{|}^2|f(j)⟩⟨f(j)|}$. When probing the two black boxes only with states${\displaystyle |j⟩}$ they seem to be identical, but they are not. In particular, one cannot run the DJ algorithm on the classical black box${\displaystyle {\mathcal{B}}_c}$ (one can, but it doesn't work). So that is the setting for which the quantum advantage is claimed: provided with the black box${\displaystyle {\mathcal{B}}_f}$ and the promise thatf is either constant or balanced, we can determine its properties with exponentially fewer queries with a quantum algorithm than with a classical one. --Qcomp (talk)13:37, 7 March 2025 (UTC)[reply]

• C-Class physics articles
• Low-importance physics articles
• C-Class physics articles of Low-importance
• C-Class Computer science articles
• Mid-importance Computer science articles
• WikiProject Computer science articles
• C-Class Computing articles
• Low-importance Computing articles
• C-Class software articles
• Low-importance software articles
• C-Class software articles of Low-importance
• All Software articles
• All Computing articles