Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
Abstract
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 Õ(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 setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a p + 2q geqslant 1 tradeoff bound for quantum SetDisjointness algorithms with O(Np) preprocessing time and O(Nq) query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.
Related
- Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling
- Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
- Quantum Secure Non-Interactive Reductions
- Coarse-grained models for loop quantum gravity and their renormalization
- Iterative Quantum Optimization: From Greedy Reductions to Branch-and-Bound
BibTeX
@misc{huang2026quantum,
title = {{Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM}},
author = {Jeremy Huang and Young Kun Ko and Chunhao Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40293},
eprint = {2609.40293},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40293},
}
RIS
TY - UNPB
TI - Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
AU - Jeremy Huang
AU - Young Kun Ko
AU - Chunhao Wang
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40293
UR - https://arxiv.org/abs/2609.40293
AB - 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 Õ(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 setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a p + 2q geqslant 1 tradeoff bound for quantum SetDisjointness algorithms with O(N^p) preprocessing time and O(N^q) query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.
ER -