Quantum algorithms for evaluating MIN-MAX trees. arXiv:0710.5794

Abstract. We present a bounded-error quantum algorithm for evaluating Min-Max trees with N 1 2 +o(1) queries, where N is the size of the tree and where the allowable queries are comparisons of the form [xj < x k ]. This is close to tight, since there is a known quantum lower bound of A Min-Max tree is a tree whose internal nodes are minimum and maximum gates, at alternating levels, and whose leaves are values from some underlying ordered set. The size N of such a tree is the number of its leaves, whose values are referred to as x 1 , . . . , x N . The value of a Min-Max tree is the value of its root, a function of x 1 , . . . , x N . In the input value query model, queries explicitly access the values of the leaves. In the comparison query model, the values of x 1 , . . . , x N are not directly accessible; rather, queries are comparisons of the form [x j < x k ]. In this latter model, the appropriate output is any j ∈ {1, . . . , N} such that x j is the value of the tree. The comparison query model is commonly used in the analysis of classical parallel algorithms for searching and sorting. Note that, when the ordered set is {0, 1}, a Min-Max tree reduces to an And-Or tree. This implies that Barnum and Saks's lower bound of Ω(N Let W (N ) be the query complexity for And-Or trees of size N . We show that Min-Max trees can be evaluated with O(W (N ) log(N )) queries in both the input value model and the comparison model. Our algorithm combines the results on And-Or trees in Refs