Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification
Andreas Wichert · 2026
Read Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification by Andreas Wichert (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28452.txt.
Introduction
Andreas Wichert, writing alone, speeds up quantum tree search. Amplitude amplification, the generalization behind Grover's famous search algorithm, is usually analyzed as if every branch of a search tree were as wide as the widest one. Real trees are uneven, and Wichert shows the cost is governed by the average branching instead.
Building the tree dynamically, his construction reaches a query complexity set by the square root of the average branching raised to the depth, improving on the worst-case figure. He also pushes back on the fashion for quantum backtracking, noting it fits only problems with a natural backtracking shape. Because the dynamically built tree hides its own structure, he proposes sampling methods to estimate it. He also adds a quantum greedy search guided by a lookahead heuristic borrowed from the Soar cognitive architecture.
Catalog record
| CREATOR | Andreas Wichert |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28452
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification Andreas Wichert 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 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 m with query complexity ( b a v g ) m \sqrt{\left(b_{avg}\right)^{m}} where b a v g b_{avg} denotes the average branching factor, improving upon the commonly assumed ( b m a x ) m \sqrt{\left(b_{max}\right)^{m}} , where b m a x 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. 1 Introduction In this work, we study quantum tree search algorithms through the lens of amplitude amplification, with the aim of clarifying and sharpening complexity claims that have been imprecisely stated in the existing literature [ 11 ] . To ground our theoretical development concretely, we illustrate all key concepts and algorithms using the 8-puzzle, a canonical sliding tile problem whose search tree exhibits the kind of variable, state-dependent branching structure that makes the distinction between average and worst-case complexity practically meaningful. A central contribution is a rigorous analysis of query complexity for dynamically constructed search trees. Specifically, we demonstrate that for a search tree of depth m , the query complexity is governed by \sqrt{\left(b_{avg}\right)^{m}} , where b_{avg} denotes the average branching factor of the tree of depth m , a bound that is strictly better than the commonly assumed worst-case complexity based on the maximum branching factor b_{\max} [ 15 ] . This distinction is non-trivial: conflating average- and worst-case branching factors leads to a systematic overestimation of the cost of amplitude-amplification-based search, and has contributed to misleading comparisons with alternative quantum approaches [ 11 ] . We address a recurring claim in the quantum search literature, namely that Grover-based algorithms are generically inferior to quantum backtracking [ 11 ] . We argue that this comparison is only valid when the problem structure naturally admits a backtracking formulation, that is, when the search space can be organized as a tree with well-defined pruning conditions that quantum walk can exploit. For problems that do not naturally form a backtracking tree, this assumption breaks down, and amplitude amplification can achieve a strictly better query complexity than quantum backtracking. A second structural observation concerns the dynamic nature of the search tree. The algorithm constructs the search tree. This dynamic construction means that the internal structure of the tree is not accessible as an explicit data structure at any point during the computation. Importantly, this is not a limitation peculiar to our approach: the same constraint applies to quantum backtracking, where the implicit tree explored by the quantum walk is similarly inaccessible. Given that the tree structure is not directly observable, we propose statistical methods to estimate it from the outside. These estimates can be used to set the number of amplitude amplification iterations. Finally, we propose a quantum greedy search algorithm based on a lookahead heuristic. The design of this heuristic is motivated by the classical cognitive architecture Soar [ 4 ] , a well-studied model of human-like problem solving that combines goal-directed search. By incorporating a quantum lookahead step, evaluating multiple candidate branches in superposition before committing to a direction, the algorithm emulates the deliberative, heuristic-guided reasoning that characterizes effective human search behavior. Together, these contributions provide a more complete and accurate picture of quantum tree search via amplitude amplification: correcting complexity claims, characterizing structural limitations, providing tools to work around those limitations, and extending the framework in a cognitively motivated direction. Throughout, the 8-puzzle serves as a concrete running example, grounding abstract complexity results in a tractable, well-understood domain. 2 Tree Search and Grover’s Algorithm Nodes and edges in a search tree represent states and transitions between states. The initial state is the root, and from each state v , either b=br(v) states can be reached or it is a leaf. From a leaf, no other state can be reached, br(v)=0 . We call b=br(v) the branching factor of a node v , indicating the number of possible choices. A leaf can either be the desired of the computation or an impasse when there are no valid transitions to a succeeding state. Each node v representing a state except the root has a unique parent node. Every node and its parent are connected by an edge, and each parent has b=br(v) children. A path in a graph is an ordered sequence of nodes, where each pair of adjacent nodes in the sequence is connected by an edge from the root node to a leaf node. Each path represents a unique route from the root node to the leaf node. The depth of a node v is defined as the number of edges on the path from the root node to that node. The depth of the search tree is indicated by m . It is defined as the number of edges that connect the root node to the deepest leaf node. When the branching factor is constant, and each leaf node has the same depth, the tree exhibits exponential growth in relation to its depth m . For instance, when the branching factor b is constant at 2 and the depth of the tree m is 5 , the resulting search tree is depicted in Figure 1 . This tree has 32=2^{5} leaf nodes. Each unique path from the root to a leaf node is represented by one of the 32 binary numbers, each consisting of five digits. Each binary number serves as a path descriptor, with each digit indicating whether to move left (1) or right (0). Figure 1: Search tree for b=2 and depth m=5 with 32=2^{5} leaf nodes. Each unique path from the root to a leaf node is represented by one of the 32 binary numbers, each consisting of five digits. Each binary number serves as a path descriptor, with each digit indicating whether to move left (1) or right (0). For a constant branching factor b>2 , each question has b possible answers. The m answers can be represented by a base- b number with m digits. In a quantum computation, we can simultaneously represent all possible path descriptors. There’s one path descriptor for each leaf off the tree. Using Grover’s algorithm, we search through all possible paths and verify whether each path leads to the desired state that is marked by an oracle. This