Inverting a permutation is as hard as unordered search

DOI10.4086/TOC.2011.V007A002MaRDI QIDQ3002827zbMATH OpenOpenAlexFDO

Authors Ashwin Nayak

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1007.2899

zbMATH Keywords

hybrid argumentinverting permutationsquantum algorithmquery complexityrandomized reductionunordered search

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

Recommendations

• Quantum queries on permutations
• The query complexity of order-finding
• Quantum lower bounds by quantum arguments
• Quantum Queries on Permutations with a Promise
• Quantum lower bounds by quantum arguments

Cited in

(5)

• On quantum one-way permutations
• Quantum Queries on Permutations with a Promise
• Quantum queries on permutations
• Tight quantum time-space tradeoffs for permutation inversion
• Quantum search with in-place queries

This page was built for publication: Inverting a permutation is as hard as unordered search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002827)