ECCC-Report TR10-121https://eccc.weizmann.ac.il/report/2010/121Comments and Revisions published for TR10-121en-usFri, 11 Mar 2011 05:28:27 +0200
Revision 1
| Inverting a permutation is as hard as unordered search |
Ashwin Nayak
https://eccc.weizmann.ac.il/report/2010/121#revision1We 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})$.Fri, 11 Mar 2011 05:28:27 +0200https://eccc.weizmann.ac.il/report/2010/121#revision1
Paper TR10-121
| Inverting a permutation is as hard as unordered search |
Ashwin Nayak
https://eccc.weizmann.ac.il/report/2010/121We 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}\,)$.Thu, 29 Jul 2010 14:59:04 +0300https://eccc.weizmann.ac.il/report/2010/121