摘要：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}\,)$.
