Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-121 | 11th March 2011 05:28

Inverting a permutation is as hard as unordered search

RSS-Feed

Abstract:

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



Changes to previous version:

Extensive editing to improve the presentation.


Paper:

TR10-121 | 28th July 2010 21:41

Inverting a permutation is as hard as unordered search





TR10-121
Authors: Ashwin Nayak
Publication: 29th July 2010 14:59
Downloads: 1099
Keywords: 


Abstract:

We describe a reduction from the problem of unordered search(with a unique solution) to the problem of inverting a permutation. Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent.

The reduction helps us bypass the Bennett-Bernstein-Brassard-Vazirani hybrid argument (1997} and the Ambainis quantum adversary method (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 in~$\Omega(\sqrt{n}\,)$.



ISSN 1433-8092 | Imprint