Volume 7 (2011) Article 2 pp. 19-25 [Note]
Inverting a Permutation is as Hard as Unordered Search
Received: July 28, 2010
Published: March 10, 2011
Download article from ToC site:
[PDF (174K)]    [PS (505K)]    [PS.GZ (179K)]
[Source ZIP]
Keywords: unordered search, inverting permutations, query complexity, quantum algorithm, hybrid argument, randomized reduction
ACM Classification: F.2.2, F.1.3, F.1.2
AMS Classification: 68Q12, 68Q17, 81P68, 68Q15, 68Q25

Abstract: [Plain Text Version]

We show how an algorithm for the problem of inverting a permutation may be used to design one for the problem of unordered search (with a unique solution). Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent.

The reduction we present helps us bypass the hybrid argument due to Bennett, Bernstein, Brassard, and Vazirani (1997) and the quantum adversary method due to Ambainis (2002) that were earlier used to derive lower bounds on the quantum query complexity of the problem of inverting permutations. It directly implies that the quantum query complexity of the problem is asymptotically the same as that for unordered search, namely in $\Theta(\sqrt{n}\,)$.