Tree search and quantum computation

Traditional tree search algorithms supply a blueprint for modeling problem solving behaviour. A diverse spectrum of problems can be formulated in terms of tree search. Quantum computation, namely Grover’s algorithm, has aroused a great deal of interest since it allows for a quadratic speedup to be obtained in search procedures. In this work we consider the impact of incorporating classical search concepts alongside Grover’s algorithm into a hybrid quantum search system. Some of the crucial points examined include: (1) the reverberations of contemplating the use of non-constant branching factors; (2) determining the consequences of incorporating an heuristic perspective into a quantum tree search model.

• Publication year

  2015

• Venue

  Quantum Information Processing

• Publication date

  2015-02-06

• Fields of study

  Physics, Computer Science

• Identifiers
  DOI 10.1007/s11128-010-0212-zarXiv 1502.01951
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Behind Deep Blue

  2022cited by this paper
• Quantum Computation and Quantum Information

  2012cited by this paper
• An Analysis of Navigation Algorithms for Smartphones Using J2ME

  2009cited by this paper
• Context Inference for Mobile Applications in the UPCASE Project

  2009cited by this paper
• An Introduction to Quantum Computing

  2007cited by this paper
• Quantum Partial Search of a Database with Several Target Items

  2006cited by this paper
• Fixed-point quantum search.

  2005cited by this paper
• Simple Algorithm for Partial Quantum Search

  2005cited by this paper
• Hierarchical Quantum Search

  2005cited by this paper
• Coins make quantum walks faster

  2004cited by this paper
• Is partial quantum search of a database any easier?

  2004cited by this paper
• Quantum search algorithms

  2004cited by this paper
• Quantum random walks: An introductory overview

  2003cited by this paper
• Quantum computing

  2003cited by this paper
• Quantum walk algorithm for element distinctness

  2003cited by this paper
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS

  2003cited by this paper
• Quantum random-walk search algorithm

  2002cited by this paper
• Deep Blue

  2002cited by this paper
• Family of sure-success quantum algorithms for solving a generalized Grover search problem

  2002cited by this paper
• Exponential algorithmic speedup by a quantum walk

  2002cited by this paper
• Trade-offs in the quantum search algorithm

  2002cited by this paper
• Grover algorithm with zero theoretical failure rate

  2001cited by this paper
• Quantum computing

  2001cited by this paper
• An Example of the Difference Between Quantum and Classical Random Walks

  2001cited by this paper
• One-dimensional quantum walks

  2001cited by this paper
• Statistical Modelling with Quantile Functions

  2000cited by this paper
• Quantum Walk on the Line

  2000cited by this paper
• Quantum Amplitude Amplification and Estimation

  2000cited by this paper
• Quantum walks on graphs

  2000cited by this paper
• Quantum Walk on the Line

  2000cited by this paper
• Random Walks on Infinite Graphs and Groups: Bibliography

  2000cited by this paper
• IBM's Deep Blue Chess grandmaster chips

  1999cited by this paper
• A Grover-based quantum search of optimal order for an unknown number of marked elements

  1999cited by this paper
• Experimental Implementation of Fast Quantum Searching

  1998cited by this paper
• Quantum Search on Structured Problems

  1998cited by this paper
• Quantum computation and decision trees

  1997cited by this paper
• GROVER'S QUANTUM SEARCHING ALGORITHM IS OPTIMAL

  1997cited by this paper
• A framework for fast quantum mechanical algorithms

  1997cited by this paper
• Strengths and Weaknesses of Quantum Computing

  1997cited by this paper
• Quantum Computers Can Search Rapidly by Using Almost Any Transformation

  1997cited by this paper
• A framework for structured quantum search

  1997cited by this paper
• Logic and Computer Design Fundamentals

  1997cited by this paper
• A fast quantum mechanical algorithm for database search

  1996cited by this paper
• Random walks and random environments, volume 1: Random walks

  1996cited by this paper
• From quantum cellular automata to quantum lattice gases

  1996cited by this paper
• Random walks and random environments. Volume 1: Random walks

  1996cited by this paper
• Tight bounds on quantum searching

  1996cited by this paper
• Random Walks and Random Environments: Volume 1: Random Walks

  1995cited by this paper
• Algorithms for quantum computation: discrete logarithms and factoring

  1994cited by this paper
• Linear-Space Best-First Search

  1993cited by this paper
• Quantum random walks.

  1993cited by this paper
• Game Tree Search on Massively Parallel Systems

  1993cited by this paper
• Chess 4.5-The Northwestern University chess program

  1988cited by this paper
• Sliding Piece Puzzles

  1987cited by this paper
• SOAR: An Architecture for General Intelligence

  1987cited by this paper
• Chunking in Soar: The Anatomy of a General Learning Mechanism

  1986cited by this paper
• Chunking in Soar

  1986cited by this paper
• Depth-First Iterative-Deepening: An Optimal Admissible Tree Search

  1985cited by this paper
• Reversible Computing

  1980cited by this paper
• Reversible Computing

  1980cited by this paper
• Principles of Artificial Intelligence

  1980cited by this paper
• Probability and Statistics

  1977cited by this paper
• Algorithm 447: efficient algorithms for graph manipulation

  1973cited by this paper
• GPS : a case study in generality and problem solving

  1971cited by this paper
• A Formal Basis for the Heuristic Determination of Minimum Cost Paths

  1968cited by this paper
• Paths, Trees, and Flowers

  1965cited by this paper
• A guide to the general problem-solver program GPS-2-2

  1963cited by this paper
• Probability and Statistics

  1959cited by this paper
• Report on a general problem-solving program

  1959cited by this paper
• Formal Reductions of the General Combinatorial Decision Problem

  1943cited by this paper
• The two-valued iterative systems of mathematical logic

  1942cited by this paper
• A new notation for quantum mechanics

  1939cited by this paper
• A fast quantum mechanical algorithm for database search Lov

  year unknowncited by this paper

• Nested Grover’s Algorithm for Tree Search

  2025cites this paper
• Chapter Ten - Qubit representation of a binary tree and its operations in quantum computation

  2023cites this paper
• A Quantum Planner for Robot Motion

  2022cites this paper
• Generalised Quantum Tree Search

  2021cites this paper
• Quantum Mathematics in Artificial Intelligence

  2021cites this paper
• Quantum Robotics: A Primer on Current Science and Future Perspectives

  2017cites this paper
• Quantum Computation for Artificial Intelligence

  2017cites this paper
• Artificial intelligence and a universal quantum computer

  2016cites this paper
• Quantum search with prior knowledge

  2015cites this paper
• Quantum Iterative Deepening with an Application to the Halting Problem

  2013cites this paper
• Intricacies of quantum computational paths

  2012cites this paper
• Iterative Quantum Tree Search

  2011cites this paper
• A quantum production model

  2011influential citation
• Problem-solving and Quantum Computation

  2011cites this paper
• A Hierarchical Sorting Oracle

  2011cites this paper