The structure of promises in quantum speedups

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 thesis, 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}1 in which each alphabet element occurs exactly once). We generalize this result to all functions f defined on orbits of the symmetric group action S., (which acts on an element of {0, 1, . . . , M - I}f 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)).

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Ben David, Shalev

Advisor dc:contributor.advisor

• Scott Aaronson.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/91097

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/91097