Quantum lower bounds connect 3SUM and set disjointness problems
Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
Computational ComplexityData Structures and Algorithms
Summary
The paper studies how hard certain problems remain when using quantum computers. It focuses on two problems: 3SUM, which involves finding three numbers that sum to zero, and SetDisjointness, determining whether two sets share any elements. The authors show how to translate assumptions about the difficulty of 3SUM into constraints on algorithms for SetDisjointness in the quantum setting. They create a framework that relates these problems and prove tradeoffs on the time quantum algorithms must spend preparing data versus answering queries.
What this means in practice
- •For quantum algorithm designers: Identify fundamental tradeoffs in quantum query and preprocessing times when building data structure algorithms for SetDisjointness.
- •For quantum complexity researchers: Use the framework to explore conditional lower bounds on problems reducible to SetDisjointness in quantum environments.
A theory result. No direct application yet.
Authors
Jeremy Huang, Young Kun Ko, Chunhao Wang
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 $\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 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.