Content deleted Content added
→Algorithm or Procedure?: Reply |
|||
| (33 intermediate revisions by 18 users not shown) | |||
Line 1:
{{Talk header}}
{{WikiProject banner shell|class=C|1=
{{
{{WikiProject
{{WikiProject
}}
== 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. :) [[User:Karadoc|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? <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Wmagro|Wmagro]] ([[User talk:Wmagro#top|talk]] • [[Special:Contributions/Wmagro|contribs]]) 19:48, 17 January 2020 (UTC)</small> <!--Autosigned by SineBot-->
:If the function is constant, you can't observe different values. [[Special:Contributions/128.250.0.202|128.250.0.202]] ([[User talk:128.250.0.202|talk]]) 06:00, 25 August 2022 (UTC)
== What the...? ==
Line 53 ⟶ 58:
The starting point is:
<math>{\color{Blue}\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)}\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)</math>
Applying <math>f(x)</math> gives
Line 86 ⟶ 91:
|}
==== This paragraph is okay, but IMHO it should be after the main algorithm. Otherwise it interrupts the flow of the article. [[User:MikeR613|MikeR613]] ([[User talk:MikeR613|talk]]) 19:10, 9 September 2012 (UTC)
=== Constant Functions ===
Line 149 ⟶ 119:
:: 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. [[User:Skippydo|Skippydo]] ([[User talk:Skippydo|talk]]) 22:32, 9 August 2011 (UTC)
:::I rewrote the motivation. Is that better? --[[User:RobinK|Robin]] ([[User talk:RobinK|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. --[[User:RobinK|Robin]] ([[User talk:RobinK|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.. [[User:Sperxios|Sperxios]] ([[User talk:Sperxios|talk]]) 00:15, 23 August 2013 (UTC)
:In layman's terms, the function <math>f</math> takes <math>n</math>-digit binary value as inputs and produces either a <math>0</math> or a <math>1</math> as output for each such value. <span style= "font-family: Tahoma, Geneva, sans-serif; font-variant:small-caps; color:silver; letter-spacing:2px; font-weight: 500"> — [[User:Aldaron|Aldaron]] • <small>[[User talk:Aldaron|T]]/[[Special:Contributions/Aldaron|C]] </small> </span> 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. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Sperxios|Sperxios]] ([[User talk:Sperxios|talk]] • [[Special:Contributions/Sperxios|contribs]]) 10:39, 25 August 2013 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Can we have references for the classical solution section? ==
Especially for the claim regarding conventional randomized algorithms. Where is this being got from?
[[User:M cuffa|M cuffa]] ([[User talk:M cuffa|talk]]) 13:15, 8 February 2014 (UTC)
: Agreed. Where does the "classical solution" section come from? [[User:Dr. Universe|Dr. Universe]] ([[User talk: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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|Aviv]] comment added by [[Special:Contributions/87.211.107.83|87.211.107.83]] ([[User talk:87.211.107.83|talk]]) 11:28, 30 September 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
== Example circuits ==
Circuits that provide a constant output of either <math>|0\rangle</math> or <math>|1\rangle</math>, assuming that the output qubit is initialised to <math>|0\rangle</math>, can be viewed as having the output qubit disconnected from the input qubits. It is therefore expected that the input qubits measure as <math>|0\rangle^{\otimes n}</math>.
{| class="wikitable"
|-
! Output qubit is constant <math>|0\rangle</math> !! Output qubit is constant <math>|1\rangle</math>
|-
| [[File:Deutsch constant 0.svg]] || [[File:Deutsch constant 1.svg]]
|}
In the circuit diagrams, the functions are shown within a dashed line border. It is important to note that an <math>X</math> gate that flips <math>|0\rangle</math> to <math>|1\rangle</math> has no effect in the Hadamard basis. <math>|+\rangle</math> passes through an <math>X</math> gate unchanged.
A sub-class of balanced functions uses only a single input qubit to decide whether the output qubit is <math>|0\rangle</math> or <math>|1\rangle</math>.
{| class="wikitable"
|-
! Output qubit is the value of one input qubit !! Output qubit is the negation of one input qubit
|-
| [[File:Deutsch balanced last qubit 0.svg]] || [[File:Deutsch balanced last qubit 1.svg]]
|}
In the Hadamard basis, the <math>CNOT</math> 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 <math>|0\rangle^{\otimes n-1}|1\rangle</math> due to the connection between the input qubits and the output qubit.
[[User:DavidBoden|DavidBoden]] ([[User talk: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. [[User:Jehochman|Jehochman]] <sup>[[User talk:Jehochman|Talk]]</sup> 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. [[User:JavaFXpert|JavaFXpert]] ([[User talk: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.<br>
: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 "[[WP:No_original_research#Routine_calculations|only routine calculations]] (like adding numbers), so I don't think writing whole programs is ok without providing a source. --[[User:Qcomp|Qcomp]] ([[User talk:Qcomp|talk]]) 20:44, 18 February 2025 (UTC)
::Thanks. I made modifications that I trust are acceptable. [[User:JavaFXpert|JavaFXpert]] ([[User talk: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.) --[[User:Qcomp|Qcomp]] ([[User talk: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? <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2001:1C06:2704:D500:DF17:1D45:B3B2:2107|2001:1C06:2704:D500:DF17:1D45:B3B2:2107]] ([[User talk:2001:1C06:2704:D500:DF17:1D45:B3B2:2107#top|talk]]) 12:37, 7 March 2025 (UTC)</small> <!--Autosigned by SineBot-->
:(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<br>
:(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 <math>\mathcal{B}(|j\rangle=|f(j)\rangle</math> for all basis states of the register but also <math>\mathcal{B}_f(\sum_j c_j |j\rangle=\sum_j c_j |f(j)\rangle</math>. 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 <math>\mathcal{B}</math> is equivalent to a classical black box that just realizes <math>\mathcal{B}_f^{(c)}(\sum_j u_j |j\rangle=\sum_j |u_j|^2 |f(j)\rangle\langle f(j)|</math>. When probing the two black boxes only with states <math>|j\rangle</math> they seem to be identical, but they are not. In particular, one cannot run the DJ algorithm on the classical black box <math>\mathcal{B}_c</math> (one can, but it doesn't work). So that is the setting for which the quantum advantage is claimed: provided with the black box <math>\mathcal{B}_f</math> 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. --[[User:Qcomp|Qcomp]] ([[User talk:Qcomp|talk]]) 13:37, 7 March 2025 (UTC)
| |||