Quantum Algorithms for Evaluating MIN-MAX Trees

Abstract

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.

Re-submitted due to name change. Besides the name of one of the authors, this version is identical to that of 31 Oct 2007: in particular, some of the authors' affiliations and the references given in the document are outdated

References in corpus (3)

• A Quantum Algorithm for the Hamiltonian NAND Tree
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
• Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer