Nested Grover's Algorithm for Tree Search

doi:10.3390/e28010024

Return

Nested Grover's Algorithm for Tree Search

2025-12-24

Andreas Wichert *

DOI：10.3390/e28010024

Original

Original request for help

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