Abstract

In this talk I will discuss private information retrieval, a scenario where a user wants to retrieve an item from a (classical) database without revealing which item he/she is retrieving. I will present a quantum protocol solving this problem with O(\sqrt{n})-qubit communication complexity, where n denotes the size of the database, in the case of a single database. This is the first protocol with sublinear communication complexity in this setting. Especially, it is known that at least n bits of communication are needed for classical protocols. I will also describe some applications of this result to quantum cryptography.