Id: arxiv/2611.12714 Url: https://arxiv.org/abs/2611.12714 Tags: cs.DS, cs.CC, quant-ph Score: 0 Title: Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search Domain: cs.DS Source: arxiv Authors: Sebastian Senge Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-09 Page: https://delphi.science/r/arxiv/2611.12714 We give quantum algorithms for exponential-time problems on $n$ vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time $O(1.3032^n)$, from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, $O(1.3100^n)$. The previous best bound in this model, to our knowledge, is $O(1.3231^n)$. (2) $k$-Colouring below the previous best bound for $k \in \{5, 7, 8, 9, 10, 11\}$ and $13 \le k \le 18$, from $O(1.4518^n)$ for $k = 5$ to $O(1.9233^n)$…