Quantum computers can search arbitrarily large databases by a single query
Quantum computers can search arbitrarily large databases by a single query
复制标题
DOI：
10.1103/physrevlett.79.4709
复制
发表时间：
1997-12-08
影响因子：
8.6
通讯作者：
Grover, LK
中科院分区：
文献类型：
--
作者：
Grover, LK
本文表明，一种能够查询与数据库多个项目相关信息的量子力学算法，可以在单次查询中搜索数据库以找到满足给定条件的唯一项目[查询被定义为对数据库提出的任何问题，数据库必须对其返回（是/否）答案]。经典算法将受限于至少log₂N次查询的信息理论界限，这是通过使用二分查找实现的。
This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (YES/NO answer]. A classical algorithm will be Limited to the information theoretic bound of at least log(2) N queries, which it would achieve by using a binary search.