Quantum private queries
Quantum private queries
复制标题
DOI：
10.1103/physrevlett.100.230502
复制
发表时间：
2008-06-13
影响因子：
8.6
通讯作者：
Maccone, Lorenzo
中科院分区：
文献类型：
--
作者：
Giovannetti, Vittorio;Lloyd, Seth;Maccone, Lorenzo
我们提出了一种对欺骗敏感的量子协议来对经典数据库进行私有搜索，该协议在通信复杂度方面是有效的。它允许用户从数据库提供程序中检索条目，而不显示他或她检索的条目：如果提供程序试图获取有关查询的信息，则查询数据库的人可以找到它。该协议还确保了数据库的完美数据隐私：用户可以在单个查询中检索的信息是有限的，不依赖于数据库的大小。相对于已知的私有信息检索策略（量子和经典），我们的协议在通信复杂度和运行时计算复杂度方面显示出指数级的降低。
We propose a cheat sensitive quantum protocol to perform a private search on a classical database which is efficient in terms of communication complexity. It allows a user to retrieve an item from the database provider without revealing which item he or she retrieved: if the provider tries to obtain information on the query, the person querying the database can find it out. The protocol ensures also perfect data privacy of the database: the information that the user can retrieve in a single query is bounded and does not depend on the size of the database. With respect to the known (quantum and classical) strategies for private information retrieval, our protocol displays an exponential reduction in communication complexity and in running-time computational complexity.