.png){kind=icon}
.png){kind=icon}
Return
Nested Grover's Algorithm for Tree Search
.png){kind=icon}
OA
AI
DOI：10.3390/e28010024.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We investigate optimizing quantum tree search algorithms by employing a nested Grover Algorithm. This approach seeks to enhance results compared to previous Grover-based methods by expanding the tree of partial assignments to a specific depth and conducting a quantum search within the subset of remaining assignments. The study explores the implications and constraints of this approach, providing a foundation for quantum artificial intelligence applications. Instead of utilizing conventional heuristic functions that are incompatible with quantum tree search, we introduce the partial candidate solution, which indicates a node at a specific depth of the tree. By employing such a function, we define the concatenated oracle, which enables us to decompose the quantum tree search using Grover's algorithm. With a branching factor of 2 and a depth of m, the costs of Grover's algorithm are O(2m/2). The concatenated oracle allows us to reduce the cost to O(m2m/4) for m partial candidate solutions.
Keywords:
quantum tree search
Grover's algorithm
heuristics
nested search