New summing algorithm using ensemble computing
C D Helon, V. Protopopescu · Journal of Physics A Mathematical and General · 2002
We propose an ensemble algorithm, which provides a new approach for evaluating and summing up a set of function samples. The proposed algorithm is not a quantum algorithm, insofar as it does not involve quantum entanglement. The query complexity of the algorithm depends only on the scaling of the measurement sensitivity with the number of distinct spin subensembles. From a practical point of view, the proposed algorithm may result in an exponential speedup, compared to known quantum and classical summing algorithms. However, in general, this advantage exists only if the total number of function samples is below a threshold value which depends on the measurement sensitivity.