Theory of the quantum speed-up
Giuseppe Castagnoli, David Ritz Finkelstein · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2001
We analyse the quantum speed-up: the fact that some quantum algorithms are faster than their classical counterparts. The classical formulation of problem solving must be modified. In general a problem statement defines the solution only implicitly, giving a property that a solution must possess, and does not represent a process that constructs the solution explicitly. A solution algorithm must then specify explicitly a finite step-by-step procedure that constructs the solution through a dynamical development. In the quantum speed-up, however, an implicit definition directly determines the solution through an extra-dynamical irreversible non-algorithmic quantum measurement. While in an algorithmic solution, the initial conditions determine the solution in a one-way manner, in a solution by measurement, the initial conditions and a final condition influence the solution jointly. The quantum computation is as implicit as the problem statement. Implicit determination with joint influence is richer than explicit one-way dynamical determination, as it yields the speed-up. Quantum problem solving with speed-up is essentially extra-dynamical and irreversible. Other forms of implicit quantum problem solving may exploit extra-dynamical projections for speed-up.