Content deleted Content added
→Algorithm or Procedure?: yes, it's an algorithm |
No edit summary |
||
Line 183:
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?
| |||