TY - GEN
T1 - Quantum lower bounds for tripartite versions of the hidden shift and the set equality problems
AU - Belovs, Aleksandrs
AU - Rosmanis, Ansis
N1 - Publisher Copyright:
© Aleksandrs Belovs and Ansis Rosmanis.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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×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 Ω(n1/3) and Ω(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 from [7].
AB - 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×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 Ω(n1/3) and Ω(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 from [7].
KW - Adversary Bound
KW - Dual Learning Graphs
KW - Quantum Query Complexity
KW - Representation Theory
UR - https://www.scopus.com/pages/publications/85052016358
U2 - 10.4230/LIPIcs.TQC.2018.3
DO - 10.4230/LIPIcs.TQC.2018.3
M3 - Conference paper
AN - SCOPUS:85052016358
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 3:1-3:15
BT - 13th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2018
A2 - Jeffery, Stacey
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 13th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2018
Y2 - 16 July 2018 through 18 July 2018
ER -