Inverting a permutation is as hard as unordered search

Details Inverting a permutation is as hard as unordered search Inverting a permutation is as hard as unordered search

2010-07-17

arxiv.org/abs/1007.2899v3

Theory of Computing 7(1):19--25, 2011

Physics

Quantum Physics

5 pages. Numerous changes to improve the presentation

Scientific paper

10.4086/toc.2011.v007a002

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)).

Affiliated with

Also associated with

No associations

Rating

Inverting a permutation is as hard as unordered search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inverting a permutation is as hard as unordered search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inverting a permutation is as hard as unordered search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-658689