How significant are the known collision and element distinctness quantum algorithms?
How significant are the known collision and element distinctness quantum algorithms?
复制标题
已知的碰撞和元素独特性量子算法有多重要？
DOI：
--
复制
发表时间：
2003
影响因子：
1
通讯作者：
T. Rudolph
中科院分区：
文献类型：
--
作者：
Lov K. Grover;T. Rudolph
量子搜索是一种在O（N）步中搜索N种可能性以获得所需目标的技术。它已被应用于几个结构化问题的量子算法设计中。这些算法中的许多都需要大量的量子硬件，本文提出了一个准则，即算法宽度需要O（S）硬件，如果它比简单的量子搜索算法产生优于O（S）的加速比，那么它就被认为是重要的。这是因为通过将搜索空间划分为S个独立的部分并将问题交给S个独立的处理器进行量子搜索（在本文中，我们在讨论时间/空间复杂度时放弃了所有的几何因素），可以轻松地获得O（S）的加速。已知的碰撞和元素清晰度算法完全饱和的标准。
Quantum search is a technique for searching N possibilities for a desired target in O(√N)steps. It has been applied in the design of quantum algorithms fur several structuredproblems. Many of these algorithms require significant amount of quantum hardware.In this paper we propose the criterion that an algorithm width requires O(S) hardwareshould be considered significant if it produces a speedup of better than O(√S) over asimple quantum search algorithm. This is because a speedup of O (√S) can be triviallyobtained by dividing the search space into S separate parts and handing the problem to Sindependent processors that do a quantum search (in this paper we drop all logarithmicfactors when discussing time/space complexity). Known algorithms for collision andelement distinctness exactly saturate the criterion.