Title: Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems,
Abstract: In this paper, we study quantum query complexity of the following rather
natural tripartite generalisations (in the spirit of the 3-sum problem) of the
hidden shift and the set equality problems, which we call the 3-shift-sum and
the 3-matching-sum problems.
The 3-shift-sum problem is as follows: given a table of $3\times n$ elements,
is it possible to circularly shift its rows so that the sum of the elements in
each column becomes zero? It is promised that, if this is not the case, then no
3 elements in the table sum up to zero. The 3-matching-sum problem is defined
similarly, but it is allowed to arbitrarily permute elements within each row.
For these problems, we prove lower bounds of $\Omega(n^{1/3})$ and
$\Omega(\sqrt n)$, respectively. The second lower bound is tight.
The lower bounds are proven by a novel application of the dual learning graph
framework and by using representation-theoretic tools.