A framework for fast quantum mechanical algorithms 论文

摘要

A framework is presented for the design and analysis of quantum mechanical algorithms, the 0( fi) step quantum search algorithm is an immediate consequence of this framework. It leads to several other search-type applications -an example is presented where the Walsh-Hadamard (W-H) transform of the quantum search algorithm is replaced by another transform tailored to the parameters of the problem. Also, it leads to quantum mechanical algorithms for problems not immediately connected with search -two such algorithms are presented for calculating the mean and median of statistical distributions. In order to classically estimate either the mean or median of a given distribution to a precision E , needs a(~-~) steps. The best known quantum mechanical algorithm for estimating the median takes O(E-') steps, and that for estimating the mean takes O(E -1.5 ) steps. This paper presents O(E-l) step algorithms for both problems (all bounds are upto polylogarithmic factors). Both algorithms are considerably simpler than known algorithms.