Quantum Algorithms for Evaluating MIN-MAX Trees

2007/10/31 by Cleve, Richard, Gavinsky, Dmytro, Yonge-Mallo, David L.
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.0710.5794

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.

Related

• A Quantum Algorithm for finding the Maximum
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees
• Time and Query Optimal Quantum Algorithms Based on Decision Trees
• A Quantum Algorithm for Finding k-Minima
• Noisy Tree Data Structures and Quantum Applications