2026-07-26T05:32:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6688 2024-03-06T10:38:40Z ddc:004 open_access

The Structure of Promises in Quantum Speedups Ben-David, Shalev Quantum computing quantum query complexity decision tree complexity lower bounds quantum adversary method In 1998, Beals, Buhrman, Cleve, Mosca, and de Wolf showed that no super-polynomial quantum speedup is possible in the query complexity setting unless there is a promise on the input. We examine several types of "unstructured" promises, and show that they also are not compatible with super-polynomial quantum speedups. We conclude that such speedups are only possible when the input is known to have some structure. Specifically, we show that there is a polynomial relationship of degree 18 between D(f) and Q(f) for any Boolean function f defined on permutations (elements of [n]^n in which each alphabet element occurs exactly once). More generally, this holds for all f defined on orbits of the symmetric group action (which acts on an element of [M]^n by permuting its entries). We also show that any Boolean function f defined on a "symmetric" subset of the Boolean hypercube has a polynomial relationship between R(f) and Q(f) - although in that setting, D(f) may be exponentially larger. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shalev Ben-David 2016 Is Part Of LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2016.7 urn:nbn:de:0030-drops-66882 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode