Quantum Algorithms for Evaluating Min-Max Trees

DOI10.1007/978-3-540-89304-2_2zbMATH Open1162.68456arXiv0710.5794OpenAlexW1657432701MaRDI QIDQ5503293FDOQ5503293

Richard Cleve, David Yonge-Mallo, Dmitry Gavinsky

Publication date: 13 January 2009

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• A lower bound on the quantum query complexity of read-once functions

Cited In (7)

• Title not available (Why is that?)
• Challenges of adiabatic quantum evaluation of NAND trees
• Quantum branch-and-bound algorithm and its application to the travelling salesman problem
• Quantum algorithm for lexicographically minimal string rotation
• Quantum walks: a comprehensive review
• Entropy lower bounds for quantum decision tree complexity
• Intricacies of quantum computational paths

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)