Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 8 (2012) Article 16 pp. 369-374 [Note]
Quantum Private Information Retrieval with Sublinear Communication Complexity
Received: July 29, 2011
Published: July 26, 2012
Download article from ToC site:
[PDF (187K)] [PS (488K)] [Source ZIP]
Keywords: private information retrieval, quantum communication complexity
ACM Classification: F.2.3
AMS Classification: 81P68

Abstract: [Plain Text Version]

This note presents a quantum protocol for private information retrieval, in the case of a single (honest) server and with information-theoretical privacy, that has O(n)-qubit communication complexity, where n denotes the size of the database. In comparison, it is known that any classical protocol must use Ω(n) bits of communication in this setting.