{"id":"arxiv/2609.40293","url":"https://arxiv.org/abs/2609.40293","tags":["cs.CC","cs.DS","quant-ph"],"score":0,"title":"Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM","domain":"cs.CC","source":"arxiv","authors":["Jeremy Huang","Young Kun Ko","Chunhao Wang"],"reviews":0,"subject":"cs.CC","summary":"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 the SetDisjointness problem. However, there is an $\\tilde{O}(n)$-time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}