文章基本信息

标题：Inverting a Permutation is as Hard as Unordered Search
本地全文：下载
作者：Ashwin Nayak
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2011
卷号：7
页码：19-25
DOI：10.4086/toc.2011.v007a002
语种：English
出版社：University of Chicago
摘要：We show how an algorithm for the problem of inverting a permutationmay be used to design one for the problem ofunordered search (with a unique solution).Since there is a straightforward reductionin the reverse direction, the problems are essentially equivalent.The reduction we present helps us bypass the hybrid argument due toBennett, Bernstein, Brassard, and Vazirani (1997) and the quantumadversary method due to Ambainis (2002) that were earlier used toderive lower bounds on the quantum query complexity of the problem ofinverting permutations. It directly implies that the quantum querycomplexity of the problem is asymptotically the same as that forunordered search, namely in $\Theta(\sqrt{n}\,)$.
关键词：unordered search; inverting permutations; query complexity; quantum algorithm; hybrid argument; randomized reduction