Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.28452

Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification

Andreas Wichert

quant-phSubmitted Jun 26, 2026• Announced Jun 29, 2026• 0 citations
arXivHTMLPDF

Abstract

In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary $A$, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth $m$ with query complexity $\sqrt{\left(b_{avg}\right)^m}$ where $b_{avg}$ denotes the average branching factor, improving upon the commonly assumed $\sqrt{\left(b_{max}\right)^m}$, where $b_{max}$ is the maximum branching factor. We further challenge the widespread assumption that amplitude amplification is inferior to quantum backtracking. In fact, quantum backtracking is unsuitable for problems that do not naturally admit a backtracking structure; in such cases, amplitude amplification yields improved query complexity. We observe that amplitude amplification constructs the search tree dynamically, rendering its internal structure inaccessible, a constraint that applies equally to quantum backtracking. To address this, we propose sampling-based methods to estimate the tree structure, under the assumption that it approximates a normal distribution with increasing depth. Finally, we introduce a quantum greedy search based on a lookahead heuristic inspired by the classical cognitive architecture Soar, which models human-like problem-solving strategies.

Related papers

Quantum Search with Prior Knowledge

Xiaoyu He, Jialin Zhang, Xiaoming Sun

Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes 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:2009.08721•Sep 18, 2020•1 citation

Quantum Search on Computation Trees

Jevgēnijs Vihrovs

We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex \(v\) in the tree of depth \(D\) is computed in \(t_v\) steps from its parent, then we show that detection of a marked vertex requires \(\text O(\sqrt {TD})\) queries to the steps of the computing procedures, where \(T = \sum_v t^2_v\). This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.

arXiv:2505.22405•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•0 citations

Nested Grover’s Algorithm for Tree Search

Andreas Wichert

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(m·2m/4) for m partial candidate solutions.

arXiv:2509.07041•Entropy•Dec 24, 2025•1 citation

The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0

Kamil Ravilevich Khadiev, Ilnaz Mannapov, Liliya Safina

In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in $O(hd(NM+N \log N))$ running time, where $M$ is a number of classes, $N$ is the size of a training data set, $d$ is a number of attributes of each element, $h$ is a tree height. Firstly, we improved the classical version, the running time of the new version is $O(h\cdot d\cdot N\log N)$. Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{ü}rr-Høyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is $O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)$ that is better than complexity of the classical algorithm.

arXiv:1907.06840•Jul 16, 2019•18 citations

Tree Search and Quantum Computation

Andreas Wichert

Abstract. Traditional tree search algorithms supply a blueprint for modeling prob-lem solving behaviour. A diverse spectrum of problems can be formulated in terms of tree search. Quantum computation, in particular 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 con-cepts 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.

•Jan 9, 2016•12 citations

Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer

Haoxiang Guo

We demonstrated the detailed construction of the hybrid quantum-classical computer. Based on this architecture, the useful concept of amplitude interception is illustrated. It is then embedded into a combination of Depth-First Search and Grover's algorithm to generate a novel approach, the Depth-First Grover Search(DFGS), to handle multi-solution searching problems on unstructured databases with an unknown number of solutions. Our new algorithm attains an average complexity of $\mathcal{O}(m\sqrt{N})$ which performs as efficient as a normal Grover Search, and a $\mathcal{O}(\sqrt{p}N)$ complexity with a manually determined constant $p$ for the case with all elements are solutions, where a normal Grover Search will degenerate to $\mathcal{O}(N\sqrt{N})$. The DFGS algorithm is more robust and stable in comparison.

arXiv:2210.04664•Oct 10, 2022•0 citations
In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary AAA, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth mmm with query complexity (bavg)m\sqrt{\left(b_{avg}\right)^m}(bavg​)m​ where bavgb_{avg}bavg​ denotes the average branching factor, improving upon the commonly assumed (bmax)m\sqrt{\left(b_{max}\right)^m}(bmax​)m​, where bmaxb_{max}bmax​ is the maximum branching factor. We further challenge the widespread assumption that amplitude amplification is inferior to quantum backtracking. In fact, quantum backtracking is unsuitable for problems that do not naturally admit a backtracking structure; in such cases, amplitude amplification yields improved query complexity. We observe that amplitude amplification constructs the search tree dynamically, rendering its internal structure inaccessible, a constraint that applies equally to quantum backtracking. To address this, we propose sampling-based methods to estimate the tree structure, under the assumption that it approximates a normal distribution with increasing depth. Finally, we introduce a quantum greedy search based on a lookahead heuristic inspired by the classical cognitive architecture Soar, which models human-like problem-solving strategies.
Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes 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.
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex vvv in the tree of depth DDD is computed in tvt_vtv​ steps from its parent, then we show that detection of a marked vertex requires O(TD)\text O(\sqrt {TD})O(TD​) queries to the steps of the computing procedures, where T=∑vtv2T = \sum_v t^2_vT=∑v​tv2​. This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.
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(m·2m/4) for m partial candidate solutions.
In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in O(hd(NM+Nlog⁡N))O(hd(NM+N \log N))O(hd(NM+NlogN)) running time, where MMM is a number of classes, NNN is the size of a training data set, ddd is a number of attributes of each element, hhh is a tree height. Firstly, we improved the classical version, the running time of the new version is O(h⋅d⋅Nlog⁡N)O(h\cdot d\cdot N\log N)O(h⋅d⋅NlogN). Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{ü}rr-Høyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is O(h⋅dlog⁡d⋅Nlog⁡N)O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)O(h⋅d​logd⋅NlogN) that is better than complexity of the classical algorithm.
Abstract. Traditional tree search algorithms supply a blueprint for modeling prob-lem solving behaviour. A diverse spectrum of problems can be formulated in terms of tree search. Quantum computation, in particular 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 con-cepts 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.
We demonstrated the detailed construction of the hybrid quantum-classical computer. Based on this architecture, the useful concept of amplitude interception is illustrated. It is then embedded into a combination of Depth-First Search and Grover's algorithm to generate a novel approach, the Depth-First Grover Search(DFGS), to handle multi-solution searching problems on unstructured databases with an unknown number of solutions. Our new algorithm attains an average complexity of O(mN)\mathcal{O}(m\sqrt{N})O(mN​) which performs as efficient as a normal Grover Search, and a O(pN)\mathcal{O}(\sqrt{p}N)O(p​N) complexity with a manually determined constant ppp for the case with all elements are solutions, where a normal Grover Search will degenerate to O(NN)\mathcal{O}(N\sqrt{N})O(NN​). The DFGS algorithm is more robust and stable in comparison.