paper

Quantum Private Information Retrieval with Sublinear Communication Complexity

arXiv:1107.5881 · doi:10.4086/toc.2012.v008a016

Abstract

This note presents a quantum protocol for private information retrieval, in the single-server case 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 Ω(n) bits of communication in this setting.

arXiv comment4 pages

References in corpus (2)

Cited by in corpus (5)