published by Dmitry Gavinsky
in 2019
in Physics
and research's language is
English
Download
Abstract in English
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.