Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks

Harry Buhrman, Bruno Loff, Subhasree Patro +1

Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5…