Quantum Algorithms for Evaluating MIN-MAX Trees
Richard Cleve, Gavinsky, Dmytro, David L. Yonge-Mallo · arXiv (Cornell University) · 2007
We present a bounded-error quantum algorithm for evaluating Min-Max trees. For a tree of size N our algorithm makes N^{1/2+o(1)} comparison queries, which is close to the optimal complexity for this problem.