首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Inverting a permutation is as hard as unordered search
  • 本地全文:下载
  • 作者:Ashwin Nayak
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2010
  • 卷号:2010
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要: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~(n) .
  • 关键词:Inverting a permutation, Quantum Algorithm, query complexity, Unordered search
国家哲学社会科学文献中心版权所有