Quantum search for multiple items using parallel queries
Quantum search for multiple items using parallel queries
复制标题
使用并行查询对多个项目进行量子搜索
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Radhakrishnan
中科院分区：
文献类型：
--
作者：
Lov K. Grover;J. Radhakrishnan
在量子数据库搜索问题中，我们需要在数据库中搜索一个项目。在本文中，我们考虑了此问题的概括，在该问题中，我们提供了数据库的相同的应对，每个数据库都有N个项目，我们可以并行查询。然后，给定k项，我们需要确定存储这些项目的位置。我们表明，此任务的任何量子算法都必须执行Omega（SQRT {NK/D Min {D，K}}）并行查询。我们还设计了一种算法，其性能属于该下限的因子O（log d）。
In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.