Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM

Jeremy Huang, Young Kun Ko, Chunhao Wang

In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to th…