Quantum Private Information Retrieval with Sublinear Communication Complexity

Le Gall, François

doi:10.4086/toc.2012.v008a016

Volume 8 (2012) Article 16 pp. 369-374 [Note]

Quantum Private Information Retrieval with Sublinear Communication Complexity

by François Le Gall

Received: July 29, 2011
Published: July 26, 2012

Download article from ToC site:
[PDF (187K)] [PS (488K)] [Source ZIP]

Misc.:
[About the Author] [HTML Bibliography] [BibTeX]

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.

DOI: 10.4086/toc.2012.v008a016

Licensed under a Creative Commons Attribution License (CC-BY)