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)
- Quantum Private Information Retrieval has linear communication complexity
- Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers
- Privacy in Quantum Communication Complexity
- Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages
- Impossibility of Quantum Private Queries