Content deleted Content added
m Signing comment by 2001:1C06:2704:D500:DF17:1D45:B3B2:2107 - "" |
→Algorithm or Procedure?: Reply |
||
Line 193:
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)
| |||