Quantum Private Information Retrieval with Sublinear Communication Complexity

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.

4 pages

References in corpus (1)

• Quantum private queries

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