Quantum Algorithms for Evaluating Min-Max Trees

DOI10.1007/978-3-540-89304-2_2MaRDI QIDQ5503293zbMATH OpenOpenAlexFDO

Authors Richard Cleve, Dmitry Gavinsky, David Yonge-Mallo

Publication date 13 January 2009

Published in Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.5794

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

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.

Recommendations

• Faster quantum algorithm for evaluating game trees
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
• Quantum Query Complexity of Some Graph Problems
• Span-program-based quantum algorithm for evaluating formulas

Cites work

• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• A lower bound on the quantum query complexity of read-once functions
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Strengths and Weaknesses of Quantum Computing

Cited in

(12)

• Intricacies of quantum computational paths
• Quantum algorithm for lexicographically minimal string rotation
• Faster quantum algorithm for evaluating game trees
• Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Entropy lower bounds for quantum decision tree complexity
• An exact quantum algorithm for a restricted subtraction game
• Quantum walks: a comprehensive review
• Quantum branch-and-bound algorithm and its application to the travelling salesman problem
• Challenges of adiabatic quantum evaluation of NAND trees
• Discrete-query quantum algorithm for NAND trees

This page was built for publication: Quantum Algorithms for Evaluating Min-Max Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5503293)