Theory of Computing
-------------------
Title     : Quantum Private Information Retrieval with Sublinear Communication Complexity
Authors   : Francois Le Gall
Volume    : 8
Number    : 16
Pages     : 369-374
URL       : https://theoryofcomputing.org/articles/v008a016

Abstract
--------

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.