Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

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ⁿ), from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, O(1.3100ⁿ). The previous best bound in this model, to our knowledge, is O(1.3231ⁿ). (2) k-Colouring below the previous best bound for k ∈ \5, 7, 8, 9, 10, 11\ and 13 ≤ k ≤ 18, from O(1.4518ⁿ) for $k = 5$ to O(1.9233ⁿ) for $k = 18$. (3) Dominating Set in O(1.2235ⁿ), against the previous O(2n/2), Independent Dominating Set in O(1.1583ⁿ), and Edge Dominating Set and Minimum Maximal Matching in O(1.1501ⁿ). (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with cᵏ nodes up to polynomial factors, the problem is solved in quantum time (2 - 1/c)n/2 up to polynomial factors. This gives Feedback Vertex Set in O(1.3081ⁿ), Subset and Group Feedback Vertex Set in O(1.3229ⁿ), Cluster Vertex Deletion in O(1.2033ⁿ), 3-Hitting Set in O(1.2405ⁿ), Proper Interval Vertex Deletion in O(1.3541ⁿ), Multicut on Trees in O(1.1647ⁿ) and Min-Ones d-SAT in O^*((2-1/d)n/2). (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in O(1.0555ⁿ) and for Feedback Vertex Set in O(1.2161ⁿ). The colouring exponents for k ≥ 6 come from an evaluation of a known reduction recursion, computed in floating point with a margin.