New summing algorithm using ensemble quantum computing
C. D’Helon, V. Protopopescu · arXiv (Cornell University) · 2002
We propose an ensemble quantum algorithm, which provides a new approach for summing up a set of function samples. The query complexity of the algorithm depends only on the scaling of the measurement sensitivity with the number of distinct spin sub-ensembles. 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.