Nested Grover's Algorithm for Tree Search

• URL: http://arxiv.org/abs/2509.07041v1
• Date: Mon, 08 Sep 2025 10:12:32 GMT
• Title: Nested Grover's Algorithm for Tree Search
• Authors: Andreas Wichert,
• Abstract summary: We investigate optimizing quantum tree search algorithms by employing a nested Grover Algorithm.<n>We introduce the partial candidate solution, which indicates a node at a specific depth of the tree.<n>By employing such a function, we define the oracled, which enables us to decompose the quantum tree search using Grover algorithm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 algorithm.

Related papers

• Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
  We build upon previous work by Baertschi and Eidenbenz to construct a state preparation routine for the Traveling Salesperson Problem.<n>With our iterations, we aim to achieve a reasonable approximation ratio with only a number of iterations.
  arXiv  Detail & Related papers  (2026-02-09T09:21:04Z)
• A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search [0.0]
  We present a quantum algorithm for solving perfect mazes by casting the pathfinding task as a structured search problem.<n>Building on Grover's amplitude amplification, the algorithm encodes all candidate paths in superposition and evaluates their proximity to the goal.<n>A Grover-compatible oracle marks high-fitness states, and an adaptive cutoff strategy refines the search iteratively.
  arXiv  Detail & Related papers  (2025-07-29T15:51:19Z)
• Regular Tree Search for Simulation Optimization [5.54189661879098]
  We propose a class of random algorithms, called Regular Tree Search, which integrates adaptive sampling with partitioning the search space.<n>We prove global convergence under sub-Gaussian noise, based on assumptions involving the optimality gap, without requiring continuity of the objective function.
  arXiv  Detail & Related papers  (2025-06-21T12:07:01Z)
• Uncertainty-Guided Likelihood Tree Search [37.25859935454988]
  Tree search is a fundamental tool for planning, as many sequential decision-making problems can be framed as searching over tree-structured spaces.<n>We propose an uncertainty-guided tree search algorithm for settings where the reward function is a log-likelihood function of the paths.
  arXiv  Detail & Related papers  (2024-07-04T14:08:50Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks [70.0197695666261]
  We introduce Q* search, a search algorithm that uses deep Q-networks to guide search in order to take advantage of the sum of the transition costs and values of the children of a node. We use Q* search to solve the Rubik's cube when formulated with a large action space that includes 1872 meta-actions. Q* search is up to 129 times faster and generates up to 1288 times fewer nodes than A* search.
  arXiv  Detail & Related papers  (2021-02-08T20:36:41Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
  This approach makes use of a algorithm to explore the search space tree of a problem instance. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees.
  arXiv  Detail & Related papers  (2020-10-22T08:33:58Z)
• Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
  We learn binary decision trees that partition data for some downstream task. We do so by relaxing a mixed-integer program for the discrete parameters. We derive customized algorithms to efficiently compute the forward and backward passes.
  arXiv  Detail & Related papers  (2020-10-09T15:11:28Z)
• Quantum Search with Prior Knowledge [15.384459603233978]
  We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
  arXiv  Detail & Related papers  (2020-09-18T09:50:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.