{"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","summary":"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)$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-09","reactions":{}}