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)

another mistake?

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)

If the function is constant, you can't observe different values. 128.250.0.202 (talk) 06:00, 25 August 2022 (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 )$

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

==== 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)

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)

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)

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)

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

Proposed move: Deutsch–Jozsa algorithm -> Deutsch–Jozsa problem

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)

Better Explaination for the function on the problem statement?

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)

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

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)

Can we have references for the classical solution section?

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

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

Missing main algorithm description and a section about implementation

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)

Example circuits

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

Output qubit is constant $|0\rangle$	Output qubit is constant $|1\rangle$

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

A sub-class of balanced functions uses only a single input qubit to decide whether the output qubit is $|0\rangle$ or $|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 $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 $|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)

Ancilla bit

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)

Shortened Qiskit code example and explanation

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)

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 by WP: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)

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

Algorithm or Procedure?

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 a finite sequence of mathematically rigorous instructions to solve a class of specific problems, namely a Promise problem. So I think it clearly falls under the definition of Algorithm. (Being a physicist, I would say that the problem DJ solves -deciding whether a function on n 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)

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 computer runs 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? — Preceding unsigned comment added by 2001:1C06:2704:D500:DF17:1D45:B3B2:2107 (talk) 12:37, 7 March 2025 (UTC)

(1) regarding runs 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 time for 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 ${\mathcal {B}}(|j\rangle =|f(j)\rangle$ for all basis states of the register but also ${\mathcal {B}}_{f}(\sum _{j}c_{j}|j\rangle =\sum _{j}c_{j}|f(j)\rangle$. 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, that for the classical algorithm the black box ${\mathcal {B}}$ is equivalent to a classical black box that just realizes ${\mathcal {B}}_{f}^{(c)}(\sum _{j}u_{j}|j\rangle =\sum _{j}|u_{j}|^{2}|f(j)\rangle \langle f(j)|$. When probing the two black boxes only with states $|j\rangle$ they seem to be identical, but they are not. In particular, one cannot run the DJ algorithm on the classical black box ${\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 ${\mathcal {B}}_{f}$ and the promise that f 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)