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
Published: July 26, 2012
Keywords: private information retrieval, quantum communication complexity
Categories: note, quantum computing, complexity theory, communication complexity, private information retrieval
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(\sqrt{n})$-qubit communication complexity, where $n$ denotes the size of the database. In comparison, it is known that any classical protocol must use $\Omega(n)$ bits of communication in this setting.