2014/09/11 by Shalev Ben-David, Ben-David, Shalev · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1409.3323
15 pages
arxiv created 2014/09/11 · arxiv updated 2014/09/12
It has long been known that in the usual black-box model, one cannot get super-polynomial quantum speedups without some promise on the inputs. In this paper, we examine certain types of symmetric promises, and show that they also cannot give rise to super-polynomial quantum speedups. We conclude that exponential quantum speedups only occur given "structured" promises on the input. Specifically, we show that there is a polynomial relationship of degree 12 between D(f) and Q(f) for any function f defined on permutations (elements of \0,1,…, M-1\n in which each alphabet element occurs exactly once). We generalize this result to all functions f defined on orbits of the symmetric group action Sn (which acts on an element of \0,1,…, M-1\n by permuting its entries). We also show that when M is constant, any function f defined on a "symmetric set" - one invariant under Sn - satisfies R(f)=O(Q(f)12(M-1)).