Knowledge representation has long been a cornerstone in Artificial Intelligence. Goal-based agents, also known as problem-solving agents use atomic representations to further reason about what actions and states to consider, given a goal. When the agent deals with known and deterministic environments, the process of reaching the goal can be formalised as a search problem [1]}. The possible action sequences starting at the initial state form a search tree where branches are actions and the nodes correspond to states in the state space of the problem. Therefore, reasoning reduces to tree searching. Quantum search algorithms, over some variant of the original Grover's Algorithm [2]}, perform search in superposition and have the potential to provide a quadratic speed-up. When the problem that the agent is trying to solve has a constant branching factor, Grover's algorithm can perform better than any classical uninformed tree search algorithm [3]}, even in an iterative deepening strategy [4]}. However, all possible quantum speed-ups work under the weak assumption of a constant branching factor problem-solving agent. When we relax the assumption for non-constant branching factor problems, then, as proved in [3]}, quantum algorithms no longer guarantee superior performance compared to classical tree search algorithms. This is due to the fact that in these cases, for classical algorithms the effective branching factor converges to the average one. However, in the quantum setting one must always use the maximum branching factor to encode superpositions. This limiting factor results in certain cases in a slowdown compared to the classical counterpart. Real-world world problems, for example, route-finding problems [6]}, typically have large, and most importantly, non-constant branching factors.
